# Kruskal-Katona theorem

Jump to: navigation, search

Kruskal-Katona theorem: If $A \subset \Gamma_{a,n-a} \subset [2]^n$ has density δ in Γa,na, 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 δ in Γa + 1,na − 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.