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

У алгебричній комбінаториці теорема Крускала-Катона дає повну характеристику f-векторів з абстрактних симпліційних комплексів. Вона включає в себе як особливий випадок теорему Ердеша — Ко — Радо. Теорема названа на честь Йосипа Крускала та Дьюли О.Г. Катона. Це було також доведено Марсель-Полем Шюценбергом, але його внесок уникав уваги протягом декількох років.

Твердження

Дано цілі додатні числа N та I, існує єдиний спосіб розкласти N у вигляді суми біноміальних коефіцієнтів наступним чином:

$N=(\genfrac{}{}{0ex}{}{n_i}{i})+(\genfrac{}{}{0ex}{}{n_{i-1}}{i-1})+\dots +(\genfrac{}{}{0ex}{}{n_j}{j}),n_i>n_{i-1}>\dots >n_j\ge j\ge 1.$

Цей розклад можна побудувати, застосовуючи жадібний алгоритм: візьмемо n_i як максимальне n, таке що $N\ge (\genfrac{}{}{0ex}{}{n}{i}),$ замінимо N різницею, i замінимо на i − 1; будемо повторювати ці операції поки різниця не стане 0. Визначимо

$N^{(i)}=(\genfrac{}{}{0ex}{}{n_i}{i+1})+(\genfrac{}{}{0ex}{}{n_{i-1}}{i})+\dots +(\genfrac{}{}{0ex}{}{n_j}{j+1}).$

Твердження для симпліційних комплексів

Вектор $(f_0,f_1,...,f_{d-1})$ це f-вектор деякого $(d-1)$-мірного симпліційного комплексу, тоді і тільки тоді

$0\le f_i\le f_{i-1}^{(i)},1\le i\le d-1.$

Твердження для рівномірних гіперграфів

Нехай A це множина яка складається з N різних i-елементних підмножин фіксованої множини U ("універсум") і B це множина всіх $(i-r)$-елементних підмножин A. Розкладемо N як описано вище. Тоді потужність B обмежена знизу як показано далі:

$|B|\ge (\genfrac{}{}{0ex}{}{n_i}{i-r})+(\genfrac{}{}{0ex}{}{n_{i-1}}{i-r-1})+\dots +(\genfrac{}{}{0ex}{}{n_j}{j-r}).$

Доведення

Для кожного позитивного i, перерахуємо всі і-елементні підмножини a1 < a2 < … ai з множини N натуральних чисел в колексикографічному порядку. Наприклад, для і = 3, список починається:

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

Даний вектор $f=(f_0,f_1,...,f_{d-1})$ з позитивними цілими компонентами, нехай Δf - це підмножина булеану $2^n$, що складається з порожньої множини разом з першими $f_{i-1}$ i-елементними підмножинами N в списку для i = 1, ..., d. Тоді наступні умови еквівалентні:

1. Вектор f є f-вектором симпліційного комплексу Δ.
2. Δf - симпліційний комплекс.
3. $f_i\le f_{i-1}^{(i)},1\le i\le d-1.$

Див. також

• Шаблон:Не перекладено

Джерела

• Шаблон:Вишенський.Перестюк.Комбінаторика
• Шаблон:TAOCP.v3
• Шаблон:Citation.
• Шаблон:Citation.
• Stanley, Richard (1996), Combinatorics and commutative algebra, Progress in Mathematics, 41 (2nd ed.), Boston, MA: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9.

Посилання

• Kruskal-Katona theorem на polymath1 wiki