Expansive: Difference between revisions
en>777sms No edit summary |
en>Squids and Chips m WPCleaner v1.27 - Repaired 1 link to disambiguation page - (You can help) - Rigid |
||
Line 1: | Line 1: | ||
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 (mathematics)|graph]] (or [[hypergraph]] in general). The original reference for this paper is unknown at the moment, and has been called 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|acting on a set]] <math>S</math> is called ''[[Group action#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 it's [[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 | |||
<center><math>\chi(H) < 1 + \frac{m}{\alpha(H)}\ln m.</math></center> | |||
==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]] |
Latest revision as of 23:38, 22 May 2013
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 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 it's 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
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
- ↑ R. Graham, B. Rothschild, J. Spencer. Ramsey Theory. 2nd ed., Wiley, New-York, 1990.