Benutzer:Schojoha/Spielwiese/Kombinatorik

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.

Kriterium

Das Kriterium lässt sich angeben wie folgt:

Eine Matrix $A=(a_{ij})\in \mathbb {Z} ^{m\times n}\;(m,n\in \mathbb {N} )$ ist genau dann vollständig unimodular, wenn es für jede Teilmenge $R\subseteq \{1,...,m\}$ eine Zerlegung

$R_{1}\;{\dot {\cup }}\;R_{2}=R$

gibt derart, dass für jeden Index $j=1,...,n$ die Beziehung

$\sum _{i\in R_{1}}{a_{ij}}-\sum _{i\in R_{2}}{a_{ij}}\in \{-1,0,1\}$

erfüllt ist.

Korollar

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

Die Inzidenzmatrix $I_{G}$ eines endlichen ungerichteten Graphen $G$ ist vollständig unimodular genau dann, wenn $G$ 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 – 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:

Eine Matrix $A$ ist genau dann vollständig unimodular, wenn für jeden Vektor $b\in \mathbb {Z} ^{m}$ sämtliche Eckpunkte des zu $b$ gehörigen Polyeders $\{x\in \mathbb {R} ^{n}\mid x\geq 0\;,{A\cdot x}\leq b\}$ ganzzahlige Koordinaten haben.

Anmerkungen

• Eine $A\in \mathbb {Z} ^{m\times n}\;(m,n\in \mathbb {N} )$ heißt vollständig unimodular oder auch total unimodular, englisch totally unimodular , falls jede Unterdeterminante (und damit auch jedes Element) von $A$ gleich 0 oder gleich 1 oder gleich −1 ist..

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.

Formulierung des Satzes

Im Einzelnen besagt der Satz Folgendes:

Gegeben seien ein endlichen Körper $K$ sowie ein endlicher $K$-Vektorraum $V$ und ganze Zahlen $a,b,t$ mit $0\leq a\leq b$.

Für eine ganze Zahl $k\geq 0$ und einen beliebigen $K$-Vektorraum $X$ sei

${\binom {X}{k}}$

das Mengensystem der $k$-dimensionalen Unterräume von $X$ und

für eine ganze Zahl $n\geq 0$

$V^{n}=\prod _{i=1}^{n}{V}$

das aus $V$ mit sich selbst gebildete $n$-fache direkte Vektorraumprodukt.

Dann gilt:

Es gibt eine ganze Zahl $N_{0}\geq 0$ derart, dass für jede beliebige ganze Zahl

$N\geq N_{0}$

und jede Zerlegung

${\binom {V^{N}}{a}}={\mathcal {A_{1}}}\;{\dot {\cup }}\;\ldots \;{\dot {\cup }}\;{\mathcal {A_{t}}}$

der $a$-dimensionalen Unterräume von $V^{N}$ in $t$ Klassen

stets ein $b$-dimensionaler Unterraum $X\subseteq V^{N}$ existiert, so dass

${\binom {X}{a}}\subseteq {\mathcal {A_{i}}}$

für mindestens eine der Klassen ${\mathcal {A_{i}}}\;(i=1\;,\;\ldots ,\;t)$ gilt.

Quellen und Hintergrundliteratur

• Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer: Ramsey Theory (= Wiley-Interscience Series in Discrete Mathematics). Johns Wiley & Sons, New York, Chichester, Brisbane, Toronto 1980 (MR0591457). 
• Jaroslav Nešetřil, Vojtěch Rödl (Hrsg.): Mathematics of Ramsey Theory (= Algorithms and Combinatorics. Band 5). Springer Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo, Hong Kong, Barcelona 1990, ISBN 978-3-642-72907-2, doi:10.1007/978-3-642-72905-8. 

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.

Formulierung des Satzes

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

Seien $n,m,r,\delta ,\tau$ natürliche Zahlen.

Sei dazu $H=(X,{\mathcal {F}})$ ein endlicher Hypergraph, bestehend aus einer endlichen Knotenmenge $X$ mit $n$ Knoten und einem System ${\mathcal {F}}\subseteq 2^{X}$ von $m$ Hyperkanten.

Dabei sei vorausgesetzt, dass

jeder Knoten $x\in X$ mindestens den Grad $\deg _{H}(x)\geq \delta$ hat

und

jede Hyperkante aus höchstens $r$ Knoten besteht.

Weiter sei

$\tau =\min(\{|{\mathcal {E}}|\colon {\mathcal {E}}\subseteq {\mathcal {F}}\;,\;\bigcup {\mathcal {E}}=X\})$

die kleinste Anzahl von Hyperkanten, die benötigt wird, um die gesamte Knotenmenge $X$ zu überdecken.

Dann gilt:

$\tau \leq {\frac {m}{\delta }}\cdot {\bigl (}1+\ln(r){\bigr )}$.

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 $r$-uniformer Hypergraph, dessen $n$ Knoten bzw. $m$ Hyperkanten aufgefasst werden als Punkte bzw. Blöcke eines Blockplans mit der Eigenschaft, dass je $l$ verschiedene Punkte in mindestens einem der Blöcke enthalten sind (mit $n,r,l,m\in \mathbb {N}$). Sind die Kennziffern $n,r,l$ gegeben, so wird die kleinste unter den möglichen Anzahlen $m$ mit $M(n,r,l)$ bezeichnet.

Dabei ist stets

$M(n,r,l)\geq {\frac {n \choose l}{r \choose l}}$.

Mit dem Satz von Lovász-Stein lässt sich $M(n,r,l)$ nun nach oben abschätzen:

$M(n,r,l)\leq {\frac {n \choose l}{r \choose l}}\cdot {\bigl (}1+\ln {n \choose l}{\bigr )}$.

Quellen und Hintergrundliteratur

• 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. Lovász: On the ratio of optimal integral and fractional covers. In: Discrete Mathematics. Band 13, 1975, S. 383–390 ([1]).  MR0384578
• S. K. Stein: Two combinatorial covering theorems. In: Journal of Combinatorial Theory. Series A. Band 16, 1974, S. 391–397 ([2]).  MR0340062

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.

Formulierung des Lemmas

Im Einzelnen besagt das Lemma folgendes:

Seien $n,r,N$ natürliche Zahlen und $k$ eine ganze Zahl mit $n\geq r\geq k\geq 0$ .

Sei $H=(X,{\mathcal {A}})$ ein $r$-uniformer Hypergraph, bestehend aus einer $n$-elementigen Grundmenge $X$ und einer $N$-gliedrigen Familie ${\mathcal {A}}=(A_{1},A_{2},\ldots ,A_{N})$ von Hyperkanten.

Sei weiter vorausgesetzt, dass für alle Durchschnitte $A_{i}\cap A_{j}\;(i,j=1,2,\ldots ,N)$ je zweier Hyperkanten stets die Anzahlbedingung $|A_{i}\cap A_{j}|\leq k$ gegeben sei.

Dann gilt:

(*) $n\geq {\frac {Nr^{2}}{r+(N-1)k}}$.

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:

Festlegungen

(1) $d(x):={\deg _{H}}(x)=|\{i\in \{1,2,\ldots ,N\}\colon x\in A_{i}\}|\;(x\in X)$

(2) $J_{Y}:=\{(y,i)\in Y\times \{1,2,\ldots ,N\}\colon y\in A_{i}\}\;(Y\subseteq X)$

(3) $K:=\{(x,i,j)\in X\times \{1,2,\ldots ,N\}\times \{1,2,\ldots ,N\}\colon x\in A_{i}\cap A_{j}\}$

Doppeltes Abzählen

(4) $|J_{Y}|=\sum _{y\in Y}{d(y)}=\sum _{j=1}^{N}{|Y\cap A_{j}|}\;(Y\subseteq X)$

(5) $|K|=\sum _{x\in X}{d(x)^{2}}=\sum _{i,j=1}^{N}{|A_{i}\cap A_{j}|}=\sum _{i=1}^{N}{|J_{A_{i}}|}$

Abschätzung nach oben

Mit (4) ergibt sich insbesondere für $i=1,2,\ldots ,N$:

(6) $|J_{A_{i}}|=\sum _{j=1}^{N}{|A_{i}\cap A_{j}|}=|A_{i}|+\sum _{j=1,2,\ldots ,N \atop \;i\neq j}{|A_{i}\cap A_{j}|}\leq r+(N-1)k$

Also folgt aus (5) und (6):

(7) $\sum _{x\in X}{d(x)^{2}}\leq {N{\bigl (}r+(N-1)k{\bigr )}}$

Abschätzung nach unten

Vermöge der jensenschen Ungleichung ergibt sich:

(8) $\sum _{x\in X}{d(x)^{2}}=n\cdot \sum _{x\in X}{{\frac {1}{n}}\cdot d(x)^{2}}\geq n\cdot {\bigl (}\sum _{x\in X}{{\frac {1}{n}}\cdot d(x)}{\bigr )}^{2}=n\cdot {\frac {1}{n^{2}}}\cdot {\bigl (}\sum _{x\in X}{d(x)}{\bigr )}^{2}={\frac {1}{n}}\cdot {\bigl (}\sum _{x\in X}{d(x)}{\bigr )}^{2}$

Wiederum mit (4) und $Y=X$ folgt dann:

(9) $\sum _{x\in X}{d(x)^{2}}\geq {\frac {1}{n}}\cdot {|J_{X}|}^{2}={\frac {1}{n}}\cdot {\bigl (}\sum _{j=1}^{N}{|A_{j}|}{\bigr )}^{2}={\frac {(Nr)^{2}}{n}}={\frac {N^{2}r^{2}}{n}}$

Zusammenfassung

(7) und (9) zusammen ergeben dann:

(10) ${N{\bigl (}r+(N-1)k{\bigr )}}\geq {\frac {N^{2}r^{2}}{n}}$

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.

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.

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]]