Proof of Sperner's Theorem via LYM Inequality

Sperner's theorem asserts that the largest antichain in $2^{[n]}$ has size $\binom{n}{\lfloor n/2 \rfloor}$ . We prove this using the Lubell-Yamamoto-Meshalkin (LYM) inequality, which is a far-reaching tool in extremal set theory.

The LYM Inequality

Theorem4.5LYM Inequality

Let $\mathcal{F} \subseteq 2^{[n]}$ be an antichain. Then $\sum_{F \in \mathcal{F}} \frac{1}{\binom{n}{|F|}} \leq 1.$

Proof

Consider a uniformly random permutation $\sigma$ of $[n]$ . For each $k \in \{0, 1, \ldots, n\}$ , define the initial segment $I_k(\sigma) = \{\sigma(1), \sigma(2), \ldots, \sigma(k)\}$ .

For any fixed set $F \in \mathcal{F}$ with $|F| = k$ , the probability that $F = I_k(\sigma)$ is $\Pr[I_k(\sigma) = F] = \frac{k!(n-k)!}{n!} = \frac{1}{\binom{n}{k}}.$

Since $\mathcal{F}$ is an antichain, at most one set in $\mathcal{F}$ can appear as an initial segment of $\sigma$ . Indeed, if $F, G \in \mathcal{F}$ with $|F| < |G|$ and $F = I_{|F|}(\sigma)$ , $G = I_{|G|}(\sigma)$ , then $F \subseteq G$ , contradicting the antichain property.

Therefore, the events $\{I_{|F|}(\sigma) = F\}$ for $F \in \mathcal{F}$ are mutually exclusive. By the union bound (which is tight here): $1 \geq \sum_{F \in \mathcal{F}} \Pr[I_{|F|}(\sigma) = F] = \sum_{F \in \mathcal{F}} \frac{1}{\binom{n}{|F|}}.$

This completes the proof of the LYM inequality. $\square$

■

Deriving Sperner's Theorem

Theorem4.6Sperner's Theorem

The maximum size of an antichain in $2^{[n]}$ is $\binom{n}{\lfloor n/2 \rfloor}$ .

Proof

Let $\mathcal{F}$ be an antichain in $2^{[n]}$ . By the LYM inequality, $\sum_{F \in \mathcal{F}} \frac{1}{\binom{n}{|F|}} \leq 1.$

Since $\binom{n}{k} \leq \binom{n}{\lfloor n/2 \rfloor}$ for all $0 \leq k \leq n$ , we have $\frac{1}{\binom{n}{|F|}} \geq \frac{1}{\binom{n}{\lfloor n/2 \rfloor}}$ for each $F$ . Therefore, $\frac{|\mathcal{F}|}{\binom{n}{\lfloor n/2 \rfloor}} \leq \sum_{F \in \mathcal{F}} \frac{1}{\binom{n}{|F|}} \leq 1,$ which gives $|\mathcal{F}| \leq \binom{n}{\lfloor n/2 \rfloor}$ .

Equality is achieved by taking all subsets of size $\lfloor n/2 \rfloor$ , confirming that the bound is tight. $\square$

■

RemarkBollobás Set-Pairs Inequality

The LYM inequality can be generalized to the Bollobás set-pairs inequality: if $(A_i, B_i)_{i=1}^m$ are pairs with $A_i \cap B_j = \emptyset$ if and only if $i = j$ , then $\sum_{i=1}^m \binom{|A_i| + |B_i|}{|A_i|}^{-1} \leq 1$ . This powerful generalization has applications in information theory and topology.

ExampleWidth of Boolean Lattice

The width of the Boolean lattice $2^{[n]}$ (maximum antichain size) is $\binom{n}{\lfloor n/2 \rfloor}$ , while the height (maximum chain length) is $n + 1$ . By Dilworth's theorem, $2^{[n]}$ can be partitioned into $\binom{n}{\lfloor n/2 \rfloor}$ chains, which yields a symmetric chain decomposition.