Sperner’s theorem

What is the size of the largest family $ℱ$ of subsets of an $n$-element set such that no $A\in ℱ$ is a subset of $B\in ℱ$? 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].

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