Sperner’s theorem
What is the size of the largest family $\mathcal{F}$ of subsets of an $n$-element set such that no $A\in \mathcal{F}$ is a subset of $B\in \mathcal{F}$? Sperner [3] gave an answer in the following elegant theorem:
Theorem.
For every family $\mathrm{F}$ of incomparable subsets of an $n$-set, $\mathrm{\left|}\mathrm{F}\mathrm{\right|}\mathrm{\le}\mathrm{\left(}\genfrac{}{}{0pt}{}{n}{\mathrm{\lfloor}n\mathrm{/}\mathrm{2}\mathrm{\rfloor}}\mathrm{\right)}$.
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 |