LYM inequality
Let ℱ be a Sperner family, that is, the collection
of
subsets of {1,2,…,n} such that no set contains any other subset.
Then
| ∑X∈ℱ1(n|X|)≤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 (nk)≤(n⌊n/2⌋) for every integer k, LYM inequality tells us that |F|/(n⌊n/2⌋)≤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
-
4
Koichi Yamamoto.
Logarithmic order of free distributive lattice
| 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 |