Benutzer:Schojoha/Spielwiese/Kombinatorik

aus Wikipedia, der freien Enzyklopädie

Kriterium für Vollständige Unimodularität

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.[1]

Kriterium

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

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.

Korollar

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

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

Weiteres Kriterium

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[1] – 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:[4][5]

Eine Matrix ist genau dann vollständig unimodular, wenn für jeden Vektor sämtliche Eckpunkte des zu gehörigen Polyeders ganzzahlige Koordinaten haben.

Anmerkungen

  • 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.[1].[4]

Literatur

  • 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

rreferences />

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


Satz von Graham-Leeb-Rothshild

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.[6]

Formulierung des Satzes

Im Einzelnen besagt der Satz Folgendes:[6][7]

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

Einzelnachweise

Kreferences />


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



Satz von Lovász-Stein

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.[8]

Formulierung des Satzes

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

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

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:[9]

.

Quellen und Hintergrundliteratur

Einzelnachweise

rreferences />

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



Lemma von Corrádi

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.[8][10]

Formulierung des Lemmas

Im Einzelnen besagt das Lemma folgendes:[8][10]

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:
(*) .

Beweis

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:[8][10]

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.

Zusatz

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.[11]

Anmerkung zur Historie

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.[12]

Quellen und Hintergrundliteratur

  • K. Corrádi: Problem at Schweitzer competition. In: Matematikai Lapok. Band 20, 1969, S. 159–162.
  • Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer Verlag, Heidelberg, Dordrecht, London, New York 2011, ISBN 978-3-642-17363-9. MR2865719
  • László Lovász: Combinatorial Problems and Exercises (= Texts in Theoretical Computer Science). North-Holland Publishing Company, Amsterdam, New York, Oxford 1979, ISBN 0-444-85219-0. MR0537284
  • Gábor J. Székely (Hrsg.): Contests in Higher Mathematics. Miklós Schweitzer Competitions 1962-1991 (= Problem Books in Mathematics). Springer Verlag, New York (u. a.) 1996, ISBN 0-387-94588-1. MR1416130

Einzelnachweise

Kreferences />


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



Einzelnachweise und Fußnoten

  1. a b c Bernhard Korte, Jens Vygen: Kombinatorische Optimierung. 2018, S. 122 ff.
  2. Korte/Vygen, op. cit., S. 124
  3. Korte/Vygen, op. cit., S. 125
  4. a b Martin Aigner: Diskrete Mathematik. 2006, S. 319
  5. Korte/Vygen, op. cit., S. 122
  6. a b Ronald L. Graham et al.: Ramsey Theory. 1980, S. 40 ff, S. 42–43, S. 172
  7. Jaroslav Nešetřil, Vojtěch Rödl: Partite Construction and Ramsey Space Systems. in: Mathematics of Ramsey Theory, Springer 1990, S. 98–112
  8. 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.
  9. Stasys Jukna: Extremal Combinatorics. 2011, S. 37–38
  10. a b c László Lovász: Combinatorial Problems and Exercises. 1979, S. 78,130,446-447
  11. Stasys Jukna: Extremal Combinatorics. 2011, S. 37
  12. Stasys Jukna: Contests in Higher Mathematics: Miklós Schweitzer Competitions 1962–1991. 1996, S. 10, 123-124