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].

1 Statement
2 Applications
3 See also
4 References

[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

$\chi(H) < 1 + \frac{m}{\alpha(H)}\ln m.$

[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 $e x (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 $K n$ are coloured with $t$ colours, there is a monochromatic copy of $G$ . Let