Combinatorics Extremal combinatorics Theorem

Kruskal–Katona theorem

Builds on Family of sets Binomial coefficient

Statement

Let $k \ge 1$ be an integer. For a family $\mathcal{F}$ of $k$ -element sets, the shadow $\partial \mathcal{F}$ is the family of all $(k-1)$ -element sets that are contained in some member of $\mathcal{F}$ . Every positive integer $m$ can be written in exactly one way as $m = \binom{a_k}{k} + \binom{a_{k-1}}{k-1} + \cdots + \binom{a_t}{t}$ with integers $a_k > a_{k-1} > \cdots > a_t \ge t \ge 1$ . If $\mathcal{F}$ is a family of $m$ sets of size $k$ , then $|\partial \mathcal{F}| \ge \binom{a_k}{k-1} + \binom{a_{k-1}}{k-2} + \cdots + \binom{a_t}{t-1}.$

Remarks

The bound is attained by the first $m$ sets of size $k$ of positive integers in the colexicographic order. In this order, $A$ comes before $B$ when the largest element of $A \mathbin{\triangle} B$ lies in $B$ . The proof shows, with compression operators, that one may assume $\mathcal{F}$ is an initial segment of this order, and then counts.

Example: let $k = 2$ and $m = 3$ , so $m = \binom{3}{2}$ and the bound is $\binom{3}{1} = 3$ . A graph with $3$ edges, seen as a family of $2$ -sets, covers at least $3$ vertices, and the triangle covers exactly $3$ .

A simpler form due to Lovász: if $|\mathcal{F}| = \binom{x}{k}$ for a real number $x \ge k$ , then $|\partial \mathcal{F}| \ge \binom{x}{k-1}$ , where $\binom{x}{j} = x(x-1)\cdots(x-j+1)/j!$ .

Going deeper

For a student

The theorem characterises the possible $f$ -vectors of simplicial complexes, since the faces of a complex form a family closed under taking shadows. It implies the Erdős–Ko–Rado theorem. Its numerical form, through the $k$ -binomial representation of $m$ , reappears in Macaulay's theorem on Hilbert functions and in the g-theorem for polytopes.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`G6WNYB0WMY`
URI	`m2://G6WNYB0WMY`
Kind	statement, theorem
Writing	W0 stub
MSC	05D05
Status	This copy of the site has no build data. Run `m2 status G6WNYB0WMY`.
About	Family of sets
Uses	Family of sets, Binomial coefficient
Same as	Wikidata Q3527102 Wikipedia Kruskal–Katona theorem
Changed	2 November 2026