|
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.
| 
