|
|
|
|
|
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.
- 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)
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 MSC: | 05D05 (Combinatorics :: Extremal combinatorics :: Extremal set theory) | | | 06A07 (Order, lattices, ordered algebraic structures :: Ordered sets :: Combinatorics of partially ordered sets) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|