# 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.