Sperner theorem

Let $[ n ] : = \{ 1 , \dots , n \}$. A family $\mathcal{F}$ of subsets of $[ n ]$ that are pairwise unrelated with respect to inclusion is called a Sperner family (or Sperner system) on $[ n ]$. Examples are the families

\begin{equation*} \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) : = \{ X \subseteq [ n ] : | X | = k \} , k = 0 , \ldots , n. \end{equation*}

Since the binomial coefficients satisfy the inequalities

\begin{equation*} \left( \begin{array} { l } { n } \\ { 0 } \end{array} \right) < \ldots < \left( \begin{array} { c } { n } \\ { \lfloor n / 2 \rfloor } \end{array} \right) = \left( \begin{array} { c } { n } \\ { \lceil n / 2 \rceil } \end{array} \right) > \ldots > \left( \begin{array} { l } { n } \\ { n } \end{array} \right), \end{equation*}

in these examples $\left( \begin{array} { l } { [ n ] } \\ { n / 2 } \end{array} \right)$, if $n$ is even, and $\left( \begin{array} { c } { [ n ] } \\ { ( n - 1 ) / 2 } \end{array} \right)$ as well as $\left( \begin{array} { c } { [ n ] } \\ { ( n + 1 ) / 2 } \end{array} \right)$, if $n$ is odd, have maximum size. Sperner's theorem from 1928 states that these best examples have even maximum size among all Sperner families on $[ n ]$ and that they are the only optimal families.

Given a Sperner family $\mathcal{F}$, let $\mathcal{F} _ { k } : = \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) \cap \mathcal{F}$ and $f _ { k } : = | \cal{F} _ { k } |$. In his original proof, E. Sperner used a shifting technique: Consider the smallest $l$ with $\mathcal{F} _ { l } \neq \emptyset$ and replace $\mathcal{A} : = \mathcal{F} _ { l }$ by its upper shadow

\begin{equation*} \nabla ( \mathcal{A} ) : = \left\{ Y \in \left( \begin{array} { l } { [ n ] } \\ { l + 1 } \end{array} \right) : Y \supset X \text { for some } X\in \mathcal{A} \right\}. \end{equation*}

Double-counting easily yields $| {\cal A} | ( n - l ) \leq | \nabla ( {\cal A} ) | ( l + 1 )$ and, equivalently,

\begin{equation} \tag{a1} \frac { | \nabla ( {\cal A} ) | } { \left( \begin{array} { c } { n } \\ { l + 1 } \end{array} \right) } \geq \frac { | {\cal A} | } { \left( \begin{array} { l } { n } \\ { l } \end{array} \right) }. \end{equation}

Thus, each Sperner family can be shifted from below to the "middle" and, analogously, from above to the "middle" and thereby increasing its size.

The inequality (a1) holds for all $\mathcal{A} \subseteq \left( \begin{array} { c } { [ n ] } \\ { l } \end{array} \right)$ and all $l$, and this property is called the normalized matching property of the lattice of subsets of $[ n ]$. If $| \cal A |$ and $l$ are fixed, the best possible estimate of the upper shadow, and, dually, of the lower shadow (replace $l + 1$ by $l - 1$ and superset by subset), is given by the Kruskal–Katona theorem.

Sperner's theorem follows also easily from the inequality

\begin{equation*} \sum _ { k = 0 } ^ { n } \frac { f _ { k } } { \left( \begin{array} { l } { n } \\ { k } \end{array} \right) } \leq 1, \end{equation*}

which can be obtained by counting in two different ways the number of pairs $( X , \pi )$ where $X \in \mathcal{F}$, $\pi$ is a permutation of $[ n ]$ and $X = \{ \pi ( 1 ) , \ldots , \pi ( | X | ) \}$. This inequality was proved independently by D. Lubell, S. Yamamoto and L. Meshalkin, and is hence called the LYM inequality; a more general form of it was given by B. Bollobás.

An essential part of Sperner theory consists of the study of other partially ordered sets having analogous properties, e.g. LYM posets and Peck posets (cf. Sperner property).

Details can be found in [a1].

References

[a1]	K. Engel, "Sperner theory" , Cambridge Univ. Press (1997)
[a2]	E. Sperner, "Ein Satz über Untermengen einer endlichen Menge" Math. Z. , 27 (1928) pp. 544–548