LYM inequality

Remarks

A maximal chain $\emptyset \subset \set{a_1} \subset \set{a_1, a_2} \subset \cdots \subset [n]$ corresponds to an ordering $a_1, \ldots, a_n$ of $[n]$, so there are $n!$ of them. A set $A$ with $|A| = k$ lies on exactly $k! (n - k)!$ maximal chains. A chain meets an antichain at most once, so $\sum_{A \in \mathcal{F}} |A|! (n - |A|)! \le n!$, and division by $n!$ gives the inequality.

Since $\binom{n}{k} \le \binom{n}{\floor{n/2}}$ for all $k$, the inequality gives $|\mathcal{F}| \le \binom{n}{\floor{n/2}}$, which is Sperner's theorem. Equality holds for the family of all $k$-subsets of $[n]$, for any $k$. Without the antichain hypothesis the sum can exceed $1$: for $\mathcal{F} = \set{\emptyset, [n]}$ it equals $2$.

Going deeper

For a student

The LYM inequality is the strong form of Sperner's theorem, and its chain-counting proof is a model double-counting argument. It extends to posets with a suitable chain structure, called LYM posets. It is also used, through the same idea of averaging over orderings, in Katona's proof of the Erdős–Ko–Rado theorem. The Kruskal–Katona theorem gives the exact minimum size of the shadow of a family of sets of one size.