Proof of Sperner's theorem by Lubell's chain counting

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.
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.
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, $\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 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 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.