Kruskal–Katona theorem

The Kruskal–Katona theorem is a combinatorial theorem about uniform hypergraphs. It can be used to derive facts about abstract simplicial complexes. It is named for Joseph Kruskal and Gyula O. H. Katona.

For an "n"-element set "X", define the "shadow" $partial\; X$ as the family of $(n-1)$-element subsets of "X", and for a family "A" of "n"-element subsets of a universe "U" (i.e., an "n"-hypergraph), define the shadow as the union of the shadows of the constituent sets,

: .

The Kruskal–Katona theorem states that the size of $partial\; A$ is minimized when "A" consists of the $|A|$ co-lexicographically first subsets of size n of "U". Denoting $m=|A|$, and the m+1'th element of the colexicographical order as $\{\; m\_1\; +\; 1,\; m\_2\; +\; 1,\; ...\; m\_n+1\}$, we have

: $m\; =\; \{m\_n\; choose\; n\}\; +\; \{m\_\{n-1\}\; choose\; n-1\}\; +\; ...\; +\; \{m\_\{u\}\; choose\; u\}$,

where $m\_n>m\_\{n-1\}>dots>m\_\{u\}ge\; uge\; 1$, u being the first integer for which $m\_u\; ge\; u$, and thus

: $|partial\; A|\; ge\; \{m\_n\; choose\; n-1\}\; +\; \{m\_\{n-1\}\; choose\; n-2\}\; +\; ...\; +\; \{m\_\{u\}\; choose\; u-1\}$,

with equality if (but not, in general, only if) "A" consists of the "m" co-lexicographically first subsets of "U". Symmetrically, if we define the "upward shadow" $partial\_u\; X$ as the family of $(n+1)$-element supersets of "X", we have that $|partial\_u\; A|$ is minimal when "A" consists of the "m" co-lexicographically last subsets of "U".

References

* J.B. Kruskal: The number of simplices in a complex, "Mathematical Optimization Techniques", R. Bellman (ed.), University of California Press, 1963.
* G.O.H. Katona: A theorem of finite sets, "Theory of Graphs", P. Erdős and G. Katona (eds.), Akadémiai Kiadó and Academic Press, 1968.
* D. Knuth: The Art of Computer Programming, [http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz pre-fascicle 3a: Generating all combinations] , pp. 18–. "Contains a proof via a more general theorem in discrete geometry."