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:

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

${\displaystyle 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 ${\displaystyle (f_{0},f_{1},...,f_{d-1})}$ is the f-vector of some ${\displaystyle (d-1)}$-dimensional simplicial complex if and only if

${\displaystyle 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 ${\displaystyle (i-r)}$-element subsets of the sets in A. Expand N as above. Then the cardinality of B is bounded below as follows:

${\displaystyle |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 ${\displaystyle (i-r)}$-element subsets of the sets in A. If ${\displaystyle |A|={\binom {x}{i}}}$ then ${\displaystyle |B|\geq {\binom {x}{i-r}}}$.

In this formulation, x need not be an integer. The value of the binomial expression is ${\displaystyle {\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

${\displaystyle 123,124,134,234,125,135,235,145,245,345,\ldots .}$

Given a vector ${\displaystyle 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 ${\displaystyle 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. ${\displaystyle 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.

## References

• Clements, G. F.; Lindström, B. (1969), "A generalization of a combinatorial theorem of Macaulay", Journal of Combinatorial Theory, 7: 230-238, doi:10.1016/S0021-9800(69)80016-5, MR 0246781. Reprinted in Gessel, Ira; Rota, Gian-Carlo, eds. (1987), Classic Papers in Combinatorics, Boston, Massachusetts: Birkhäuser Boston, Inc., pp. 416-424, doi:10.1007/978-0-8176-4842-8, ISBN 0-8176-3364-2, MR 0904286
• Harper, L. H. (1966), "Optimal numberings and isoperimetric problems on graphs", Journal of Combinatorial Theory, 1: 385-393, doi:10.1016/S0021-9800(66)80059-5, MR 0200192
• Katona, Gyula O. H. (1968), "A theorem of finite sets", in Erd?s, Paul; Katona, Gyula O. H. (eds.), Theory of Graphs, Akadémiai Kiadó and Academic Press. Reprinted in Gessel & Rota (1987, pp. 381-401).
• Knuth, Donald (2011), "7.2.1.3", The Art of Computer Programming, volume 4A: Combinatorial algorithms, part 1, p. 373.
• Kruskal, Joseph B. (1963), "The number of simplices in a complex", in Bellman, Richard E. (ed.), Mathematical Optimization Techniques, University of California Press.
• Lovász, László (1993), Combinatorial problems and exercises, Amsterdam: North-Holland.
• Le, Dinh Van; Römer, Tim (2019), A Kruskal-Katona type result and applications, arXiv:1903.02998
• Stanley, Richard (1996), Combinatorics and commutative algebra, Progress in Mathematics, 41 (2nd ed.), Boston, MA: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9.
• Schützenberger, M.P. (1959), "A Characteristic Property of Certain Polynomials of E. F. Moore and C. E. Shannon", RLE Quarterly Progress Report, 55 (Processing and Transmission of Information): 117-118, retrieved 2019.