Sperner family
|
|
In combinatorics, a Sperner family (or Sperner system), named in honor of Emanuel Sperner, is a set system (F, E) in which no element is contained in another. Formally,
- If X, Y are in F and X ≠ Y, then X is not contained in Y and Y is not contained in X.
Equivalently, a Sperner family is an antichain in the inclusion lattice over the power set of E. A Sperner family is also sometimes called an independent system.
| Contents |
Sperner's theorem
One interesting and useful result is the following, known as Sperner's theorem.
For every Sperner family S over an n-set,
- <math>|S| \le {n \choose \lfloor{n/2}\rfloor}.<math>
Proof
The following proof is due to Lubell. (see reference). Let sk denote the number of k-sets in S. For all 0 ≤ k ≤ n,
- <math>{n \choose \lfloor{n/2}\rfloor} \ge {n \choose k}<math>
and, thus,
- <math>{s_k \over {n \choose \lfloor{n/2}\rfloor}} \le {s_k \over {n \choose k}}.<math>
Since S is an antichain, we can sum over the above inequality from k = 0 to n and then apply the LYM inequality to obtain
- <math>\sum_{k=0}^n{s_k \over {n \choose \lfloor{n/2}\rfloor}} \le \sum_{k=0}^n{s_k \over {n \choose k}} \le 1,<math>
which means
- <math> |S| = \sum_{k=0}^n s_k \le {n \choose \lfloor{n/2}\rfloor}<math>.
This completes the proof.
Sperner's theorem can be seen as a special case of Dilworth's theorem. It is sometimes called Sperner's lemma, but unfortunately, this name also refers to another result on coloring. To differentiate the two results, the above is more commonly known as simply Sperner's theorem nowadays.
References
Lubell, D. (1966). A short proof of Sperner's theorem, J. Combin. Theory 1, 299.
External links
- Sperner's Theorem (http://www.cut-the-knot.org/pigeonhole/sperner.shtml)