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]

Statement

edit

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 (or hypergraph) 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

 

Applications

edit

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

edit

Notes

edit
  1. ^ R. Graham, B. Rothschild, J. Spencer. Ramsey Theory. 2nd ed., Wiley, New-York, 1990.