Введение
О числе граней различных размерностей в абстрактном симплициальном комплексе. В алгебраической комбинаторике теорема Крускала — Катоны дает полную характеристику f-векторов абстрактных симплициальных комплексов. Она включает в себя теорему Эрдеша — Ко — Радо как частный случай и может быть переформулирована в терминах однородных гиперграфов. Теорема названа в честь Джозефа Крускала и Гюлы О. Х. Катоны, но была открыта независимо несколькими другими исследователями.
In algebraic combinatorics, the Kruskal–Katona theorem gives a complete characterization of the f vectors of abstract simplicial complexes. It includes as a special case the Erdős–Ko–Rado theorem and can be restated in terms of uniform hypergraphs. It is named after Joseph Kruskal and Gyula O. H. Katona, but has been independently discovered by several others.
Заявление для однородных гиперграфов
Пусть A — множество, состоящее из N различных i-элементных подмножеств фиксированного множества U ("универсум"), а B — множество всех подмножеств элементов множеств из A. Разложим N, как описано выше. Тогда кардинальность B ограничена снизу следующим образом:
Упрощенная формулировка Ловаша
Следующая более слабая, но полезная форма заключается в следующем: пусть A – множество подмножеств из i элементов фиксированного множества U ("универсум"), а B – множество всех подмножеств элементов множеств из A. Если , то в данной формулировке x не обязательно должно быть целым числом. Значение биномиального выражения равно .
In this formulation, x need not be an integer. The value of the binomial expression is .
Состав доказательства
Для каждого положительного i перечислите все i-элементные подмножества a1 < a2 < … < ai множества N натуральных чисел в лексикографическом порядке. Например, для i = 3, список начинается с…
Пусть дан вектор f с положительными целочисленными компонентами. Обозначим Δf подмножеством множества степеней 2N, состоящим из пустого множества вместе с первыми i элементами подмножеств N в списке для i = 1, 2, …, d. Тогда следующие условия эквивалентны:
Вектор f является f-вектором симплициального комплекса Δ.
Δf является симплициальным комплексом. Сложная часть доказательства – импликация 1 ⇒ 2.
Δf is a simplicial complex. The difficult implication is 1 ⇒ 2.
История
Теорема названа в честь Джозефа Крускаля и Гюлы О. Х. Катоны, которые опубликовали ее в 1963 и 1968 годах соответственно. Согласно [источнику], она была открыта независимо от [авторов], [авторов], [авторов], [авторов] и [авторов]. [Автор] пишет, что самый ранний из этих источников, работа Шутценбергера, содержит неполное доказательство.