Теорема Крускала–Катона

В алгебраической комбинаторике теорема Крускала –Катоны даёт полную характеристику f -векторов абстрактных симплициальных комплексов . Она включает в себя как частный случай теорему Эрдёша–Ко–Радо и может быть переформулирована в терминах однородных гиперграфов . Она названа в честь Джозефа Крускала и Дьюлы ОХ Катоны , но была независимо открыта несколькими другими.

Для двух положительных целых чисел N и i существует единственный способ разложить N в виде суммы биномиальных коэффициентов следующим образом:

${\displaystyle N={\binom {n_{i}}{i}}+{\binom {n_{i-1}}{i-1}}+\ldots +{\binom {n_{j}}{j}},\quad n_{i}>n_{i-1}>\ldots >n_{j}\geq j\geq 1.}$

Это расширение можно построить, применив жадный алгоритм : установим n _i равным максимальному n, такому, чтобы заменить N на разницу, i на i − 1, и повторять, пока разница не станет равной нулю. Определим${\displaystyle N\geq {\binom {n}{i}},}$

${\displaystyle N^{(i-1)}={\binom {n_{i}}{i-1}}+{\binom {n_{i-1}}{i-2}}+\ldots +{\binom {n_{j}}{j-1}}.}$

Целочисленный вектор является f -вектором некоторого -мерного симплициального комплекса тогда и только тогда, когда${\displaystyle (f_{0},f_{1},...,f_{d-1})}$${\displaystyle (d-1)}$

${\displaystyle 0\leq f_{i}^{(i)}\leq f_{i-1},\quad 1\leq i\leq d-1.}$

Пусть A — множество, состоящее из N различных i -элементных подмножеств фиксированного множества U («вселенная»), а B — множество всех -элементных подмножеств множеств в A. Расширим N , как указано выше. Тогда мощность B ограничена снизу следующим образом:${\displaystyle (ир)}$

${\displaystyle |B|\geq {\binom {n_{i}}{ir}}+{\binom {n_{i-1}}{ir-1}}+\ldots +{\binom {n_{j }}{младший}}.}$

Следующая более слабая, но полезная форма принадлежит Ласло Ловасу  (1993, 13.31b). Пусть A — множество i -элементных подмножеств фиксированного множества U («вселенная»), а B — множество всех -элементных подмножеств множеств в A . Если тогда .${\displaystyle (ир)}$${\displaystyle |A|={\binom {x}{i}}}$${\displaystyle |B|\geq {\binom {x}{ir}}}$

В этой формулировке x не обязательно должен быть целым числом. Значение биномиального выражения равно .${\displaystyle {\binom {x}{i}}={\frac {x(x-1)\dots (x-i+1)}{i!}}}$

Для каждого положительного i перечислите все i -элементные подмножества a ₁ < a ₂ < … a _i множества N натуральных чисел в колексикографическом порядке . Например, для i = 3 список начинается

${\displaystyle 123,124,134,234,125,135,235,145,245,345,\ldots .}$

Для данного вектора с положительными целыми компонентами пусть Δ _f будет подмножеством множества мощности 2 ^N, состоящим из пустого множества вместе с первыми i -элементными подмножествами N в списке для i = 1, …, d . Тогда следующие условия эквивалентны:${\displaystyle f=(f_{0},f_{1},...,f_{d-1})}$${\displaystyle f_{i-1}}$

1. Вектор f является f -вектором симплициального комплекса Δ .
2. Δ _f — симплициальный комплекс.
3. ${\displaystyle f_{i}^{(i)}\leq f_{i-1},\quad 1\leq i\leq d-1.}$

Сложное следствие: 1 ⇒ 2.

Теорема названа в честь Джозефа Крускала и Дьюлы О. Х. Катоны , которые опубликовали ее в 1963 и 1968 годах соответственно. Согласно Le & Römer (2019), она была открыта независимо Крускалом (1963), Катоной (1968), Марселем-Полем Шютценбергером  (1959), Харпером (1966) и Клементсом и Линдстрёмом (1969). Дональд Кнут  (2011) пишет, что самая ранняя из этих ссылок, Шютценбергера, имеет неполное доказательство.

• Теорема Шпернера

• Клементс, ГФ; Линдстрём, Б. (1969), «Обобщение комбинаторной теоремы Маколея», Журнал комбинаторной теории , 7 : 230–238, doi : 10.1016/S0021-9800(69)80016-5 , MR  0246781. Перепечатано в Gessel, Ira ; Rota, Gian-Carlo , eds. (1987), Classic Papers in Combinatorics , Бостон, Массачусетс: Birkhäuser Boston, Inc., стр. 416–424, doi :10.1007/978-0-8176-4842-8, ISBN 0-8176-3364-2, МР  0904286
• Харпер, Л. Х. (1966), «Оптимальные нумерации и изопериметрические задачи на графах», Журнал комбинаторной теории , 1 : 385–393, doi : 10.1016/S0021-9800(66)80059-5 , MR  0200192
• Катона, Дьюла О.Х. (1968), «Теорема о конечных множествах», Эрдеш, Пол ; Катона, Дьюла О.Г. (ред.), Теория графов , Akadémiai Kiadó и Academic Press. Перепечатано в Gessel & Rota (1987, стр. 381–401).
• Кнут, Дональд (2011), «7.2.1.3», Искусство программирования, том 4А: Комбинаторные алгоритмы, часть 1 , стр. 373.
• Крускаль, Джозеф Б. (1963), «Число симплексов в комплексе», в Bellman, Richard E. (ред.), Mathematical Optimization Techniques , University of California Press.
• Ловас, Ласло (1993), Комбинаторные задачи и упражнения , Амстердам: Северная Голландия, ISBN 9780444815040.
• Ле, Динь Ван; Ремер, Тим (2019), Результат типа Крускала-Катона и его приложения , arXiv : 1903.02998
• Стэнли, Ричард (1996), Комбинаторика и коммутативная алгебра , Progress in Mathematics, т. 41 (2-е изд.), Бостон, Массачусетс: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9.
• Шютценбергер, MP (1959), «Характерное свойство некоторых многочленов Э. Ф. Мура и К. Э. Шеннона», RLE Quarterly Progress Report , 55 (Обработка и передача информации): 117–118 , получено 19 марта 2019 г..

• Теорема Крускала-Катона на вики-сайте polymath1