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 [R. Graham, B. Rothschild, J. Spencer. Ramsey Theory. 2nd ed., Wiley, New-York, 1990.] .

tatement

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

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

ee also

* Ramsey theory

References