Sperner Theorem on Maximal Antichains
Let \(S\) be a family of subsets of \(\{1,\ldots,n\}\) such that no set in \(S\) contains another. This is often called an antichain.
Theorem. [Sperner’s Theorem]
\[
|S| \leq {n \choose \lfloor n/2 \rfloor}.
\]
The proof of Sperner’s Theorem follows from the following lemma, which is known as LYM (Lubell–Yamamoto–Meshalkin) inequality.
Lemma. [LYM Inequality]
\[
\sum_{A\in S} \frac{1}{n \choose |A|} \leq 1.
\]
Proof. The proof follows from a double counting argument, that is, counting the number of permutations of \(\{1,\ldots,n\}\) in two ways. A direct counting gives \(n!\).
Another way is to generate permutations according to subsets in \(S\). For each \(A\in S\), we first give a permutation of the elements in \(A\), and then concatenate a permutation of elements which are not in \(A\). Each \(A\) gives \(|A|!(n-|A|)!\) permutations. By the antichain property, permutations generated from different subsets are different. Therefore, the lemma follows directly from the following:
\[
\sum_{A\in S} |A|!(n-|A|)! \leq n!.
\]▢
Sperner’s Theorem follows from LYM Inequality by the fact that \({n \choose |A|} \leq {n \choose \lfloor n/2 \rfloor}\) for all \(A\).
One can also thinks of a probabilistic argument for the LYM Inequality. Suppose we get a uniformly random permutation. For each \(A\in S\), consider the event that \(A\) is exactly the first \(|A|\) elements in the random permutation. This event happens with probability \(1 / {n\choose |A|}\). For different subsets in \(S\), such events are disjoint. This gives the LYM Inequality.