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

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

Заявление

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

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\geq {\binom {n}{i}},$ замените N на разницу, i на i - 1, и повторяйте, пока разница не станет нулевой. Определять

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

Утверждение для симплициальных комплексов

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

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

Заявление об однородных гиперграфах

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

|B|\geq {\binom {n_{i}}{i-r}}+{\binom {n_{i-1}}{i-r-1}}+\ldots +{\binom {n_{j}}{j-r}}.

Упрощенная формулировка Ловаса

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

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

Ингредиенты доказательства

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

123,124,134,234,125,135,235,145,245,345,\ldots .

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

Вектор f является f -вектором симплициального комплекса Δ .
∆ _f — симплициальный комплекс.
$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), «Обобщение комбинаторной теоремы Маколея», Journal of Combinatorial Theory , 7 : 230–238, doi : 10.1016/S0021-9800(69)80016-5 , MR 0246781 . Перепечатано в Гессель, Ира ; Рота, Джан-Карло , ред. (1987), Классические статьи по комбинаторике , Бостон, Массачусетс: 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», Искусство компьютерного программирования, том 4A: Комбинаторные алгоритмы, часть 1 , с. 373 .
Краскал, Джозеф Б. (1963), «Число симплексов в комплексе», Беллман, Ричард Э. (редактор), «Методы математической оптимизации» , University of California Press .
Ловас, Ласло (1993), Комбинаторные задачи и упражнения , Амстердам: Северная Голландия, ISBN 9780444815040 .
Ле, Динь Ван; Ремер, Тим (2019), Результат типа Крускала-Катона и его приложения , arXiv : 1903.02998
Стэнли, Ричард (1996), Комбинаторика и коммутативная алгебра , Progress in Mathematics, vol. 41 (2-е изд.), Бостон, Массачусетс: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9 .
Шютценбергер, член парламента (1959), «Характеристическое свойство некоторых полиномов Э.Ф. Мура и К.Э. Шеннона» , Ежеквартальный отчет о ходе работы RLE , 55 (Обработка и передача информации): 117–118 , получено 19 марта 2019 г.

Внешние ссылки

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