 Kruskal-Katona Theorem
Get Kruskal%E2%80%93Katona Theorem essential facts below. View Videos or join the Kruskal%E2%80%93Katona Theorem discussion. Add Kruskal%E2%80%93Katona Theorem to your PopFlock.com topic list for future reference or share this resource on social media.
Kruskal%E2%80%93Katona 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. 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:

$N={\binom {n_{i}}{i}}+{\binom {n_{i-1}}{i-1}}+\ldots +{\binom {n_{j}}{j}},\quad n_{i}>n_{i-1}>\ldots >n_{j}\geq j\geq 1.$ This expansion can be constructed by applying the greedy algorithm: set ni to be the maximal n such that $N\geq {\binom {n}{i}},$ replace N with the difference, i with i - 1, and repeat until the difference becomes zero. Define

$N^{(i)}={\binom {n_{i}}{i+1}}+{\binom {n_{i-1}}{i}}+\ldots +{\binom {n_{j}}{j+1}}.$ ### 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

$0\leq f_{i}\leq f_{i-1}^{(i)},\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 {n_{i}}{i-r}}+{\binom {n_{i-1}}{i-r-1}}+\ldots +{\binom {n_{j}}{j-r}}.$ ### Lovász' simplified formulation

The following weaker but useful form is due to László Lovász (1993) 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 {x}{i}}$ then $|B|\geq {\binom {x}{i-r}}$ .

In this formulation, x need not be an integer. The value of the binomial expression is ${\binom {x}{i}}={\frac {x(x-1)\dots (x-i+1)}{i!}}$ .

## Ingredients of the proof

For every positive i, list all i-element subsets a1 < a2 < ... ai of the set N of natural numbers 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_{d-1})$ with positive integer components, let ?f be the subset of the power set 2N 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}\leq f_{i-1}^{(i)},\quad 1\leq i\leq d-1.$ 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 Le & Römer (2019), it was discovered independently by Kruskal (1963), Katona (1968), Marcel-Paul Schützenberger (1959), Harper (1966), and Clements & Lindström (1969). Donald Knuth (2011) writes that the earliest of these references, by Schützenberger, has an incomplete proof.