UV-compression proof of the Kruskal-Katona theorem

ID: uv-compression-proof-of-the-kruskal-katona-theorem

If a uniform family is not an initial colexicographic segment, choose a nontrivial -compression with and with 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
because the largest element of belongs to . 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.

New to topics? Read the docs here!