Теорема Крускала — Катони
У алгебричній комбінаториці теорема Крускала-Катона дає повну характеристику 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. Тоді наступні умови еквівалентні:
- Вектор f є f-вектором симпліційного комплексу Δ.
- Δf - симпліційний комплекс.
Дивитися також ред.
Примітки ред.
- 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