Kruskal-Katona theorem

Let $[ n ] : = \{ 1 , \dots , n \}$ and $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) : = \{ X \subseteq [ n ] : | X | = k \}$, $k = 0 , \dots , n$ (cf. also Sperner property; Sperner theorem). The elements of $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ can be linearly ordered in the following way: $X < Y$ if the largest element in which $X$ and $Y$ differ is in $Y$ (cf. also Totally ordered set). If $\{ a _ { 1 } + 1 , \dots , a _ { k } + 1 \}$, $0 \leq a _ { 1 } < \ldots < a _ { k } \leq n - 1$, is the $( m + 1 )$th element in this order, then

\begin{equation} \tag{a1} m = \left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right) + \left( \begin{array} { c } { a _ { k - 1} } \\ { k - 1 } \end{array} \right) + \ldots + \left( \begin{array} { c } { a _ { 2 } } \\ { 2 } \end{array} \right) + \left( \begin{array} { c } { a _ { 1 } } \\ { 1 } \end{array} \right), \end{equation}

since $\left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right)$ $k$-element subsets of $[ n ]$ have maximal element smaller than $a _ { k } + 1$, $\left( \begin{array} { c } { a _ { k - 1 } } \\ { k - 1 } \end{array} \right)$ have maximal element $a _ { k } + 1$ but the second largest element smaller than $a _ { k - 1} + 1$, etc.. Equation (a1) is called the $k$-representation of $m$, $1 \leq m \leq \left( \begin{array} { l } { n } \\ { k } \end{array} \right)$ (for $m = \left( \begin{array} { l } { n } \\ { k } \end{array} \right)$, one takes $a _ { 1 } = 0$, $a _ { 2 } = 1 , \dots , a _ { k - 1 } = k - 2$, $a _ { k } = n$). This (unique) representation can be found directly by choosing $a_k$ maximal such that $\left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right) \leq m$, $a_{k - 1}$ maximal such that $\left( \begin{array} { c } { a _ { k - 1 } } \\ { k - 1 } \end{array} \right) \leq m - \left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right)$, etc..

For a family ${\cal F} \subseteq \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$, the lower shadow of $\mathcal{F}$ is defined by

\begin{equation*} \Delta ( \mathcal{F} ) : = \left\{ Y \in \left( \begin{array} { c } { [ n ] } \\ { k - 1 } \end{array} \right) : Y \subset X \text { for some } X \in \mathcal{F} \right\}. \end{equation*}

If $m$ is given as above, then the lower shadow of the family of the first $m$ elements in $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ is the family of all $( k - 1 )$-element subsets of $[ n ]$ having maximal element smaller than $a _ { k } + 1$, of all $( k - 1 )$-element subsets of $[ n ]$ having maximal element $a _ { k } + 1$, but the second largest element smaller than $a _ { k - 1} + 1$, etc., i.e. the family of the first $\partial _ { k } ( m )$ elements of $\left( \begin{array} { c } { [ n ] } \\ { k - 1 } \end{array} \right)$ where

\begin{equation*} \partial _ { k } ( m ) = \left( \begin{array} { c } { a _ { k } } \\ { k - 1 } \end{array} \right) + \left( \begin{array} { c } { a _ { k } - 1 } \\ { k - 2 } \end{array} \right) + \ldots + \left( \begin{array} { c } { a _ { 1 } } \\ { 0 } \end{array} \right). \end{equation*}

The Kruskal–Katona theorem states that in this way one obtains a lower shadow of minimum size, i.e., if $\mathcal{F}$ is any $m$-element family in $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ and $m$ is given by (a1), then

\begin{equation*} \Delta ( {\cal F} ) | \geq \partial _ { k } ( m ). \end{equation*}

There exist generalizations to similar results for other partially ordered sets, like products of chains, products of stars, the partially ordered set of subwords of $0$-$1$-words, and the partially ordered set of submatrices of a matrix.

The following result of L. Lovász is weaker but numerically easier to handle: If ${\cal F} \subseteq \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ and $| \mathcal F | = \left( \begin{array} { l } { x } \\ { k } \end{array} \right)$ with some real $x$, where $k \leq x \leq n$, then

\begin{equation*} | \Delta ( \mathcal{F} ) | \geq \left( \begin{array} { c } { x } \\ { k - 1 } \end{array} \right). \end{equation*}

The original papers by J.B. Kruskal and G.O.H. Katona are [a3], [a4].

According to [a2], p. 1296, the Kruskal–Katona theorem is probably the most important one in finite extremal set theory.

References

[a1]	K. Engel, "Sperner theory" , Encyclopedia of Mathematics and its Applications 65, Cambridge Univ. Press (1997) ISBN 0-521-45206-6 Zbl 0868.05001
[a2]	P. Frankl, "Extremal set systems" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , 2 , Elsevier (1995) pp. 1293–1329
[a3]	J.B. Kruskal, "The number of simplices in a complex" , Mathematical Optimization Techniques , Univ. California Press (1963) pp. 251–278. Zbl 0116.35102
[a4]	G.O.H. Katona, "A theorem of finite sets" , Theory of Graphs. Proc. Colloq. Tihany , Akad. Kiadó (1966) pp. 187–207