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,

|S| \le {n \choose \lfloor{n/2}\rfloor}.

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,

{n \choose \lfloor{n/2}\rfloor} \ge {n \choose k}

and, thus,

{s_k \over {n \choose \lfloor{n/2}\rfloor}} \le {s_k \over {n \choose k}}.

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

\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,

which means

|S| = \sum_{k=0}^n s_k \le {n \choose \lfloor{n/2}\rfloor}.

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.

[edit] External links

Languages