About the numbers of faces of different dimensions in an abstract simplicial complex
In algebraic combinatorics, the Kruskal–Katona theorem gives a complete characterization of the "f"-vectors of abstract simplicial complexes. 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 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 coefficients as follows:
 formula_1
This expansion can be constructed by applying the greedy algorithm: set "n""i" to be the maximal "n" such that formula_2 replace "N" with the difference, "i" with "i" − 1, and repeat until the difference becomes zero. Define
 formula_3
Statement for simplicial complexes.
An integral vector formula_4 is the "f"-vector of some formula_5-dimensional simplicial complex if and only if
 formula_6
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 formula_7-element subsets of the sets in "A". Expand "N" as above. Then the cardinality of "B" is bounded below as follows:
 formula_8
Lovász' simplified formulation.
The following weaker but useful form is due to László Lovász (1993, 13.31b). Let "A" be a set of "i"-element subsets of a fixed set "U" ("the universe") and "B" be the set of all formula_7-element subsets of the sets in "A". If formula_10 then formula_11.
In this formulation, "x" need not be an integer. The value of the binomial expression is formula_12.
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 the colexicographical order. For example, for "i" = 3, the list begins
 formula_13
Given a vector formula_14 with positive integer components, let "Δ""f" be the subset of the power set 2N consisting of the empty set together with the first formula_15 "i"-element subsets of N in the list for "i" = 1, …, "d". Then the following conditions are equivalent:
The difficult implication is 1 ⇒ 2.
History.
The theorem is named after Joseph Kruskal and Gyula O. H. Katona, who published it in 1963 and 1968 respectively.
According to , it was discovered independently by , , Marcel-Paul Schützenberger (1959), , and .
Donald Knuth (2011) writes that the earliest of these references, by Schützenberger, has an incomplete proof.