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\cal{F}$? Sperner [3] gave an answer in the following elegant theorem:

Theorem.

For every family $\mathcal{F}$ of incomparable subsets of an $n$-set, $\left\lvert\mathcal{F}\right\rvert\leq\binom{n}{\left\lfloor n/2\right\rfloor}$.

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=completeAvailable online at http://www.emis.de/projects/JFM/JFM.
Title Sperner’s theorem SpernersTheorem 2013-03-22 13:51:57 2013-03-22 13:51:57 bbukh (348) bbukh (348) 7 bbukh (348) Theorem msc 05D05 msc 06A07 LYMInequality Sperner family