Maths WorkshopMaths problems with full solutions
Exercise 1976Combinatorics › Binomial coefficientsOlympiadAdded 5 Nov 2026

Sperner's theorem and the LYM inequality

#antichains#double counting#chains#Sperner

Statement

A family F\mathcal F of subsets of {1,…,n}\{1,\dots,n\} is an *antichain* if no set of F\mathcal F is contained in another. Prove the LYM inequality
∑A∈F1(n∣A∣)≤1,\sum_{A\in\mathcal F}\frac1{\binom n{|A|}}\le1,
and deduce Sperner's theorem: ∣F∣≤(n⌊n/2⌋)|\mathcal F|\le\dbinom n{\lfloor n/2\rfloor}.

Hint

Count pairs (set A∈FA\in\mathcal F, maximal chain ∅=C0⊂C1⊂⋯⊂Cn={1,…,n}\emptyset=C_0\subset C_1\subset\dots\subset C_n=\{1,\dots,n\} passing through AA).

Show solutionHide solution

Solution

Idea. A maximal chain adds one element at a time, so it corresponds to a permutation; an antichain meets each chain at most once.

LYM. There are n!n! maximal chains. Each set AA of size aa lies on exactly a! (n−a)!a!\,(n-a)! of them. Since F\mathcal F is an antichain, each chain contains at most one member of F\mathcal F. Therefore
∑A∈F∣A∣! (n−∣A∣)!≤n!.\sum_{A\in\mathcal F}|A|!\,(n-|A|)!\le n!.
Dividing by n!n! gives ∑A∈F1(n∣A∣)≤1\sum_{A\in\mathcal F}\dfrac1{\binom n{|A|}}\le1.

Sperner. For every aa, (na)≤(n⌊n/2⌋)\binom na\le\binom n{\lfloor n/2\rfloor}, so
∣F∣(n⌊n/2⌋)≤∑A∈F1(n∣A∣)≤1.\frac{|\mathcal F|}{\binom n{\lfloor n/2\rfloor}}\le\sum_{A\in\mathcal F}\frac1{\binom n{|A|}}\le1.
∎

Sharpness. All subsets of size ⌊n/2⌋\lfloor n/2\rfloor form an antichain of that size.

Lesson. Double count (set, maximal chain) pairs: chains correspond to permutations and give clean factorial weights.