Symmetric hypergraph theorem
From Wikipedia, the free encyclopedia
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 |
[edit] 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 it's 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
[edit] Applications
This theorem has applications to Ramsey theory, specifically graph Ramsey theory. Using this theorem, the following relationship between graph Ramsey theory and extremal graph theory can be shown:
Let G be a graph. Define ex(n,G) as the maximum number of edges a graph on n vertices may have without containing a copy of G, and define R(G;t) to be the minimum n such that whenever the edges of Kn are coloured with t colours, there is a monochromatic copy of G. Let
and
Then for all 
,
[edit] See also
[edit] References
- ^ R. Graham, B. Rothschild, J. Spencer. Ramsey Theory. 2nd ed., Wiley, New-York, 1990.
