Symmetric hypergraph theorem

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 its 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) \leq 1 + \frac{\ln{m}}{-\ln{(1-\alpha(H)/m)}} == 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). The theorem has also been applied to problems involving arithmetic progressions. For instance, let r_k(n) denote the minimum number of colors required so that there exists an r_k(n)-coloring of [1,n] that avoids any monochromatic k-term arithmetic progression. The Symmetric Hypergraph Theorem can be used to show that :r_k(n) == See also ==