Kruskal-Katona theorem

Kruskal-Katona theorem: If [math]\displaystyle{ A \subset \Gamma_{a,n-a} \subset [2]^n }[/math] has density [math]\displaystyle{ \delta }[/math] in [math]\displaystyle{ \Gamma_{a,n-a} }[/math], then the upper shadow [math]\displaystyle{ \partial^+ A \subset \Gamma_{a+1,n-a-1} \subset [2]^n }[/math], defined as all the strings obtained from a string in A by flipping a 0 to a 1, has density at least [math]\displaystyle{ \delta }[/math] in [math]\displaystyle{ \Gamma_{a+1,n-a-1} }[/math]. Similarly, the lower shadow [math]\displaystyle{ \partial^- A \subset \Gamma_{a-1,n-a+1} \subset [2]^n }[/math], defined as all the strings obtained from a string in A by flipping a 1 to a 0, [math]\displaystyle{ \partial^+ A \subset \Gamma_{a-1,n-a+1} \subset [2]^n }[/math].

A more precise statement can be found at the Wikipedia entry on this theorem.

It can be used to prove a variant of Sperner's theorem.