Lubell-Yamamoto-Meshalkin-Ungleichung
aus Wikipedia, der freien Enzyklopädie
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 (
) und weiter ein Mengensystem 
von Teilmengen von X, welche paarweise nicht ineinander enthalten sind, also eine Antikette der Potenzmenge 2X bilden.
Weiter sei für i = 0, ... , n
- ai = Anzahl der in vorkommenden Mengen mit exakt i Elementen.
Dann gilt
.
Den Satz von Sperner gewinnt man aus der LYM-Ungleichung, indem man beide Seiten der Ungleichung mit
multipliziert und dann noch berücksichtigt, dass die Summe der ai gleich der Anzahl der in vorkommenden Mengen ist.
