# Kruskal-Katona theorem

### From Polymath1Wiki

**Kruskal-Katona theorem**: If has density δ in Γ_{a,n − a}, then the upper shadow , defined as all the strings obtained from a string in A by flipping a 0 to a 1, has density at least δ in Γ_{a + 1,n − a − 1}. Similarly, the lower shadow , defined as all the strings obtained from a string in A by flipping a 1 to a 0, .

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.