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.
Articles by others on the same topic
There are currently no matching articles.