Відмінності між версіями «Теорема Крускала — Катони»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[неперевірена версія][неперевірена версія]
 
(Немає відмінностей)

Поточна версія на 00:47, 21 лютого 2019

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

Твердження[ред. | ред. код]

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

Цей розклад можна побудувати, застосовуючи жадібний алгоритм: візьмемо ni як максимальне n, таке що замінимо N різницею, i замінимо на i − 1; будемо повторювати ці операції поки різниця не стане 0. Визначимо

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

Вектор  це f-вектор деякого -мірного симпліціального комплексу, тоді і тільки тоді

Твердження для рівномірних гіперграфів [ред. | ред. код]

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

Доведення[ред. | ред. код]

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

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

  1. Вектор f є f-вектором симпліціального комплексу Δ.
  2. Δf - симпліціальний комплекс.

Дивитися також[ред. | ред. код]

Примітки[ред. | ред. код]

  • Kruskal, J. B. (1963). The number of simplices in a complex. У Bellman, R.. Mathematical Optimization Techniques. University of California Press. .
  • Stanley, Richard (1996), Combinatorics and commutative algebra, Progress in Mathematics, 41 (2nd ed.), Boston, MA: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9 .

Посилання[ред. | ред. код]