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

У алгебричній комбінаториці теорема Крускала-Катона дає повну характеристику 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; будемо повторювати ці операції поки різниця не стане 0. Визначимо

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

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

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

0\leq f_{i}\leq f_{i-1}^{(i)},\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}}.

Доведення

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

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

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

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

Дивитися також

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

Примітки

Kruskal, J. B. (1963). The number of simplices in a complex. У Bellman, R.. Mathematical Optimization Techniques. University of California Press..

Katona, G. O. H. (1968). A theorem of finite sets. У Erdős, P.; Katona, G. O. H.. Theory of Graphs. Akadémiai Kiadó and Academic Press..

Knuth, D.. The Art of Computer Programming, pre-fascicle 3a: Generating all combinations.. Contains a proof via a more general theorem in discrete geometry.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.