Kruskal-Katona theorem

cosmos 30th October 2017 at 9:39pm

Let F[n](r)\mathcal{F} \subseteq [n]^{(r)} (the rrth layer of the Power set on [n][n]) and let A\mathcal{A} be the family consisting of the first F|\mathcal{F}| elements of [n](r)[n]^{(r)} in colex order. Then FA|\partial \mathcal{F}| \geq |\partial \mathcal{A}|, where \partial represents the Shadow set.

lecture note

This means that

shadows are minimized by taking initial segments of colex

Families of sets corresponding to initial segments of colex minimize the size of their shadows