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 Ck,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} is
C⌊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.

Log in or register to write something here or to contact authors.