Теорема о симметричном гиперграфе - Symmetric hypergraph theorem

В Теорема о симметричном гиперграфе это теорема в комбинаторика который устанавливает верхнюю границу хроматическое число из график (или же гиперграф в целом). Первоначальная ссылка на эту статью на данный момент неизвестна и была названа фольклор.^[1]

Заявление

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

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

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

Приложения

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

Смотрите также

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

Примечания