Теорема Крускала – Катоны - Kruskal–Katona theorem

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

Заявление

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

{ displaystyle 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.}

Это разложение можно построить, применяя жадный алгоритм: набор п_я быть максимальным п такой, что ${ displaystyle N geq { binom {n} {i}},}$ заменять N с той разницей, я с я - 1 и повторяйте, пока разница не станет равной нулю. Определять

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

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

Интегральный вектор ${ displaystyle (f_ {0}, f_ {1}, ..., f_ {d-1})}$ это ж-вектор некоторых ${ displaystyle (d-1)}$ -мерный симплициальный комплекс тогда и только тогда, когда

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

Утверждение для равномерных гиперграфов

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

{ displaystyle | B | geq { binom {n_ {i}} {ir}} + { binom {n_ {i-1}} {ir-1}} + ldots + { binom {n_ {j) }} {jr}}.}

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

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

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

Состав доказательства

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

{ displaystyle 123,124,134,234,125,135,235,145,245,345, ldots.}

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