HOME

TheInfoList



OR:

In algebraic combinatorics, the Kruskal–Katona theorem gives a complete characterization of the ''f''-vectors of
abstract simplicial complex In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely c ...
es. It includes as a special case the Erdős–Ko–Rado theorem and can be restated in terms of uniform hypergraphs. It is named after
Joseph Kruskal Joseph Bernard Kruskal, Jr. (; January 29, 1928 – September 19, 2010) was an American mathematician, statistician, computer scientist and psychometrician. Personal life Kruskal was born to a Jewish family in New York City to a successful fu ...
and Gyula O. H. Katona, but has been independently discovered by several others.


Statement

Given two positive integers ''N'' and ''i'', there is a unique way to expand ''N'' as a sum of
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s as follows: : N=\binom+\binom+\ldots+\binom,\quad n_i > n_ > \ldots > n_j \geq j\geq 1. This expansion can be constructed by applying the
greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
: set ''n''''i'' to be the maximal ''n'' such that N\geq \binom, replace ''N'' with the difference, ''i'' with ''i'' − 1, and repeat until the difference becomes zero. Define : N^=\binom+\binom+\ldots+\binom.


Statement for simplicial complexes

An integral vector (f_0, f_1, ..., f_) is the ''f''-vector of some (d-1)-dimensional simplicial complex if and only if : 0 \leq f_^ \leq f_,\quad 1\leq i\leq d-1.


Statement for uniform hypergraphs

Let ''A'' be a set consisting of ''N'' distinct ''i''-element subsets of a fixed set ''U'' ("the universe") and ''B'' be the set of all (i-r)-element subsets of the sets in ''A''. Expand ''N'' as above. Then the cardinality of ''B'' is bounded below as follows: : , B, \geq \binom+\binom+\ldots+\binom.


Lovász' simplified formulation

The following weaker but useful form is due to . Let ''A'' be a set of ''i''-element subsets of a fixed set ''U'' ("the universe") and ''B'' be the set of all (i-r)-element subsets of the sets in ''A''. If , A, = \binom then , B, \geq \binom. In this formulation, ''x'' need not be an integer. The value of the binomial expression is \binom = \frac.


Ingredients of the proof

For every positive ''i'', list all ''i''-element subsets ''a''1 < ''a''2 < … ''a''''i'' of the set N of
natural numbers In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...
in the colexicographical order. For example, for ''i'' = 3, the list begins : 123, 124, 134, 234, 125, 135, 235, 145, 245, 345, \ldots. Given a vector f = (f_0, f_1, ..., f_) with positive integer components, let ''Δ''''f'' be the subset of the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
2N consisting of the empty set together with the first f_ ''i''-element subsets of N in the list for ''i'' = 1, …, ''d''. Then the following conditions are equivalent: # Vector ''f'' is the ''f''-vector of a simplicial complex ''Δ''. # ''Δ''''f'' is a simplicial complex. # f_^ \leq f_,\quad 1\leq i\leq d-1. The difficult implication is 1 ⇒ 2.


History

The theorem is named after
Joseph Kruskal Joseph Bernard Kruskal, Jr. (; January 29, 1928 – September 19, 2010) was an American mathematician, statistician, computer scientist and psychometrician. Personal life Kruskal was born to a Jewish family in New York City to a successful fu ...
and Gyula O. H. Katona, who published it in 1963 and 1968 respectively. According to , it was discovered independently by , , , , and . writes that the earliest of these references, by Schützenberger, has an incomplete proof.


See also

* Sperner's theorem


References

*. Reprinted in * *. Reprinted in . *. *. *. * *. *.


External links


Kruskal-Katona theorem
on the polymath1 wiki {{DEFAULTSORT:Kruskal-Katona theorem Algebraic combinatorics Hypergraphs Families of sets Theorems in combinatorics Extremal combinatorics