Science Fair Project Encyclopedia
- If X, Y are in F and X ≠ Y, then X is not contained in Y and Y is not contained in X.
One interesting and useful result is the following, known as Sperner's theorem.
For every Sperner family S over an n-set,
The following proof is due to Lubell. (see reference). Let sk denote the number of k-sets in S. For all 0 ≤ k ≤ n,
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
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.
Lubell, D. (1966). A short proof of Sperner's theorem, J. Combin. Theory 1, 299.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details