# Sperner's Theorem

We know that if more than a half of subsets of an n-set **A** have been selected, there are bound to be at least two of which one contains another. This is proven with the help of the Pigeonhole Principle. Below we prove by far a stronger result - the Sperner's Theorem. It appears that a half is a few too many; there is no need to take this many subsets.

A collection **B** of nonempty subsets of a set **A** is called an *antichain* (or *clutter* or *Sperner system*) in **A** if no set in **B** is (properly) contained in another set from **B**.

Prove that, for an n-set **A**, the number of sets in any antichain in **A** cannot exceed

To remind, C(n, m) is a *binomial coefficient*

that appears in the Binomial Theorem which, for an integer exponent, can be written as

(x + y)^{n} = C(n,0)x^{n} + C(n,1)x^{n-1}y + C(n,2)x^{n-2}y^{2} + ... + C(n,n)y^{n}

For an even n, there are an odd number of binomial coefficients with the middle coefficient

At this time, I shall assume the *unimodal* behavior of the sequence of binomial coefficients:

For all 0 ≤ k ≤ n, C(n, k) ≤ C(n, n').

C(n, k) is the number of ways to select k (unordered) elements out of n. It follows that the number of sets in any antichain in which all sets have the same number of elements is bounded above by

A maximal chain in the n-set **A** is a sequence X_{0}, X_{1},... ,X_{n} of subsets of **A** such that for all i card(X_{i}), *cardinality* or the number of elements in the set X_{i}, is i; and _{i} ⊂ X_{i+1},**A** and its maximal chains: any permutation _{1} x_{2} ... x_{n}}

Ø ⊂ {x_{1}} ⊂ {x_{1}, x_{2}} ⊂ ... ⊂ {x_{1}, x_{2}, ..., x_{n}} = **A**

and vice versa. Let **B** = {B_{1},B_{2},...,B_{t}} be an antichain in **A**, with _{i}) = b_{i},**A** - maximal or not - can contain at most one of the sets B_{i}. Now, there are b_{i}! ways of
forming a chain from Ø to B_{i}, and there are _{i})!_{i} is _{i}!(n - b_{i})!.

Suppose that among the cardinalities {b_{i}} there are p_{1} 1s, p_{2} 2s, ..., p_{n} n's. So that p_{k}'s are nonnegative integers that sum up to t. The previous inequality can be rewritten as

This is known as the *Lubell-Yamamoto-Meshalkin* (LYM) inequality. From here it follows at once that

or t ≤ C(n, n').

## References

- V.K. Balakrishnan,
*Theory and Problems of Combinatorics*, Schaum's Outline Series, McGraw-Hill, 1995

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny62030624 |