This is about the only proof I can come up with for Sperner's theorem (which see). It's an interesting question whether other, structurally different, proofs exist. In particular, a truly probabilistic proof (not just rephrasing the counting argument below in terms of probability) would be desirable (to me, at least).


Suppose we have some antichain F on {1,...,n}. Consider all ordered permutations a1,an∈{1,...,n} (that is, all orderings of the numbers 1,...,n). There are n! such orderings. Now, the sequence of sets

{a1} ⊆ {a1,a2} ⊆ ... ⊆ {a1,a2,...,an}
contains at most one element of F (otherwise F is no antichain).

Suppose f∈F has k elements. Then there are exactly k!(n-k)! orderings that intersect f. So, if ck is the number of elements of F with k elements, by intersections of orderings we have that

k=0n ck⋅k!(n-k)! ≤ n!
Now, we're interested in just ∑ck = |F| (the number of elements of F). But for all k we have that
k!(n-k)! ≥ ⌊n/2⌋!⌈n/2⌉! = m(n)
(this is just the claim that the largest binomial coefficient is the central one). So,
|F|⋅m(n) = k=0n ck⋅m(n) ≤ k=0n ck⋅k!(n-k)! ≤ n!,
or, in other words, |F| is not larger than the central binomial coefficient.


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