Kruskal–Katona theorem

Statement

Given two positive integers N and i, there is a unique way to expand N as a sum of binomial coefficients as follows:

This expansion can be constructed by applying the greedy algorithm: set n_i to be the maximal n such that N ≥ ( n i ) , replace N with the difference, i with i − 1, and repeat until the difference becomes zero. Define

Statement for simplicial complexes

An integral vector ( f 0 , f 1 , . . . , f d − 1 ) is the f-vector of some ( d − 1 ) -dimensional simplicial complex if and only if

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:

Ingredients of the proof

For every positive i, list all i-element subsets a₁ < a₂ < … a_i of the set N of natural numbers in the colexicographical order. For example, for i = 3, the list begins

Given a vector f = ( f 0 , f 1 , . . . , f d − 1 ) with positive integer components, let Δ_f be the subset of the power set 2^N consisting of the empty set together with the first f i − 1 i-element subsets of N in the list for i = 1, …, d. Then the following conditions are equivalent:

1. Vector f is the f-vector of a simplicial complex Δ.
2. Δ_f is a simplicial complex.
3. f i ≤ f i − 1 ( i ) , 1 ≤ i ≤ d − 1.

The difficult implication is 1 ⇒ 2.