Sperner's Theorem

The largest antichain in the Boolean lattice is the middle layer.

The idea

Theorem (Sperner's theorem).

Among all families of subsets of an $n$-element set in which no member contains another, the largest possible family has exactly $\binom{n}{\lfloor n/2 \rfloor}$ members.

A family with this no-containment property is an antichain for the containment order. Containment orders subsets only partially — $\{1,2\}$ and $\{2,3\}$ contain neither one another — so an antichain has room to be large, and the theorem determines how large.

One antichain of the stated size is immediate. Take every subset of a single fixed size $k$: two distinct sets of the same size cannot contain one another, and this layer is largest when $k = \lfloor n/2 \rfloor$, where the binomial coefficients peak. Sperner's theorem asserts that no family, even one mixing sizes, exceeds this middle layer.

Ways to work on it

• Walkthrough. How large a family of subsets can be if none contains another, and the chain-counting argument that bounds it.
• Practice. Evaluate the maximum antichain size for a small n.
• Hardest. Bound the size of an antichain whose sets come in two different sizes.

Not sure where to start? Take the ten-question placement test.