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.

Statement

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

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

[math]\displaystyle{ \chi(H) \leq 1 + \frac{\ln{m}}{-\ln{(1-\alpha(H)/m)}} }[/math]

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).

See also

• Ramsey theory