Sperner's theorem

Statement

Let $E$ be a set with $n$ elements. Let $\mathcal{S}$ be a family of subsets of $E$ in which no set is a proper subset of another. Then $|\mathcal{S}| \le \binom{n}{\lfloor n/2 \rfloor}$. Equality holds if and only if $\mathcal{S}$ is the family of all subsets of size $\lfloor n/2 \rfloor$, or of all subsets of size $\lceil n/2 \rceil$.

Remarks

A family with this property is a Sperner family, or an antichain of sets. For each $k$, the subsets of size $k$ form an antichain. The binomial coefficient $\binom{n}{k}$ is largest for $k = \lfloor n/2 \rfloor$. Lubell gave a short proof in 1966, with the Lubell–Yamamoto–Meshalkin inequality.

History

Emanuel Sperner published the theorem in 1928.

Explanations

L1 human

You want many subsets of a set, but no one of them may contain another. The best you can do is to take all subsets of half the size.