LYM inequality
Let $\mathcal{F}$ be a Sperner family, that is, the collection^{} of subsets of $\{1,2,\mathrm{\dots},n\}$ such that no set contains any other subset. Then
$$\sum _{X\in \mathcal{F}}\frac{1}{\left(\genfrac{}{}{0pt}{}{n}{\left|X\right|}\right)}\le 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 $\left(\genfrac{}{}{0pt}{}{n}{k}\right)\le \left(\genfrac{}{}{0pt}{}{n}{\lfloor n/2\rfloor}\right)$ for every integer $k$, LYM inequality tells us that $\left|F\right|/\left(\genfrac{}{}{0pt}{}{n}{\lfloor n/2\rfloor}\right)\le 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 |