LYM inequality

Let $\mathcal{F}$ be a Sperner family, that is, the collection of subsets of $\{1,2,\ldots,n\}$ such that no set contains any other subset. Then

\sum_{X\in\mathcal{F}}\frac{1}{\binom{n}{\left\lvert X\right\rvert}}\leq 1.

This inequality is known as LYM inequality by the names of three people that independently discovered it: Lubell[2], Yamamoto[4], Meshalkin[3].

Since $\binom{n}{k}\leq\binom{n}{\left\lfloor n/2\right\rfloor}$ for every integer $k$ , LYM inequality tells us that $\left\lvert F\right\rvert/\binom{n}{\left\lfloor n/2\right\rfloor}\leq 1$ which is Sperner’s theorem (http://planetmath.org/SpernersTheorem).

References

1 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.
2 David Lubell. A short proof of Sperner’s lemma. J. Comb. Theory, 1:299, 1966. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0151.01503Zbl 0151.01503.
3 Lev D. Meshalkin. Generalization of Sperner’s theorem on the number of subsets of a finite set. Teor. Veroyatn. Primen., 8:219–220, 1963. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0123.36303Zbl 0123.36303.
4 Koichi Yamamoto. Logarithmic order of free distributive lattice. J. Math. Soc. Japan, 6:343–353, 1954. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0056.26301Zbl 0056.26301.

Title	LYM inequality
Canonical name	LYMInequality
Date of creation	2013-03-22 14:06:01
Last modified on	2013-03-22 14:06:01
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	6
Author	bbukh (348)
Entry type	Theorem
Classification	msc 05D05
Classification	msc 06A07
Synonym	LYM-inequality
Related topic	SpernersTheorem