PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
LYM inequality (Theorem)

Let $\mathcal{F}$ be a Sperner family, that is, the collection of subsets of $\{1,2,\dotsc,n\}$ such that no set contains any other subset. Then \begin{equation*} \sum_{X\in\mathcal{F}} \frac{1}{\binom{n}{\abs{X}}}\leq 1. \end{equation*}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}{\floor{n/2}}$ for every integer $k$ LYM inequality tells us that $\abs{F}/\binom{n}{\floor{n/2}}\leq 1$ which is Sperner's theorem.

References

1
Konrad Engel.
Sperner theory, volume 65 of Encyclopedia of Mathematics and Its Applications.
Cambridge University Press.
Zbl 0868.05001.
2
David Lubell.
A short proof of Sperner's lemma.
J. Comb. Theory, 1:299, 1966.
Zbl 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.
Zbl 0123.36303.
4
Koichi Yamamoto.
Logarithmic order of free distributive lattice.
J. Math. Soc. Japan, 6:343-353, 1954.
Zbl 0056.26301.




"LYM inequality" is owned by bbukh.
(view preamble | get metadata)

View style:

See Also: Sperner's theorem

Other names:  LYM-inequality
Keywords:  Sperner family
Log in to rate this entry.
(view current ratings)

Cross-references: integer, inequality, contains, subsets, collection, Sperner family
There is 1 reference to this entry.

This is version 3 of LYM inequality, born on 2003-12-24, modified 2004-01-25.
Object id is 5498, canonical name is LYMInequality.
Accessed 3679 times total.

Classification:
AMS MSC05D05 (Combinatorics :: Extremal combinatorics :: Extremal set theory)
 06A07 (Order, lattices, ordered algebraic structures :: Ordered sets :: Combinatorics of partially ordered sets)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)