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 (nach Emanuel 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 den drei Mathematikern 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 Artikel im Jahr 1928 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
Die LYM-Ungleichung
Gegeben sei eine endliche Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Elementen, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} eine natürliche Zahl sei, und weiter ein Mengensystem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{A}} von Teilmengen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} , welche paarweise nicht ineinander enthalten sind, also eine Antikette der Potenzmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal P(X)} bilden.
Weiter sei für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i = 0,\dots,n} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {a_i}} die Anzahl der in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{A}} vorkommenden Mengen mit exakt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} Elementen. Dann gilt:
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tbinom{n}{\lfloor {n/2} \rfloor}} multipliziert und einbezieht, dass die Summe der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {a_i }} gleich der Anzahl der in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{A}} vorkommenden Mengen ist.
Die Ungleichung von Bollobás
Gegeben seien zwei endliche Folgen endlicher Mengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ( A_1,\dots,A_M )} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (B_1,\dots,B_M )} , welche den folgenden zwei Vorschriften genügen:
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_J\cap B_J = \emptyset} (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J=1,\dots,M} )
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_J\cap B_K \neq \emptyset} (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J, K =1,\dots,M} ; Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J \neq K } )
Dann gilt:
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{A}} abzählt in der Form
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{A} = \{A_1,\dots,A_M \}} (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = |\mathcal{A}|} )
und dann für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J=1,\dots,M} jeweils Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B_J = X \setminus A_J} setzt.
Die beiden Spernerschen Ungleichungen
Gegeben sei eine endliche Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Elementen, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} eine natürliche Zahl sei, und zudem ein Mengensystem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{T}} von Teilmengen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} , welche alle dieselbe Mächtigkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \le n} haben.
Sei weiterhin Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta\mathcal{T}} das Mengensystem derjenigen Teilmengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \subseteq X} derart, dass für ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T \in \mathcal{T} } Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \subset T} und zudem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |T \setminus A| = 1} ist[6] und sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nabla\mathcal{T}} das Mengensystem derjenigen Teilmengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \subseteq X} derart, dass für ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T \in \mathcal{T}} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \supset T} und zudem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |A \setminus T| = 1} ist[7].
Dann gelten die folgenden beiden Ungleichungen:
- Erste Spernersche Ungleichung
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |\Delta\mathcal{T}| \ge \frac{k}{n-k+1} \cdot |\mathcal{T}|}
- Zweite Spernersche Ungleichung
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |\nabla\mathcal{T}| \ge \frac{n-k}{k+1} \cdot |\mathcal{T}|}
Die Ahlswede-Zhang-Identität
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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Elementen ( Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \in \mathbb N } ) und dazu ein nicht-leeres Mengensystem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{A} \neq \emptyset } von nicht-leeren Teilmengen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} , also eine nicht-leere Teilmenge der reduzierten Potenzmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal P(M) \setminus \{ \emptyset \}} . Weiter sei für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X \subseteq M } :
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{\emptyset \neq X \subseteq M } \frac{|D_{\mathcal{A}}(X)|}{|X|\cdot \binom{n}{|X|}} = 1 }
Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{A} } eine Antikette von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal P(X)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \in \mathcal{A} } , so ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{\mathcal{A}}(A) = A } . Also ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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
- ↑ Curtis Greene, Daniel J. Kleitman: Proof techniques in the theory of finite sets in: Studies in Combinatorics. Hrsg.: Gian-Carlo Rota. S. 35.
- ↑ Martin Aigner: Combinatorial Theory. S. 425.
- ↑ D. J. Kleitman in : M. Hall and J. H. van Lint (eds.): Combinatorics (Math. Centre Tracts 55). Amsterdam 1974, S. 77 ff.
- ↑ Hans-Josef Scholz: Über die Kombinatorik der endlichen Potenzmengen im Zusammenhang mit dem Satz von Sperner. S. 19.
- ↑ Konrad Engel: Sperner Theory.
- ↑ Mengensystem der unteren Nachbarn von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{T}}
- ↑ Mengensystem der oberen Nachbarn von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{T}}
- ↑ R. Ahlswede, Z. Zhang: An identity in combinatorial extremal theory. In: Advances in Mathematics. Band 80, 1990, S. 137–151.
- ↑ 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.