# Kruskal-Katona theorem

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

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.