Symmetric hypergraph theorem

From Wikipedia, the free encyclopedia

The Symmetric hypergraph theorem is a theorem in combinatorics that puts an upper bound on the chromatic number of a graph (or hypergraph in general). The original reference for this paper is unknown at the moment, and has been called folklore. ^[1]

A group $G$ acting on a set $S$ is called transitive if given any two elements $x$ and $y$ in $S$ , there exists an element $f$ of $G$ such that $f(x)=y$ . A graph (or hypergraph) is called symmetric if its automorphism group is transitive.

Theorem. Let $H=(S,E)$ be a symmetric hypergraph. Let $m=|S|$ , and let $\chi (H)$ denote the chromatic number of $H$ , and let $\alpha (H)$ denote the independence number of $H$ . Then

$\chi (H)\leq 1+{\frac {\ln {m}}{-\ln {(1-\alpha (H)/m)}}}$

Applications

This theorem has applications to Ramsey theory, specifically graph Ramsey theory. Using this theorem, a relationship between the graph Ramsey numbers and the extremal numbers can be shown (see Graham-Rothschild-Spencer for the details).

The theorem has also been applied to problems involving arithmetic progressions. For instance, let $r_{k}(n)$ denote the minimum number of colors required so that there exists an $r_{k}(n)$ -coloring of $[1,n]$ that avoids any monochromatic $k$ -term arithmetic progression. The Symmetric Hypergraph Theorem can be used to show that^[2]

r_{k}(n)<{\frac {2n\log n}{\log \log n}}(1+o(1))

See also

Notes

Related Articles

Wikiwand AI