Symmetric hypergraph theorem

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.[1] Contents 1 Statement 2 Applications 3 See also 4 Notes Statement A group {displaystyle G} acting on a set {displaystyle S} is called transitive if given any two elements {displaystyle x} and {displaystyle y} in {displaystyle S} , there exists an element {displaystyle f} of {displaystyle G} such that {displaystyle f(x)=y} . A graph (or hypergraph) is called symmetric if its automorphism group is transitive.

Theorem. Let {displaystyle H=(S,E)} be a symmetric hypergraph. Let {displaystyle m=|S|} , and let {displaystyle chi (H)} denote the chromatic number of {displaystyle H} , and let {displaystyle alpha (H)} denote the independence number of {displaystyle H} . Then {displaystyle 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).

See also Ramsey theory Notes ^ R. Graham, B. Rothschild, J. Spencer. Ramsey Theory. 2nd ed., Wiley, New-York, 1990. Categories: Graph coloringTheorems in graph theory