Symmetric hypergraph theorem

The Symmetric hypergraph theorem is a theorem in combinatorics that puts an upper bound on the chromatic number of a graph. The original reference for this paper is unknown at the moment, and has been called folklore.

Statement

A group acting on a set is called transitive if given any two elements and in, there exists an element of such that. A graph is called symmetric if its automorphism group is transitive.
Theorem. Let be a symmetric hypergraph. Let, and let denote the chromatic number of, and let denote the independence number of. Then

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.
The theorem has also been applied to problems involving arithmetic progressions. For instance, let denote the minimum number of colors required so that there exists an -coloring of that avoids any monochromatic -term arithmetic progression. The Symmetric Hypergraph Theorem can be used to show that