Kruskal–Katona theorem

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. The theorem is named after Joseph Kruskal and Gyula O. H. Katona. It was independently proved by Marcel-Paul Schützenberger, but his contribution escaped notice for several years.

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 ${\displaystyle N\geq {\binom {n}{i}},}$ replace N with the difference, i with i − 1, and repeat until the difference becomes zero. Define

An integral vector ${\displaystyle (f_{0},f_{1},...,f_{d-1})}$ is the f-vector of some ${\displaystyle (d-1)}$-dimensional simplicial complex if and only if

...
Wikipedia