Теорема о симметричном гиперграфе

Теорема симметричном гиперграфе — это теорема комбинаторики , которая устанавливает верхнюю границу хроматического числа графа о (или гиперграфа в целом). Оригинальная ссылка на эту статью на данный момент неизвестна и называется «фольклор» .

Заявление

Группа ​ $G$ играю на съемочной площадке $S$ называется транзитивным, если даны любые два элемента $x$ и $y$ в $S$, существует элемент $f$ из $G$ такой, что $f(x)=y$. Граф (или гиперграф) называется симметричным , если его группа автоморфизмов транзитивна.

Теорема. Позволять $H=(S,E)$ быть симметричным гиперграфом. Позволять $m=|S|$, и пусть $\chi (H)$ обозначают хроматическое число $H$, и пусть $\alpha (H)$ обозначают независимости число $H$. Затем

$$\chi (H)\leq 1+{\frac {\ln {m}}{-\ln {(1-\alpha (H)/m)}}}$$

Приложения

Эта теорема имеет приложения к теории Рамсея , в частности к теории графов Рамсея . Используя эту теорему, можно показать связь между числами Рамсея на графике и экстремальными числами (подробности см. в разделе Грэма-Ротшильда-Спенсера).

См. также

• Теория Рэмси