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 weightbecause 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!