Sperner's theorem

Statement of the theorem

Sperner's theorem as originally stated is a result about set systems. Suppose that you want to find the largest collection of sets [math]\displaystyle{ \mathcal{A} }[/math] such that no set in [math]\displaystyle{ \mathcal{A} }[/math] is a proper subset of any other. Then the best you can do is choose all the sets of some fixed size---and of course the best size to pick is [math]\displaystyle{ \lfloor n/2\rfloor }[/math], since the binomial coefficient [math]\displaystyle{ \binom nm }[/math] is maximized when [math]\displaystyle{ m=\lfloor n/2\rfloor. }[/math]

Sperner's theorem is closely related to the density Hales-Jewett theorem: in fact, it is nothing other than DHJ(2) with the best possible bound. To see this, we associate each set [math]\displaystyle{ A\subset[n] }[/math] with its characteristic function (that is, the sequence that is 0 outside A and 1 in A). If we have a pair of sets [math]\displaystyle{ A\subset B, }[/math] then the two sequences form a combinatorial line in [math]\displaystyle{ [2]^n. }[/math] For example, if n=6 and A and B are the sets [math]\displaystyle{ \{2,3\} }[/math] and [math]\displaystyle{ \{2,3,4,6\} }[/math], then we get the combinatorial line that consists of the two points 011000 and 011101, which we can denote by 011*0* (so the wildcard set is [math]\displaystyle{ \{4,6\} }[/math]).

Proof of the theorem

There are several proofs, but perhaps the most enlightening is a very simple averaging argument that proves a stronger result. Let [math]\displaystyle{ \mathcal{A} }[/math] be a collection of subsets of [n]. For each k, let [math]\displaystyle{ \delta_k }[/math] denote the density of [math]\displaystyle{ \mathcal{A} }[/math] in the kth layer of the cube: that is, it is the number of sets in [math]\displaystyle{ \mathcal{A} }[/math] of size k, divided by [math]\displaystyle{ \binom nk. }[/math] The equal-slices measure of [math]\displaystyle{ \mathcal{A} }[/math] is defined to be [math]\displaystyle{ \delta_0+\dots+\delta_n. }[/math]

Now the equal-slices measure of [math]\displaystyle{ \mathcal{A} }[/math] is easily seen to be equal to the following quantity. Let [math]\displaystyle{ \pi }[/math] be a random permutation of [n], let [math]\displaystyle{ U_0,U_1,U_2\dots,U_n }[/math] be the sets [math]\displaystyle{ \emptyset, \{\pi(1)\},\{\pi(1),\pi(2)\},\dots,[n], }[/math] and let [math]\displaystyle{ \mu(\mathcal{A}) }[/math] be the expected number of the sets [math]\displaystyle{ U_i }[/math] that belong to [math]\displaystyle{ \mathcal{A}. }[/math] This is the same by linearity of expectation and the fact that the probability that [math]\displaystyle{ U_k }[/math] belongs to [math]\displaystyle{ \mathcal{A} }[/math] is [math]\displaystyle{ \delta_k. }[/math]

Therefore, if the equal-slices measure of [math]\displaystyle{ \mathcal{A} }[/math] is greater than 1, then the expected number of sets [math]\displaystyle{ U_k }[/math] in [math]\displaystyle{ \mathcal{A} }[/math] is greater than 1, so there must exist a permutation for which it is at least 2, and that gives us a pair of sets with one contained in the other.

To see that this implies Sperner's theorem, one just has to make the simple observation that a set with equal-slices measure at most 1 must have cardinality at most [math]\displaystyle{ \binom n{\lfloor n/2\rfloor}. }[/math] (If n is odd, so that there are two middle layers, then it is not quite so obvious that to have an extremal set you must pick one or other of the layers, but this is the case.) This stronger version of the statement is called the LYM inequality

Further remarks

The k=3 generalisation of the LYM inequality is the hyper-optimistic conjecture.

Sperner's theorem is also related to the Kruskal-Katona theorem.

• The Wikipedia entry for Sperner's theorem
• The Wikipedia entry for the LYM inequality