Lubell-Yamamoto-Meshalkin-Ungleichung

Die Lubell-Yamamoto-Meshalkin-Ungleichung o​der kurz LYM-Ungleichung i​st ein Resultat d​er diskreten Mathematik. Sie i​st engstens m​it dem bekannten Satz v​on Sperner (nach Emanuel Sperner, 1905–1980) verknüpft, d​en sie s​ogar verallgemeinert. Ebenso w​ie bei diesem g​eht es a​uch bei d​er LYM-Ungleichung u​m die Darstellung d​es Zusammenhangs zwischen d​en Antiketten endlicher Potenzmengen u​nd den Binomialkoeffizienten.

Die Ungleichung w​ird den d​rei Mathematikern Lubell (1966), Yamamoto (1954) u​nd Meshalkin (1963) zugeschrieben[1][2], welche s​ie unabhängig voneinander fanden. Für d​ie korrekte historische Einordnung m​uss jedoch erwähnt werden, d​ass der ungarische Mathematiker Béla Bollobás i​m Jahre 1965 – e​twa zeitgleich m​it Lubell u​nd Meshalkin – e​ine ganz ähnliche Ungleichung publiziert hat. Tatsächlich i​st die Ungleichung v​on Bollobás i​m Vergleich z​ur LYM-Ungleichung s​ogar noch allgemeiner.

In diesem Zusammenhang i​st erwähnenswert, d​ass Emanuel Sperner selbst i​n seinem Artikel i​m Jahr 1928 a​ls wesentliche Argumentationshilfe z​wei Ungleichungen benutzt u​nd beweist, v​on denen s​ich erwiesen hat[3][4], d​ass sie ihrerseits logisch äquivalent z​ur LYM-Ungleichung sind.

Zusammen m​it dem Satz v​on Sperner bilden d​ie genannten Ungleichungen e​inen wesentlichen Ausgangspunkt für d​ie Entwicklung d​er sogenannten Spernertheorie. Diese h​at sich i​n den letzten Jahrzehnten z​u einem eigenen Zweig d​er diskreten Mathematik herausgebildet[5]. Im Rahmen dieser Entwicklung h​at sich insbesondere ergeben, d​ass die Lubell-Yamamoto-Meshalkin-Ungleichung a​uch aufgefasst werden k​ann als Folge e​iner allgemeinen Identität, d​er sogenannten Ahlswede-Zhang-Identität.

Die Ungleichungen

Die LYM-Ungleichung

Gegeben sei eine endliche Menge   ${\displaystyle X}$   mit   ${\displaystyle n}$   Elementen, wobei   ${\displaystyle n}$   eine natürliche Zahl sei, und weiter ein Mengensystem   ${\displaystyle {\mathcal {A}}}$   von Teilmengen von ${\displaystyle X}$, welche paarweise nicht ineinander enthalten sind, also eine Antikette der Potenzmenge   ${\displaystyle {\mathcal {P}}(X)}$   bilden.

Weiter sei für   ${\displaystyle i=0,\dots ,n}$   ${\displaystyle {a_{i}}}$   die Anzahl der in   ${\displaystyle {\mathcal {A}}}$   vorkommenden Mengen mit exakt   ${\displaystyle i}$   Elementen. Dann gilt:

${\displaystyle {\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   ${\displaystyle {\tbinom {n}{\lfloor {n/2}\rfloor }}}$   multipliziert und einbezieht, dass die Summe der   ${\displaystyle {a_{i}}}$   gleich der Anzahl der in   ${\displaystyle {\mathcal {A}}}$   vorkommenden Mengen ist.

Die Ungleichung von Bollobás

Gegeben seien zwei endliche Folgen endlicher Mengen   ${\displaystyle (A_{1},\dots ,A_{M})}$   und   ${\displaystyle (B_{1},\dots ,B_{M})}$   , welche den folgenden zwei Vorschriften genügen:

1. ${\displaystyle A_{J}\cap B_{J}=\emptyset }$ (${\displaystyle J=1,\dots ,M}$)
2. ${\displaystyle A_{J}\cap B_{K}\neq \emptyset }$ (${\displaystyle J,K=1,\dots ,M}$ ; ${\displaystyle J\neq K}$)

Dann gilt:

${\displaystyle {\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   ${\displaystyle {\mathcal {A}}}$   abzählt in der Form

${\displaystyle {\mathcal {A}}=\{A_{1},\dots ,A_{M}\}}$ (${\displaystyle M=|{\mathcal {A}}|}$)

und dann für   ${\displaystyle J=1,\dots ,M}$   jeweils   ${\displaystyle B_{J}=X\setminus A_{J}}$   setzt.

Die beiden Spernerschen Ungleichungen

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

Sei weiterhin   ${\displaystyle \Delta {\mathcal {T}}}$   das Mengensystem derjenigen Teilmengen   ${\displaystyle A\subseteq X}$   derart, dass für ein   ${\displaystyle T\in {\mathcal {T}}}$   ${\displaystyle A\subset T}$   und zudem   ${\displaystyle |T\setminus A|=1}$   ist[6] und sei   ${\displaystyle \nabla {\mathcal {T}}}$   das Mengensystem derjenigen Teilmengen   ${\displaystyle A\subseteq X}$   derart, dass für ein   ${\displaystyle T\in {\mathcal {T}}}$   ${\displaystyle A\supset T}$   und zudem   ${\displaystyle |A\setminus T|=1}$   ist[7].

Dann gelten d​ie folgenden beiden Ungleichungen:

Erste Spernersche Ungleichung

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

Zweite Spernersche Ungleichung

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

Die Ahlswede-Zhang-Identität

Diese Identität (auch AZ-Identität genannt, i​n der englischsprachigen Literatur a​ls AZ identity bezeichnet[8][9]) g​eht auf d​ie beiden Mathematiker Rudolf Ahlswede (1938–2010) u​nd Zhen Zhang zurück. Sie stellt e​ine Verschärfung d​er LYM-Ungleichung d​ar und lässt s​ich formulieren w​ie folgt:

Gegeben sei eine endliche Menge   ${\displaystyle M}$   mit   ${\displaystyle n}$   Elementen (  ${\displaystyle n\in \mathbb {N} }$  ) und dazu ein nicht-leeres Mengensystem   ${\displaystyle {\mathcal {A}}\neq \emptyset }$   von nicht-leeren Teilmengen von ${\displaystyle M}$, also eine nicht-leere Teilmenge der reduzierten Potenzmenge ${\displaystyle {\mathcal {P}}(M)\setminus \{\emptyset \}}$   . Weiter sei für   ${\displaystyle X\subseteq M}$   :

${\displaystyle D_{\mathcal {A}}(X)={\begin{cases}\ \;\,\bigcap \{A\mid A\in {\mathcal {A}}\land A\subseteq X\}&\exists A\in {\mathcal {A}}:A\subseteq X\\\ \;\,\emptyset &\mathrm {sonst} \end{cases}}}$

Dann gilt:

${\displaystyle \sum _{\emptyset \neq X\subseteq M}{\frac {|D_{\mathcal {A}}(X)|}{|X|\cdot {\binom {n}{|X|}}}}=1}$

Ist   ${\displaystyle {\mathcal {A}}}$   eine Antikette von ${\displaystyle {\mathcal {P}}(X)}$ und   ${\displaystyle A\in {\mathcal {A}}}$   , so ist   ${\displaystyle D_{\mathcal {A}}(A)=A}$ . Also ist   ${\displaystyle \sum _{A\in {\mathcal {A}}}{\frac {1}{\binom {n}{|A|}}}=\sum _{A\in {\mathcal {A}}}{\frac {|A|}{|A|\cdot {\binom {n}{|A|}}}}}$   in der obigen Summe enthalten, was zeigt, dass die AZ-Identität die LYM-Ungleichung unmittelbar impliziert.

Quellen

Artikel und Originalarbeiten

• R. Ahlswede ; Z. Zhang: An identity in combinatorial extremal theory. In: Advances in Mathematics. Band 80, 1990, S. 137–151 (ams.org).

• R. Ahlswede ; N. Cai: A generalization of the AZ identity. In: Combinatorica. Band 13, 1993, S. 241–247 (ams.org).

• Béla Bollobás: On generalized graphs. In: Acta Mathematica Academiae Scientiarum Hungaricae. Band 16, 1965, S. 447–452, doi:10.1007/BF01904851 (ams.org).

• Curtis Greene and Daniel J. Kleitman: Proof techniques in the theory of finite sets in : G. C. Rota (ed.): Studies in Combinatorics. Mathematical Association of America, Washington, DC 1978, ISBN 0-88385-117-2, S. 23–79 (ams.org).

• D. J. Kleitman: On an extremal property of antichains in partial orders. The LYM property and some of its implications and applications in : M. Hall and J. H. van Lint (eds.): Combinatorics (Math. Centre Tracts 55). Amsterdam 1974, S. 77–90 (ams.org).

• D. Lubell: A short proof of Sperner's lemma. In: Journal of Combinatorial Theory. Band 1, 1966, S. 299, doi:10.1016/S0021-9800(66)80035-2 (ams.org).

• L.D. Meshalkin: Generalization of Sperner's theorem on the number of subsets of a finite set. In: Theory of Probability and its Applications. Band 8, 1963, S. 203–204.

• 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. In: Math. Z. Band 27, 1928, S. 544–548 (ams.org).

• Koichi Yamamoto: Logarithmic order of free distributive lattice. In: Journal of the Mathematical Society of Japan. Band 6, 1954, S. 343–353 (ams.org).

• Douglas B. West: Extremal problems in partially ordered sets in : Ivan Rival (ed.): Ordered Sets. Proceedings of the NATO advanced study institute held at Banff, Canada, August 28 to September 12, 1981. D. Reidel Publishing Company, Dordrecht [u. a.] 1982, ISBN 90-277-1396-0, S. 473–521 (ams.org).

Monographien

• Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1.
• Martin Aigner: Combinatorial Theory (= Grundlehren der Mathematischen Wissenschaften. Band 234). Springer Verlag, Berlin (u. a.) 1979, ISBN 3-540-90376-3 (ams.org).
• Martin Aigner: Diskrete Mathematik (= Dokumente zur Geschichte der Mathematik. Band 6). 6. Auflage. Vieweg Verlag, Wiesbaden 2006, ISBN 978-3-8348-0084-8.
• Ian Anderson: Combinatorics of Finite Sets. Clarendon Press, Oxford 1987, ISBN 0-19-853367-5 (ams.org).
• Konrad Engel: Sperner Theory (= Encyclopedia of Mathematics and its Applications. Band 65). Cambridge University Press, Cambridge (u. a.) 1997, ISBN 0-521-45206-6 (ams.org).
• Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York, NY 2005, ISBN 0-387-24219-8 (ams.org).
• Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer Verlag, Heidelberg (u. a.) 2011, ISBN 978-3-642-17363-9 (ams.org).
• 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 (ams.org).

Weblinks

• Lectures on extremal set systems and two-colorings of hypergraphs (PDF; 237 kB) von Gy. Károlyi.
• Kombinatorische Methoden in der Informatik. (PDF; 1,4 MB) Skript einer Vorlesung von Peter Hauck, Uni Tübingen, SS 2008.
• Weiterführender Artikel von Rudolf Ahlswede und Ning Cai zur AZ-Identität
• Weiterführender Artikel von T. D. Thu zur AZ-Identität

Einzelnachweise und Fußnoten

1. Curtis Greene, Daniel J. Kleitman: Proof techniques in the theory of finite sets in: Studies in Combinatorics. Hrsg.: Gian-Carlo Rota. S. 35.
2. Martin Aigner: Combinatorial Theory. S. 425.
3. D. J. Kleitman in : M. Hall and J. H. van Lint (eds.): Combinatorics (Math. Centre Tracts 55). Amsterdam 1974, S. 77 ff.
4. Hans-Josef Scholz: Über die Kombinatorik der endlichen Potenzmengen im Zusammenhang mit dem Satz von Sperner. S. 19.
5. Konrad Engel: Sperner Theory.
6. Mengensystem der unteren Nachbarn von   ${\displaystyle {\mathcal {T}}}$
7. Mengensystem der oberen Nachbarn von   ${\displaystyle {\mathcal {T}}}$
8. R. Ahlswede, Z. Zhang: An identity in combinatorial extremal theory. In: Advances in Mathematics. Band 80, 1990, S. 137–151.
9. Konrad Engel: Sperner Theory (= Encyclopedia of Mathematics and its Applications. Band 65). Cambridge University Press, Cambridge (u. a.) 1997, ISBN 0-521-45206-6, S. 18 ff.