imported>Dexxor: better link

2024-09-21T15:28:54Z

better link

New page

{{one source |date=April 2024}}
The '''Symmetric hypergraph theorem''' is a theorem in [[combinatorics]] that puts an upper bound on the [[Graph coloring#Chromatic number|chromatic number]] of a [[Graph (discrete mathematics)|graph]] (or [[hypergraph]] in general). The original reference for this paper is unknown at the moment, and has been called [[Mathematical folklore|folklore]].<ref>R. Graham, B. Rothschild, J. Spencer. Ramsey Theory. 2nd ed., Wiley, New-York, 1990.</ref>

== Statement ==
A [[Group (mathematics)|group]] <math>G</math> [[Group action (mathematics)|acting on a set]] <math>S</math> is called ''[[Group action (mathematics)#Types of actions|transitive]]'' if given any two elements <math>x</math> and <math>y</math> in <math>S</math>, there exists an element <math>f</math> of <math>G</math> such that <math>f(x) = y</math>. A graph (or hypergraph) is called ''symmetric'' if its [[automorphism group]] is transitive.

'''Theorem.''' Let <math>H = (S, E)</math> be a symmetric hypergraph. Let <math>m = |S|</math>, and let <math>\chi(H)</math> denote the chromatic number of <math>H</math>, and let <math>\alpha(H)</math> denote the [[Glossary of graph theory#Independence|independence number]] of <math>H</math>. Then

<math display="block">\chi(H) \leq 1 + \frac{\ln{m}}{-\ln{(1-\alpha(H)/m)}}</math>

== 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 ==
* [[Ramsey theory]]

== Notes ==
<references />

[[Category:Graph coloring]]
[[Category:Theorems in graph theory]]

{{graph-stub}}

Symmetric hypergraph theorem - Revision history

imported>Dexxor: better link