Sperner family
From Wikipedia, the free encyclopedia
 |
It has been suggested that clutter (mathematics) be merged into this article or section. (Discuss) |
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 |
[edit] Sperner's theorem
The k-subsets of an n-set forms a Sperner family, the size of which is maximized when k = n/2. Sperner's theorem (a special case of Dilworth's theorem) states that these families are the largest possible Sperner families over an n-set. Formally, the theorem states that, for every Sperner family S over an n-set,
It is sometimes called Sperner's lemma, but unfortunately, that name also refers to another result on coloring. To differentiate the two results, the result on the size of a Sperner family is now more commonly known as Sperner's theorem.
[edit] 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,
and, thus,
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
which means
.
This completes the proof.
[edit] References
- Lubell, D. (1966). A short proof of Sperner's theorem, J. Combin. Theory 1, 299.
Sperner Theory, by Konrad Engel. More information on this site.
