Symmetric hypergraph theorem

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]

Statement

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

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

$${\displaystyle \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 ${\displaystyle r_{k}(n)}$ denote the minimum number of colors required so that there exists an ${\displaystyle r_{k}(n)}$-coloring of ${\displaystyle [1,n]}$ that avoids any monochromatic ${\displaystyle k}$-term arithmetic progression. The Symmetric Hypergraph Theorem can be used to show that^[2]

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

See also

• Ramsey theory
• Van der Waerden's theorem