Kruskal-Katona theorem
From Polymath1Wiki
Kruskal-Katona theorem: If ![A \subset \Gamma_{a,n-a} \subset [2]^n](/polymath1/images/math/3/b/6/3b636763ba6cf19ece4af94bdb6ff4c7.png)
has density δ in Γa,n − a, then the upper shadow ![\partial^+ A \subset \Gamma_{a+1,n-a-1} \subset [2]^n](/polymath1/images/math/3/6/6/366b894b473c34193421c1a7ff523d85.png)
, 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 ![\partial^- A \subset \Gamma_{a-1,n-a+1} \subset [2]^n](/polymath1/images/math/e/e/6/ee61b3b348c5381511b63ea89b0d58cf.png)
, 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](/polymath1/images/math/5/7/c/57c498f2ddbe9bcf75370ae3f07b2021.png)
.
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.
