Sperner’s theorem
What is the size of the largest family of subsets of an -element set such that no is a subset of ? Sperner [3] gave an answer in the following elegant theorem:
Theorem.
For every family of incomparable subsets of an -set, .
A family satisfying the conditions of Sperner’s theorem is usually
called Sperner family or antichain. The later
terminology stems from the fact that subsets of a finite set
ordered by inclusion form a Boolean lattice.
There are many generalizations of Sperner’s theorem. On one hand,
there are refinements
like LYM inequality that strengthen the
theorem in various ways. On the other hand, there are
generalizations to posets other than the Boolean lattice. For a
comprehensive exposition of the topic one should consult a
well-written monograph by Engel[2].
References
-
1
Béla Bollobás.
Combinatorics: Set systems, hypergraphs
, families of vectors, and combinatorial probability. 1986. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0595.05001Zbl 0595.05001.
- 2 Konrad Engel. Sperner theory, volume 65 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0868.05001Zbl 0868.05001.
-
3
Emanuel Sperner.
Ein Satz über Untermengen einer endlichen Menge.
Math. Z., 27:544–548, 1928.
http://www.emis.de/cgi-bin/jfmen/MATH/JFM/quick.html?first=1&maxdocs=20&type=html&an=JFM%2054.0090.06&format=complete
Available online at http://www.emis.de/projects/JFM/JFM.
Title | Sperner’s theorem |
---|---|
Canonical name | SpernersTheorem |
Date of creation | 2013-03-22 13:51:57 |
Last modified on | 2013-03-22 13:51:57 |
Owner | bbukh (348) |
Last modified by | bbukh (348) |
Numerical id | 7 |
Author | bbukh (348) |
Entry type | Theorem |
Classification | msc 05D05 |
Classification | msc 06A07 |
Related topic | LYMInequality |
Defines | Sperner family |