Harman Patil (Editor)

Symmetric hypergraph theorem

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

Statement

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 χ ( H ) denote the chromatic number of H , and let α ( H ) denote the independence number of H . Then

χ ( H ) < 1 + m α ( H ) ln ⁡ 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).

References

Symmetric hypergraph theorem Wikipedia
(Text) CC BY-SA