Kruskal-Katona theorem

From Polymath1Wiki
Jump to: navigation, search

Kruskal-Katona theorem: If [math]A \subset \Gamma_{a,n-a} \subset [2]^n[/math] has density [math]\delta[/math] in [math]\Gamma_{a,n-a}[/math], then the upper shadow [math]\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]\delta[/math] in [math]\Gamma_{a+1,n-a-1}[/math]. Similarly, the lower shadow [math]\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]\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.