---
tag: 0J87V9K1GE
kind: statement
role: theorem
name: Sperner's theorem
msc: [05D05]
uses: [092GEF38YD]
sources:
  - url: https://en.wikipedia.org/wiki/Sperner's_theorem
    locator: Statement
same_as:
  wikidata: Q2226786
  wikipedia: 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|092GEF38YD]] $\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.