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.

Statement

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

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

χ ( H ) ≤ 1 + ln ⁡ m − ln ⁡ ( 1 − α ( H ) / m ) {\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 r k ( n ) {\displaystyle r_{k}(n)} denote the minimum number of colors required so that there exists an r k ( n ) {\displaystyle r_{k}(n)}-coloring of [ 1 , n ] {\displaystyle [1,n]} that avoids any monochromatic k {\displaystyle k}-term arithmetic progression. The Symmetric Hypergraph Theorem can be used to show that

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

See also

Notes