Symmetric hypergraph theorem

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. It is most well known from .

Statement

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 it's 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)<1+{\frac {m}{\alpha (H)}}\ln m.$

Applications

This theorem has applications to Ramsey theory, specifically graph Ramsey theory.

See Also

• Ramsey theory