Lubell-Yamamoto-Meshalkin-Ungleichung

Die Lubell-Yamamoto-Meshalkin-Ungleichung oder kurz LYM-Ungleichung ist ein Resultat der diskreten Mathematik. Sie ist engstens mit dem bekannten Satz von Sperner verknüpft, den sie sogar verallgemeinert. Ebenso wie bei diesem geht es auch bei der LYM-Ungleichung um die Darstellung des Zusammenhangs zwischen den Antiketten endlicher Potenzmengen und den sogenannten Binomialkoeffizienten.

Die Ungleichung wird Lubell (1966), Yamamoto (1954) und Meshalkin (1963) zugeschrieben, welche sie unabhängig voneinander fanden. Für die korrekte historische Einordnung muss jedoch erwähnt werden, dass Béla Bollobás im Jahre 1965 - etwa zeitgleich mit Lubell und Meshalkin - eine ganz ähnliche Ungleichung publiziert hat. Tatsächlich ist die Ungleichung von Bollobás im Vergleich zur LYM-Ungleichung sogar noch allgemeiner.

In diesem Zusammenhang ist erwähnenswert, dass Emanuel Sperner selbst in seinem 1928-er Artikel als wesentliche Argumentationshilfe zwei Ungleichungen benutzt und beweist, von denen sich erwiesen hat, dass sie ihrerseits logisch äquivalent zur LYM-Ungleichung sind.

Zusammen mit dem Satz von Sperner bilden die genannten Ungleichungen einen wesentlichen Ausgangspunkt für die Entwicklung der sogenannten Spernertheorie (englisch Sperner theory). Diese hat sich in den letzten Jahrzehnten zu einem eigenen Zweig der diskreten Mathematik herausgebildet. Einen Überblick über die Spernertheorie und deren Umfeld geben Anderson, Engel oder Jukna (siehe Literatur).

Die Ungleichungen

Die LYM-Ungleichung

Gegeben sei eine endliche Menge $X\,$ mit $n\,$ Elementen, wobei $n\,$ eine natürlichen Zahl sei, und weiter ein Mengensystem ${\mathcal {A}}$ von Teilmengen von $X\,$, welche paarweise nicht ineinander enthalten sind, also eine Antikette der Potenzmenge ${\mathcal {P}}(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}}}}\leq 1$

Den Satz von Sperner gewinnt man aus der LYM-Ungleichung, indem man auf beiden Seiten der Ungleichung mit dem größten Binomialkoeffizienten ${\tbinom {n}{\lfloor {n/2}\rfloor }}$ multipliziert und einbezieht, dass die Summe der ${a_{i}}\,$ gleich der Anzahl der in ${\mathcal {A}}$ vorkommenden Mengen ist.

Die Ungleichung von Bollobás

Gegeben seien zwei endliche Folgen endlicher Mengen

$(A_{1},\dots ,A_{M})$ und $(B_{1},\dots ,B_{M})$ , welche den folgenden zwei Vorschriften genügen:

(1) $A_{J}\cap B_{J}=\emptyset$ ( $J=1,\dots ,M$ )

(2) $A_{J}\cap B_{K}\neq \emptyset$ ( $1\leq J<K\leq M$ )

Dann gilt:

${\sum _{J=1}^{M}{\frac {1}{\binom {|A_{J}|+|B_{J}|}{|A_{J}|}}}}\leq 1$

Die LYM-Ungleichung gewinnt man aus der Ungleichung von Bollobás, indem man ${\mathcal {A}}$ abzählt in der Form

${\mathcal {A}}=\{A_{1},\dots ,A_{M}\}$ ( $M=|{\mathcal {A}}|$ ) und dann für $J=1,\dots ,M$ jeweis $B_{J}=X\setminus A_{J}$ setzt.

Die beiden Spernerschen Ungleichungen

Gegeben sei eine endliche Menge $X\,$ mit $n\,$ Elementen, wobei $n\,$ eine natürlichen Zahl sei, und zudem ein Mengensystem ${\mathcal {T}}$ von Teilmengen von $X\,$, welche alle dieselbe Mächtigkeit $\mathrm {} k\leq n$ haben.

Seien weiterhin

$\Delta {\mathcal {T}}$ = Mengensystem derjenigen Teilmengen $A\subseteq X\,$, so dass für ein $T\in {\mathcal {T}}$ $A\subset T$ und zudem $|T\setminus A|=1$ ist

( Mengensystem der "unteren Nachbarn" von ${\mathcal {T}}$ )

und

$\nabla {\mathcal {T}}$ = Mengensystem derjenigen Teilmengen $A\subseteq X\,$, so dass für ein $T\in {\mathcal {T}}$ $A\supset T$ und zudem $|A\setminus T|=1$ ist

( Mengensystem der "oberen Nachbarn" von ${\mathcal {T}}$ )

Dann bestehen die folgenden beiden Ungleichungen:

Erste Spernersche Ungleichung

$|\Delta {\mathcal {T}}|\geq {\frac {k}{n-k+1}}\cdot |{\mathcal {T}}|$

Zweite Spernersche Ungleichung

$|\nabla {\mathcal {T}}|\geq {\frac {n-k}{k+1}}\cdot |{\mathcal {T}}|$

Literatur

Originalarbeiten

• Béla Bollobás: On generalized graphs. Acta Mathematica Academiae Scientiarum Hungaricae, Vol. 16, 3–4, (1965): 447–452. doi:10.1007/BF01904851, MR

• D. Lubell: A short proof of Sperner's lemma. Journal of Combinatorial Theory, Vol. 1, 2 (1966): 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): 203–204. doi:10.1137/1108023, MR

• Hans-Josef Scholz: Über die Kombinatorik der endlichen Potenzmengen im Zusammenhang mit dem Satz von Sperner. Dissertation, Universität Düsseldorf (1987).

• Emanuel Sperner: Ein Satz über Untermengen einer endlichen Menge. Math. Z. 27 (1928): 544–548. MR

• Koichi Yamamoto: Logarithmic order of free distributive lattice. Journal of the Mathematical Society of Japan, Vol. 6 (1954): 343–353. MR.

Monographien

• Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie. Springer-Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1. 

• Martin Aigner: Combinatorial Theory. Springer-Verlag, Berlin (u. a.) 1979, ISBN 3-540-90376-3. 

• Martin Aigner: Diskrete Mathematik. 6. Auflage. Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8. 

• Ian Anderson: Combinatorics of Finite Sets. Clarendon Press, Oxford 1987, ISBN 0-19-853367-5. 

• Konrad Engel: Sperner Theory. Cambridge University Press, Cambridge (u. a.) 1997, ISBN 0-521-45206-6. 

• Egbert Harzheim: Ordered Sets. Springer, New York 2005, ISBN 0-387-24219-8. 

• Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way. Cambridge University Press, Cambridge (u. a) 2009, ISBN 978-0-521-73794-4. 

• Stasys Jukna: Extremal Combinatorics. Springer-Verlag, Heidelberg (u. a.) 2011, ISBN 978-3-642-17363-9. 

Weblinks

• [1] Link ins englische WIKIPEDIA zu "LYM inequality"
• [2] Link zu "Lectures on extremal set systems and two-colorings of hypergraphs" von Gy. Károlyi
• [3] Kombinatorische Methoden in der Informatik (Skript einer Vorlesung von Prof. Dr. Peter Hauck, Uni Tübingen, SS 2008)