Lubell-Yamamoto-Meshalkin-Ungleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Lubell-Yamamoto-Meshalkin-Ungleichung oder kurz LYM-Ungleichung ist ein Resultat der diskreten Mathematik. Sie ist engstens mit dem bekannten Satz von Sperner (1905 - 1980) 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 Binomialkoeffizienten.

Die Ungleichung wird Lubell (1966), Yamamoto (1954) und Meshalkin (1963) zugeschrieben[1][2], welche sie unabhängig voneinander fanden. Für die korrekte historische Einordnung muss jedoch erwähnt werden, dass der ungarische Mathematiker 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[3][4], 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. Diese hat sich in den letzten Jahrzehnten zu einem eigenen Zweig der diskreten Mathematik herausgebildet[5]. Im Rahmen dieser Entwicklung hat sich insbesondere ergeben, dass die Lubell-Yamamoto-Meshalkin-Ungleichung auch aufgefasst werden kann als Folge einer allgemeinen Identität, der sogenannten Ahlswede-Zhang-Identität.

Die Ungleichungen[Bearbeiten]

Die LYM-Ungleichung[Bearbeiten]

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}   die 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 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[Bearbeiten]

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 ( J, K =1,\dots,M ;  J \neq K  )

Dann gilt:

{\sum_{J=1}^M \frac{1}{\binom{|A_J|+|B_J|}{|A_J|}}  } \le 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   jeweils    B_J = X \setminus A_J   setzt.

Die beiden Spernerschen Ungleichungen[Bearbeiten]

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 \le n   haben.

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

Dann gelten die folgenden beiden Ungleichungen:

Erste Spernersche Ungleichung
|\Delta\mathcal{T}|  \ge  \frac{k}{n-k+1} \cdot |\mathcal{T}|
Zweite Spernersche Ungleichung
|\nabla\mathcal{T}|  \ge \frac{n-k}{k+1} \cdot |\mathcal{T}|

Die Ahlswede-Zhang-Identität[Bearbeiten]

Diese Identität (auch AZ-Identität genannt, in der englischsprachigen Literatur als AZ identity bezeichnet [8] [9]) geht auf die beiden Mathematiker Rudolf Ahlswede (1938- 2010) und Zhen Zhang zurück. Sie stellt eine Verschärfung der LYM-Ungleichung dar und lässt sich formulieren wie folgt:

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

 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:

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

Ist    \mathcal{A}   eine Antikette von \mathcal P(X) und    A \in \mathcal{A}   , so ist    D_{\mathcal{A}}(A) =  A  . Also ist    \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[Bearbeiten]

Artikel und Originalarbeiten[Bearbeiten]

  •  R. Ahlswede ; Z. Zhang: An identity in combinatorial extremal theory. In: Advances in Mathematics. 80, 1990, S. 137–151.MR1046687
  •  R. Ahlswede ; N. Cai: A generalization of the AZ identity. In: Combinatorica. 13, 1993, S. 241–247. MR1238819
  • 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. MR0360379
  •  L.D. Meshalkin: Generalization of Sperner's theorem on the number of subsets of a finite set. In: Theory of Probability and its Applications. 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).
  •  Koichi Yamamoto: Logarithmic order of free distributive lattice. In: Journal of the Mathematical Society of Japan. 6, 1954, S. 343–353. MR0067086
  • 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. MR0661304

Monographien[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise und Fußnoten[Bearbeiten]

  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   \mathcal{T}
  7. Mengensystem der oberen Nachbarn von   \mathcal{T}
  8.  Ahlswede / Zhang in : Advances in Mathematics 80 (1990): S. 137 ff.
  9.  Engel a.a.O.: S. 18 ff.