Sperner Theorem

Sperner's theorem determines the maximum size of an antichain in the Boolean lattice—a family of subsets of $[n]$ with no set containing another. This elegant result has numerous proofs and generalizations, making it a central theorem in extremal set theory.

TheoremSperner's Theorem

The maximum size of an antichain in $\mathcal{P}([n])$ (the Boolean lattice $B_n$ ) is $\binom{n}{\lfloor n/2 \rfloor}$ . This maximum is achieved by taking all subsets of size $\lfloor n/2 \rfloor$ (or $\lceil n/2 \rceil$ ).

ProofCounting Chains

Count pairs $(C, A)$ where $C$ is a maximal chain and $A \in \mathcal{F}$ with $A \in C$ , for an antichain $\mathcal{F}$ .

Total maximal chains: $n!$ (permutations determining chains $\emptyset \subset \{a_1\} \subset \{a_1,a_2\} \subset \cdots$ )
Each chain contains at most one element of $\mathcal{F}$ (antichain property)
Thus: $\sum_{A \in \mathcal{F}} (\text{chains through } A) \leq n!$

For $|A| = k$ , the number of chains through $A$ is $k! \cdot (n-k)!$ (order elements before/after $A$ ).

$\sum_{A \in \mathcal{F}} k! \cdot (n-k)! \leq n! \implies \sum_{A \in \mathcal{F}} \frac{1}{\binom{n}{|A|}} \leq 1$

For $\mathcal{F}$ to be an antichain with all sets of same size $k$ : $|\mathcal{F}| \cdot \frac{1}{\binom{n}{k}} \leq 1 \implies |\mathcal{F}| \leq \binom{n}{k}$

Maximum is $\binom{n}{\lfloor n/2 \rfloor}$ since binomial coefficients are maximized at the middle.

■

ExampleSperner Family

For $n = 4$ :

Maximum antichain size is $\binom{4}{2} = 6$
Example: $\{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}\}$
No subset contains another in this family

Remark

LYM Inequality (Lubell-Yamamoto-Meshalkin): For any antichain $\mathcal{F}$ in $B_n$ : $\sum_{A \in \mathcal{F}} \frac{1}{\binom{n}{|A|}} \leq 1$

This refined inequality directly implies Sperner's theorem and extends to many generalizations.

Sperner's theorem initiated extremal set theory and remains fundamental in combinatorial optimization and theoretical computer science.