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 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 its 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).

gollark: I mostly just avoid data-related worries by blocking stuff very intensively and also blocking all adverts.
gollark: And has almost certainly been patched by now?
gollark: This seems to be from 2014?
gollark: What do you mean ”””cannons”””?
gollark: As I said, presumably DRM stuff. Content like movies probably goes through special pipelines designed to not let you copy/screenshot/etc, which is ultimately futile but implemented anyway.

See also

Notes

  1. R. Graham, B. Rothschild, J. Spencer. Ramsey Theory. 2nd ed., Wiley, New-York, 1990.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.