= UV-compression proof of the Kruskal-Katona theorem
{c}
If a uniform family is not an initial <colexicographic> segment, choose a nontrivial $UV$-compression with $\max U<\max V$ and with $|U|$ minimal. The minimal choice supplies the smaller-compression hypotheses of the <Shadow lemma for UV-compressions>, so the operation does not increase the <lower shadow>. It strictly decreases the integer weight
$$
\sum_{A\in\mathcal A}\sum_{i\in A}2^i,
$$
because the largest element of $U\cup V$ belongs to $V$. Iteration therefore terminates. A terminal family must be an initial colexicographic segment: otherwise an earlier absent set and a later present set supply one more admissible compression. The shadow of that segment has the size in the <Kruskal-Katona theorem>, proving the theorem.
Back to article page
