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 formula_1 acting on a set formula_2 is called "transitive" if given any two elements formula_3 and formula_4 in formula_2, there exists an element formula_6 of formula_1 such that formula_8. A graph (or hypergraph) is called "symmetric" if its automorphism group is transitive. Theorem. Let formula_9 be a symmetric hypergraph. Let formula_10, and let  formula_11 denote the chromatic number of formula_12, and let formula_13 denote the independence number of formula_12. Then formula_15 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).