In algebraic combinatorics, the Kruskal–Katona theorem gives a complete characterization of the -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 and , there is a unique way to expand as a sum of binomial coefficients as follows:

This expansion can be constructed by applying the greedy algorithm: set to be the maximal such that replace with the difference, with , and repeat until the difference becomes zero. Define

Statement for simplicial complexes

An integral vector is the -vector of some -dimensional simplicial complex if and only if

Statement for uniform hypergraphs

Let be a set consisting of distinct -element subsets of a fixed set ("the universe") and be the set of all -element subsets of the sets in . Expand as above. Then the cardinality of is bounded below as follows:

Lovász' simplified formulation

The following weaker but useful form is due to . Let be a set of -element subsets of a fixed set ("the universe") and be the set of all -element subsets of the sets in . If then .

In this formulation, need not be an integer. The value of the binomial expression is .

Ingredients of the proof

For every positive , list all -element subsets of the set of natural numbers in the colexicographical order. For example, for , the list begins

Given a vector with positive integer components, let be the subset of the power set consisting of the empty set together with the first -element subsets of in the list for . Then the following conditions are equivalent:

Vector is the -vector of a simplicial complex . is a simplicial complex. for .

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 , , , , 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