LYM inequality


Let be a Sperner family, that is, the collectionMathworldPlanetmath of subsets of {1,2,,n} such that no set contains any other subset. Then

X1(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)(nn/2) for every integer k, LYM inequality tells us that |F|/(nn/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. GeneralizationPlanetmathPlanetmath of Sperner’s theorem on the number of subsets of a finite setMathworldPlanetmath. 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 latticeMathworldPlanetmath. 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