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

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) < 1 + \frac{m}{\alpha(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).

See also

Notes

  1. ↑ R. Graham, B. Rothschild, J. Spencer. Ramsey Theory. 2nd ed., Wiley, New-York, 1990.
This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.