Sperner’s theorem

What is the size of the largest family of subsets of an n-element set such that no A is a subset of B? Sperner [3] gave an answer in the following elegant theorem:


For every family F of incomparable subsets of an n-set, |F|(nn/2).

A family satisfying the conditions of Sperner’s theorem is usually called Sperner family or antichainMathworldPlanetmath. The later terminology stems from the fact that subsets of a finite setMathworldPlanetmath ordered by inclusion form a Boolean lattice.

There are many generalizationsPlanetmathPlanetmath of Sperner’s theorem. On one hand, there are refinementsMathworldPlanetmathPlanetmath 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].


  • 1 Béla Bollobás. Combinatorics: Set systems, hypergraphsMathworldPlanetmath, 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=completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathAvailable 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