Kruskal-Katona theorem

From Polymath1Wiki

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.

Personal tools