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.

Comments

comments

Tagged with: , ,
Posted in Theory