Benutzer:Schojoha/Spielwiese/Kombinatorik

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Lemma von Kleitman

[Bearbeiten | Quelltext bearbeiten]

Der Lemma von Kleitman, englisch Kleitman's lemma, ist einer der Lehrsätze des mathematischen Teilgebiets der Kombinatorik. Es geht auf eine Arbeit von Daniel J. Kleitman aus dem Jahre 1966 zurück und behandelt eine Größenabschätzung für gewisse Teilmengensysteme innerhalb einer endlichen Potenzmenge. Das Lemma steht in enger Beziehung zu der Ungleichung von Ahlswede-Daykin (englisch Ahlswede–Daykin inequality), mit der es sich leicht herleiten lässt.[1][2][3]

Das Lemma lässt sich angeben wie folgt:[1][2][3]

Gegeben seien eine natürliche Zahl sowie eine endliche Menge mit Elementen und dazu zwei Teilmengensysteme und .
Dabei soll gelten, dass innerhalb einerseits ein Ideal sei und andererseits ein Filter.[A 1]
Dann gilt die folgende Ungleichung:
.[A 2]

Das Lemma zieht eine Reihe von Folgerungen nach sich. Dazu gehören nicht zuletzt die folgenden:[1][2][3]

(i) Ist (unter den obigen allgemeinen Voraussetzungen) ein Teilmengensystem gegeben, welches zudem die Eigenschaft haben soll, dass für stets die Relationen erfüllt seien, so gilt die Ungleichung . Diese obere Schranke ist für jede natürliche Zahl die bestmögliche.
(ii) Sind (unter den obigen allgemeinen Voraussetzungen) endlich viele Teilmengensysteme gegeben derart, dass für und stets die Relation erfüllt ist, so gilt für die Gesamtheit all dieser Teilmengen die Ungleichung .[A 3] Diese obere Schranke ist für alle natürlichen Zahlen und mit die bestmögliche.

Verwandter Satz

[Bearbeiten | Quelltext bearbeiten]

Verwandt mit dem Kleitman'schen Lemma ist ein Satz, der im Jahre 1969 von John G. Marica und Johanan Schönheim vorgelegt wurde und die folgende elementare Aussage macht:[4][3]

Ist eine natürliche Zahl und sind verschiedene Mengen gegeben, so gibt es dazu stets mindestens verschiedene Differenzmengen .

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

rreferences />

rreferences group="A" />

KKKategorie:Satz (Mathematik)|Kleitman, Lemma von]]

Kriterium für Vollständige Unimodularität

[Bearbeiten | Quelltext bearbeiten]

In der Kombinatorischen Optimierung, einem der Teilgebiete der Kombinatorik, findet man einige Kriterien für die vollständige Unimodularität ganzzahliger Matrizen. Ein besonders nützliches dieser Kriterien geht auf eine Arbeit des französischen Mathematikers Alain Ghouila-Houri aus dem Jahre 1962 zurück.[5]

Das Kriterium lässt sich angeben wie folgt:[6]

Eine Matrix ist genau dann vollständig unimodular, wenn es für jede Teilmenge eine Zerlegung
gibt derart, dass für jeden Index die Beziehung
erfüllt ist.

Das Kriterium von Ghouila-Houri lässt sich umsetzen in ein Kriterium für bipartite Graphen:[7]

Die Inzidenzmatrix eines endlichen ungerichteten Graphen ist vollständig unimodular genau dann, wenn bipartit ist.

Weiteres Kriterium

[Bearbeiten | Quelltext bearbeiten]

Ein anderes wichtiges Kriterium für die vollständige Unimodularität ganzzahliger Matrizen – welches auch zum Beweis des Kriteriums von Ghouila-Houri herangezogen werden kann[5] – hatten schon A.J. Hoffman und J.B. Kruskal im Jahre 1956 geliefert. Darin wird die vollständige Unimodularität ganzzahliger Matrizen in Verbindung gebracht mit Ganzzahligkeitseigenschaften der zugehörigen Polyeder. Im Einzelnen gilt nämlich der folgende Satz:[8][9]

Eine Matrix ist genau dann vollständig unimodular, wenn für jeden Vektor sämtliche Eckpunkte des zu gehörigen Polyeders ganzzahlige Koordinaten haben.
  • Eine heißt vollständig unimodular oder auch total unimodular, englisch totally unimodular , falls jede Unterdeterminante (und damit auch jedes Element) von gleich 0 oder gleich 1 oder gleich −1 ist.[5].[8]
  • Martin Aigner: Diskrete Mathematik (= Vieweg Studium: Aufbaukurs Mathematik). 6., korrigierte Auflage. Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8.
  • Alain Ghouila-Houri: Caractérisation des graphes non orientés dont on peut orienter les arětes de manière à obtenir le graphe d'une relation d'ordre. In: Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Band 254, 1962, S. 1370–1371 (MR0172275).
  • A. J. Hoffman , J. B. Kruskal: Integral boundary points of convex polyhedra In: Linear Inequalities and Related Systems. In: Annals of Mathematics Studies. Band 38, 1956, S. 223–246 (MR0085148).
  • Bernhard Korte, Jens Vygen: Kombinatorische Optimierung: Theorie und Algorithmen. 3. Auflage. Springer Spektrum, Berlin 2018, ISBN 978-3-662-57690-8, S. 122 ff.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

rreferences />

KKKategorie:Kombinatorik]] KKKategorie:Satz (Graphentheorie)|Kriterium für Vollständige Unimodularität]]

Satz von Graham-Leeb-Rothshild

[Bearbeiten | Quelltext bearbeiten]

Der Satz von Graham-Leeb-Rothshild, benannt nach den Mathematikern Ronald Lewis Graham, Klaus Leeb und Bruce Lee Rothschild, ist ein Lehrsatz des mathematischen Teilgebiets der Ramseytheorie. Der Satz ist in der englischsprachigen Fachliteratur auch als Vektor Space Ramsey Theorem oder als Ramsey Theorem for Spaces bekannt. Ihm liegt eine Vermutung von Gian-Carlo Rota zugrunde.[10]

Formulierung des Satzes

[Bearbeiten | Quelltext bearbeiten]

Im Einzelnen besagt der Satz Folgendes:[10][11]

Gegeben seien ein endlichen Körper sowie ein endlicher -Vektorraum und ganze Zahlen mit .
Für eine ganze Zahl und einen beliebigen -Vektorraum sei
das Mengensystem der -dimensionalen Unterräume von und
für eine ganze Zahl
das aus mit sich selbst gebildete -fache direkte Vektorraumprodukt.
Dann gilt:
Es gibt eine ganze Zahl derart, dass für jede beliebige ganze Zahl
und jede Zerlegung
der -dimensionalen Unterräume von in Klassen
stets ein -dimensionaler Unterraum existiert, so dass
für mindestens eine der Klassen gilt.

Quellen und Hintergrundliteratur

[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

Kreferences />


KKKategorie:Kombinatorik]] KKKategorie:Diskrete Mathematik]] KKKategorie:Satz (Mathematik)|Satz von Lovász-Stein]]



Satz von Lovász-Stein

[Bearbeiten | Quelltext bearbeiten]

Der Satz von Lovász-Stein, benannt nach den Mathematikern László Lovász und Sherman K. Stein, ist ein Lehrsatz des mathematischen Teilgebiets der Graphentheorie. Der Satz formuliert eine Ungleichung, welche die kleinste Anzahl von Hyperkanten, die zur Überdeckung der gesamten Knotenmenge eines gegebenen endlichen Hypergraphen benötigt wird, zu anderen Kennziffern dieses Hypergraphen in Beziehung setzt.[12]

Formulierung des Satzes

[Bearbeiten | Quelltext bearbeiten]

Der Darstellung von Stasys Jukna folgend lässt sich der Satz wie folgt formulieren:[12]

Seien natürliche Zahlen.
Sei dazu ein endlicher Hypergraph, bestehend aus einer endlichen Knotenmenge mit Knoten und einem System von Hyperkanten.
Dabei sei vorausgesetzt, dass
jeder Knoten mindestens den Grad hat
und
jede Hyperkante aus höchstens Knoten besteht.
Weiter sei
die kleinste Anzahl von Hyperkanten, die benötigt wird, um die gesamte Knotenmenge zu überdecken.
Dann gilt:
.

Anwendung auf spezielle Blockpläne

[Bearbeiten | Quelltext bearbeiten]

Der Satz gibt als Anwendung eine obere Abschätzung über gewisse Anzahlen von Blöcken bei sogenannten Überdeckungsblockplänen.

Dabei ist ein Überdeckungsblockplan (englisch covering design) ein -uniformer Hypergraph, dessen Knoten bzw. Hyperkanten aufgefasst werden als Punkte bzw. Blöcke eines Blockplans mit der Eigenschaft, dass je verschiedene Punkte in mindestens einem der Blöcke enthalten sind (mit ). Sind die Kennziffern gegeben, so wird die kleinste unter den möglichen Anzahlen mit bezeichnet.

Dabei ist stets

.

Mit dem Satz von Lovász-Stein lässt sich nun nach oben abschätzen:[13]

.

Quellen und Hintergrundliteratur

[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

rreferences />

KKKategorie:Satz (Graphentheorie)|Lovasz-Stein]] KKKategorie:Endliche Geometrie]]



Lemma von Corrádi

[Bearbeiten | Quelltext bearbeiten]

Das Lemma von Corrádi, benannt nach dem ungarischen Mathematiker K. Corrádi, ist ein Lehrsatz, welcher dem Übergangsfeld der mathematischen Teilgebiete Kombinatorik, Graphentheorie und Endliche Geometrie zuzurechnen ist. Das Lemma gibt Aufschluss über die mindestens notwendige Anzahl der Knoten, die ein endlicher uniformer Hypergraph haben muss, wenn vorausgesetzt wird, dass je zwei verschiedene Hyperkanten eine gewisse vorgegebene Anzahl von Elementen gemeinsam haben.[12][14]

Formulierung des Lemmas

[Bearbeiten | Quelltext bearbeiten]

Im Einzelnen besagt das Lemma folgendes:[12][14]

Seien natürliche Zahlen und eine ganze Zahl mit .
Sei ein -uniformer Hypergraph, bestehend aus einer -elementigen Grundmenge und einer -gliedrigen Familie von Hyperkanten.
Sei weiter vorausgesetzt, dass für alle Durchschnitte je zweier Hyperkanten stets die Anzahlbedingung gegeben sei.
Dann gilt:
(*) .

Der Beweis der behaupteten Ungleichung ergibt sich - in Anschluss an die Darstellung bei Jukna bzw. Lovász - durch Anwendung der Methode des doppelten Abzählens und der jensenschen Ungleichung in folgenden Schritten:[12][14]

Festlegungen
(1)
(2)
(3)
Doppeltes Abzählen
(4)
(5)
Abschätzung nach oben

Mit (4) ergibt sich insbesondere für :

(6)

Also folgt aus (5) und (6):

(7)
Abschätzung nach unten

Vermöge der jensenschen Ungleichung ergibt sich:

(8)

Wiederum mit (4) und folgt dann:

(9)
Zusammenfassung

(7) und (9) zusammen ergeben dann:

(10)

Da nun (10) und (*) gleichwertig sind, ist alles gezeigt.

Die obige Ungleichung (*) ist scharf in dem Sinne, dass endliche Strukturen existieren, für welche in der Ungleichung (*) sogar das Gleichheitszeichen gilt. Beispiele dafür bietet jede endliche projektive Ebene, indem man deren Punkte als Knoten und deren Geraden als Hyperkanten eines Hypergraphen auffasst.[15]

Anmerkung zur Historie

[Bearbeiten | Quelltext bearbeiten]

Das Lemma geht zurück auf ein Problem, welches K. Corrádi anlässlich des 1968er Miklós-Schweitzer-Wettbewerbs für Studenten gestellt hat.[16]

Quellen und Hintergrundliteratur

[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

Kreferences />


KKKategorie:Kombinatorik]] KKKategorie:Graphentheorie]] KKKategorie:Endliche Geometrie]] KKKategorie:Diskrete Mathematik]] KKKategorie:Satz (Mathematik)|Corrádi, Lemma von]]


===================================================================================================
[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]
  1. a b c Ian Anderson: Combinatorics of Finite Sets. 1987, S. 87 ff.
  2. a b c Béla Bollobás: Combinatorics. 1986, S. 143 ff.
  3. a b c d Konrad Engel: Sperner Theory. 1997, S. 265 ff.
  4. J. Marica, J. Schönheim: Differences of sets and a problem of Graham. In: Canad. Math. Bull. 12, S. 635–637
  5. a b c Bernhard Korte, Jens Vygen: Kombinatorische Optimierung. 2018, S. 122 ff.
  6. Korte/Vygen, op. cit., S. 124
  7. Korte/Vygen, op. cit., S. 125
  8. a b Martin Aigner: Diskrete Mathematik. 2006, S. 319
  9. Korte/Vygen, op. cit., S. 122
  10. a b Ronald L. Graham et al.: Ramsey Theory. 1980, S. 40 ff, S. 42–43, S. 172
  11. Jaroslav Nešetřil, Vojtěch Rödl: Partite Construction and Ramsey Space Systems. in: Mathematics of Ramsey Theory, Springer 1990, S. 98–112
  12. a b c d e Stasys Jukna: Extremal Combinatorics. 2011, S. 34 ff Referenzfehler: Ungültiges <ref>-Tag. Der Name „Jukna“ wurde mehrere Male mit einem unterschiedlichen Inhalt definiert.
  13. Stasys Jukna: Extremal Combinatorics. 2011, S. 37–38
  14. a b c László Lovász: Combinatorial Problems and Exercises. 1979, S. 78,130,446-447
  15. Stasys Jukna: Extremal Combinatorics. 2011, S. 37
  16. Stasys Jukna: Contests in Higher Mathematics: Miklós Schweitzer Competitions 1962–1991. 1996, S. 10, 123-124


  1. Selbstverständlich betrachtet man hier – wie üblich!– als versehen mit der Inklusionsrelation.
  2. ist die Anzahlfunktion.
  3. Ein Mengensystem mit der genannten Durchschnittseigenschaft bezeichnet man in der englischsprachigen mathematischen Fachliteratur als intersecting family.