# Sperner's theorem

### From Polymath1Wiki

## Contents |

## 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 such that no set in 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 , since the binomial coefficient is maximized when

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 with its characteristic function (that is, the sequence that is 0 outside A and 1 in A). If we have a pair of sets then the two sequences form a combinatorial line in [2]^{n}. For example, if n=6 and A and B are the sets {2,3} and {2,3,4,6}, 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 {4,6}).

## 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 be a collection of subsets of [n]. For each k, let δ_{k} denote the density of in the kth layer of the cube: that is, it is the number of sets in of size k, divided by The equal-slices measure of is defined to be

Now the equal-slices measure of is easily seen to be equal to the following quantity. Let π be a random permutation of [n], let be the sets and let be the expected number of the sets *U*_{i} that belong to This is the same by linearity of expectation and the fact that the probability that *U*_{k} belongs to is δ_{k}.

Therefore, if the equal-slices measure of is greater than 1, then the expected number of sets *U*_{k} in 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 (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*

### Strong version

An alternative argument deduces the multidimensional Sperner theorem from the density Hales-Jewett theorem. We can think of [2]^{n} as [2^{k}]^{n / k}. If we do so and apply DHJ(2^k) and translate back to [2]^{n}, then we find that we have produced a k-dimensional combinatorial subspace. This is obviously a much more sophisticated proof, since DHJ(2^k) is a very hard result, but it gives more information, since the wildcard sets turn out to have the same size. A sign that this strong version is genuinely strong is that it implies Szemerédi's theorem. For instance, suppose you take as your set the set of all sequences such that the number of 0s plus the number of 1s in even places plus twice the number of 1s in odd places belongs to some dense set in [3*n*]. Then if you have a 2D subspace with both wildcard sets of size d, one wildcard set consisting of odd numbers and the other of even numbers (which this proof gives), then this implies that in your dense set of integers you can find four integers of the form a, a+d, a+2d, a+d+2d, which is an arithmetic progression of length 4.

One can also prove the above strong form of Sperner theorem by using the multidimensional Szemerédi theorem which has combinatorial proofs. (reference!) It states that large dense high dimensional grids contain corners. Given a dense subset of [2]^{n}, denoted by . We can suppose that the elements of are of size about Take a random permutation of [n]. An element of is “*d* − nice” after the permutation if it consists of *d* intervals, each of length between and each interval begins at position *i**d* for some (Suppose that *d* divides *n*) Any *d* − nice set can be represented as a point in a *d* − dimensional cube. The sets represented by the vertices of an axis-parallel *d* − dimensional cube in form a subspace with equal sized wildcard sets. Finding a cube is clearly more difficult than finding a corner, but it's existence in dense sets also follows from the multidimensional Szemerédi theorem. All what we need is to show that the expected number of the *d* − nice elements is where c only depends on the density of . For a typical *m* − element subset of the probability that it is *d* − nice after the permutation is about The sum for elements of with size between gives that the expected number of the *d* − nice elements is so there is a cube if n is large enough.

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