---
tag: 57DD99JPR1
kind: proof
name: Proof of Sperner's theorem by Lubell's chain counting
msc: [05D05]
proves: 0J87V9K1GE
uses: [092GEF38YD, 033KTKKRV6, 0BFMR2FQ8B, 0CEBCS0E0E, 0F8YBHF2W3]
sources:
  - url: https://kam.mff.cuni.cz/~chvatal/est.pdf
  - url: https://en.wikipedia.org/wiki/Sperner's_theorem
    locator: Proof
---

## Proof

We count pairs of a full chain and a member of $\mathcal{S}$ on it (Lubell's method). Then we examine when equality holds.

*Setup.*

1. Let $E$ be a set with $n$ elements and let $m = \floor{n/2}$. Let $\mathcal{S}$ be a family of subsets of $E$ in which no set is a proper subset of another. Write $\binom{n}{k}$ for the [[binomial coefficient|092GEF38YD]].
2. A *listing* of $E$ is a sequence $(x_1, \dots, x_n)$ in which each element of $E$ appears exactly once. There are $n!$ listings, by the [[number of permutations|0CEBCS0E0E]].
3. A listing $\sigma = (x_1, \dots, x_n)$ has the *chain* $C_\sigma = \set{\set{x_1, \dots, x_k} : 0 \le k \le n}$. It has exactly one set of each size $k$, namely its first $k$ elements.

*The binomial coefficients.*

4. By the [[factorial formula|033KTKKRV6]], $\binom{n}{k+1} \big/ \binom{n}{k} = (n-k)/(k+1)$ for $0 \le k < n$. This ratio is greater than $1$ when $2k < n - 1$, equal to $1$ when $2k = n - 1$, and less than $1$ when $2k > n - 1$.
5. So $\binom{n}{k}$ strictly increases for $0 \le k \le \floor{n/2}$, strictly decreases for $\ceil{n/2} \le k \le n$, and $\binom{n}{\floor{n/2}} = \binom{n}{\ceil{n/2}}$.
6. Hence $\binom{n}{k} \le \binom{n}{m}$ for all $0 \le k \le n$, with equality exactly when $k \in \set{\floor{n/2}, \ceil{n/2}}$.

*The LYM inequality.*

7. Let $A \subseteq E$ with $\abs{A} = k$. Then $A \in C_\sigma$ exactly when the first $k$ entries of $\sigma$ list $A$ and the others list $E \setminus A$. By Step 2, there are $k!\,(n-k)!$ such listings.
8. Each chain $C_\sigma$ contains at most one member of $\mathcal{S}$. Indeed, of two distinct sets of $C_\sigma$, one is a proper subset of the other.
9. [[Double count|0F8YBHF2W3]] the pairs $(\sigma, A)$ with $A \in \mathcal{S} \cap C_\sigma$. By Step 7 there are $\sum_{A \in \mathcal{S}} \abs{A}!\,(n - \abs{A})!$ pairs. By Step 8 there are at most $n!$ of them.
10. Divide by $n!$ and use the factorial formula: $\sum_{A \in \mathcal{S}} 1 \big/ \binom{n}{\abs{A}} \le 1$.

*The bound.*

11. By Step 6, each term satisfies $1 \big/ \binom{n}{\abs{A}} \ge 1 \big/ \binom{n}{m}$. So $\abs{\mathcal{S}} \big/ \binom{n}{m} \le \sum_{A \in \mathcal{S}} 1 \big/ \binom{n}{\abs{A}} \le 1$.
12. Hence $\abs{\mathcal{S}} \le \binom{n}{m}$.

*The two extremal families attain the bound.*

13. Let $k \in \set{\floor{n/2}, \ceil{n/2}}$, and let $\mathcal{L}_k$ be the family of all subsets of $E$ of size $k$. Two distinct sets of the same size are not proper subsets of each other. So $\mathcal{L}_k$ has the property of $\mathcal{S}$.
14. By the [[number of $k$-element subsets|0BFMR2FQ8B]] and Step 5, $\abs{\mathcal{L}_k} = \binom{n}{k} = \binom{n}{m}$.

*Equality forces an extremal family.*

15. Suppose now $\abs{\mathcal{S}} = \binom{n}{m}$. Then both inequalities of Step 11 are equalities.
16. The first equality and Step 6 show that every $A \in \mathcal{S}$ has $\abs{A} \in \set{\floor{n/2}, \ceil{n/2}}$.
17. The second equality means that the count of Step 9 is exactly $n!$. By Step 8, every chain $C_\sigma$ contains exactly one member of $\mathcal{S}$.
18. If $n$ is even, every member of $\mathcal{S}$ has size $n/2$. So $\mathcal{S} \subseteq \mathcal{L}_{n/2}$, and both have $\binom{n}{m}$ elements by Step 14. Hence $\mathcal{S} = \mathcal{L}_{n/2}$.
19. Let $n$ be odd. Since $\binom{n}{m} \ge 1$, the family $\mathcal{S}$ has a member $A$. Let $k = \abs{A}$, so $k \in \set{m, m+1}$.
20. *Swap step.* Let $A \in \mathcal{S}$ with $\abs{A} = k$. Let $A' = (A \setminus \set{x}) \cup \set{y}$ with $x \in A$ and $y \notin A$, and put $D = A \setminus \set{x}$. We show $A' \in \mathcal{S}$.
21. If $k = m$, choose a listing that starts with the elements of $D$, then $y$, then $x$. Its chain contains $A' = D \cup \set{y}$, of size $m$, and $B = D \cup \set{x, y}$, of size $m + 1$.
22. By Steps 16 and 17, exactly one of $A'$ and $B$ lies in $\mathcal{S}$. But $A \subsetneq B$ and $A \in \mathcal{S}$, so $B \notin \mathcal{S}$. Hence $A' \in \mathcal{S}$.
23. If $k = m + 1$, choose a listing that starts with the elements of $D$, then $y$. Its chain contains $D$, of size $m$, and $A' = D \cup \set{y}$, of size $m + 1$.
24. Exactly one of them lies in $\mathcal{S}$. But $D \subsetneq A$ and $A \in \mathcal{S}$, so $D \notin \mathcal{S}$. Hence $A' \in \mathcal{S}$.
25. Let $A''$ be any subset of $E$ of size $k$, and let $t = \abs{A \setminus A''}$. Replacing elements one at a time, we get sets $A = A_0, A_1, \dots, A_t = A''$ of size $k$, each obtained from the previous one as in Step 20.
26. By Step 20 and induction on $t$, $A'' \in \mathcal{S}$. So $\mathcal{L}_k \subseteq \mathcal{S}$.
27. By Step 14, $\abs{\mathcal{L}_k} = \binom{n}{m} = \abs{\mathcal{S}}$. Hence $\mathcal{S} = \mathcal{L}_k$, the family of all subsets of size $\floor{n/2}$ or of all subsets of size $\ceil{n/2}$.
28. By Steps 13, 14 and 15 to 27, equality holds exactly for these families.

## Idea

A random ordering of $E$ builds a chain of $n+1$ nested sets, and an antichain can meet it at most once. A set of size $k$ lies on a fraction $1/\binom{n}{k}$ of these chains, so these fractions add up to at most $1$. For equality, every chain must meet the family at a middle size, and a swapping argument then fills a whole middle level.