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 XX mit nn Elementen (n∈N0)( n \in\mathbb N_0) und weiter ein Mengensystem A\mathcal{A} von Teilmengen von XX, welche paarweise nicht ineinander enthalten sind, also eine Antikette der Potenzmenge 2X2^{X} bilden.
Weiter sei für i=0,…,ni = 0, \dots , n
ai{a_i} = Anzahl der in A\mathcal{A}
vorkommenden Mengen mit exakt ii Elementen.
Dann gilt
∑i=0nai/(ni)≤1 {\sum\limits_{i=0}^n a_i/\chooseNT{n}{{i} } } \le 1 .
Den Satz von Sperner gewinnt man aus der LYM-Ungleichung, indem man beide Seiten der Ungleichung mit
(n⌊n/2⌋) \chooseNT{n}{{\brFloor{ {n/2} }} }
multipliziert und dann noch berücksichtigt, dass die Summe der ai{a_i } gleich der Anzahl der in A\mathcal{A} vorkommenden Mengen ist.
 
 

Nach unserer bisherigen Erfahrung sind wir zum Vertrauen berechtigt, dass die Natur die Realisierung des mathematisch denkbar Einfachsten ist.

Albert Einstein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Lubell-Yamamoto-Meshalkin-Ungleichung aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Diskrete Mathematik