Lubell-Yamamoto-Meshalkin-Ungleichung

Die Lubell-Yamamoto-Meshalkin-Ungleichung oder auch LYM-Ungleichung ist ein Resultat, welches mit dem Satz von Sperner eng verwandt ist und diesen sogar verallgemeinert. Ebenso wie bei dem Satz von Sperner geht es auch bei der LYM-Ungleichung um die Darstellung des unmittelbaren Zusammenhangs zwischen Antiketten endlicher Potenzmengen und Binomialkoeffizienten.

Das Resultat fanden unabhängig voneinander Lubell 1966, Yamamoto 1954 und Meshalkin 1963.

Die LYM-Ungleichung lässt sich wie folgt formulieren:

Gegeben sei eine endliche Menge X mit n Elementen ($n \in\mathbb N_0$) und weiter ein Mengensystem $\mathcal{A}$ von Teilmengen von X, welche paarweise nicht ineinander enthalten sind, also eine Antikette der Potenzmenge 2^X bilden.

Weiter sei für $i = 0,\dots,n$

a_i = Anzahl der in $\mathcal{A}$ vorkommenden Mengen mit exakt i Elementen.

Dann gilt

${\sum_{i=0}^n \frac{a_i}{\binom{n}{i}} } \le 1.$

Den Satz von Sperner gewinnt man aus der LYM-Ungleichung, indem man beide Seiten der Ungleichung mit $\tbinom{n}{\lfloor {n/2} \rfloor}$ multipliziert und dann noch berücksichtigt, dass die Summe der a_i gleich der Anzahl der in $\mathcal{A}$ vorkommenden Mengen ist.

Literatur

• B. Bollobás: On generalized graphs, Acta Mathematica Academiae Scientiarum Hungaricae, Vol. 16, 3–4, (1965). S. 447–452. doi:10.1007/BF01904851, MR
• D. Lubell: A short proof of Sperner's lemma, Journal of Combinatorial Theory, Vol. 1, 2 (1966). S. 299. doi:10.1016/S0021-9800(66)80035-2, MR
• L.D. Meshalkin: Generalization of Sperner's theorem on the number of subsets of a finite set, Theory of Probability and its Applications, Vol. 8, 2 (1963). S. 203–204, doi:10.1137/1108023, MR
• Koichi Yamamoto: Logarithmic order of free distributive lattice, Journal of the Mathematical Society of Japan, Vol. 6, 1954, S. 343–353, MR.