# Sperner's theorem

### (Combinatorics, finite set theory:)

Sperner's theorem is an important example of extremal problems in finite combinatorics. It establishes a bound on the largest possible size of a (hopefully interesting) configuration.

What is the size of the largest possible antichain on {1,2,...,n}?
As the antichain writeup shows, the set of all subsets of size k
is an antichain. The size of this antichain
is **C**_{k,n}=n!/(k!⋅(n-k)!). The
largest such antichain (for even n) is attained when k=n/2. It
turns out that this is, in fact, the largest *possible*
antichain.

Theorem.The size of the largest possible antichain on {1,2,...,n} isC_{⌊n/2⌋,n}= n!/(⌊n/2⌋!⋅⌈n/2⌉!)

Proofs of Sperner's theorem also show that the bound is
attained *only* with a family of subsets -- of size k if n=2k
is even, or of size k or k+1 if n=2k+1 is odd.