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 $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. Using this theorem, the following relationship between graph Ramsey theory and extremal graph theory can be shown:

Let $G$ be a graph. Define $ex(n,G)$ as the maximum number of edges a graph on n vertices may have without containing a copy of $G$, and define $R(G;t)$ to be the minimum $n$ such that whenever the edges of $K_{n}$ are coloured with $t$ colours, there is a monochromatic copy of $G$. Let

$f(m)={\frac {m \choose 2}{ex(n,G)}}$

and

$g(m)=1+f(m)\ln {m \choose 2}.$

Then for all $t\in \mathbb {N}$,

$g^{-1}(t)<R(G;t)\leq f^{-1}(t)+1$

See Also

• Ramsey theory