# 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 LYMInequality 2013-03-22 14:06:01 2013-03-22 14:06:01 bbukh (348) bbukh (348) 6 bbukh (348) Theorem msc 05D05 msc 06A07 LYM-inequality SpernersTheorem