Benutzer:Schojoha/Spielwiese/Matroidtheorie

Satz von Rado

Der Satz von Rado (englisch Rado's theorem oder Rado's transversal theorem) ist ein Lehrsatz der Matroidtheorie und gehört als solcher in das Gebiet der Diskreten Mathematik. Er geht auf eine Arbeit des deutschen Mathematikers Richard Rado aus dem Jahre 1942 zurück und stellt eine weitreichende Verallgemeinerung des berühmten Heiratssatzes von Philip Hall dar.

Formulierung des Satzes

Der Satz lässt sich folgendermaßen formulieren:

Gegeben seien eine nichtleere endliche Grundmenge $E$ und darauf ein Matroid $M$ mit der Rangfunktion $r\colon {\mathcal {P}}(E)\to \mathbb {N} _{0}$.

Weiter gegeben seien eine nichtleere endliche Indexmenge $I$ und dazu eine Mengenfamilie ${\mathcal {A}}=(A_{i})_{i\in I}$ von $E$-Teilmengen $A_{i}\subseteq E$.

Dann sind folgende Aussagen äquivalent:

(1) Die Mengenfamilie ${\mathcal {A}}$ besitzt eine Transversale, die in $M$ eine unabhängige Menge ist.

(2) Jede Teilmenge $J\subseteq I$ erfüllt in Hinblick auf die Rangfunktion $r$ die Ungleichung  $r{\bigl (}A(J){\bigr )}\geq |J|$.

Erläuterungen und Anmerkungen

• Eine Teilmenge $T\subseteq E$ ist eine Transversale der Mengenfamilie ${\mathcal {A}}$, wenn es eine bijektive Abbildung $\chi \colon T\to I$ gibt derart, dass für jedes $t\in T$ stets $t\in A_{\chi (t)}$ gilt.
• In der Matroidtheorie ist $A(J)$ für ein $J\subseteq I$ eine abkürzende Schreibung, wobei stets $A(J)=\bigcup _{j\in J}{A_{j}}$ gilt.
• Die obige Bedingung (2) nennen manche Autoren auch – in Analogie zur Hall-Bedingung (bzw. zu Hall’s Bedingung) im Heiratssatz – die Rado-Bedingung oder Rado’s Bedingung. Sie besagt, dass die Vereinigungsmenge von je $m$ der Teilmengen $A_{i}\subseteq E\;(m\in \mathbb {N} ,1\leq m\leq |I|)$ eine in $M$ unabhängige Menge mit mindestens $m$ Elementen umfasst.
• Fallen die Rangfunktion $r$ und die Anzahlfunktion $|\cdot |$ zusammen und sind damit alle Teilmengen $S\subseteq E$ unabhängig, so fällt die Rado-Bedingung mit der Hall-Bedingung zusammen und man erhält den Heiratssatz.
• Der Satz von Rado lässt sich ausdehnen auf den transfiniten Fall, der ein unendliches Matroid voraussetzt, also eine Matroidstruktur mit unendlicher Grundmenge $E$ und zusätzlichen Endlichkeitsbedingungen.
• Auf Richard Rado geht ein weiterer wichtiger Lehrsatz zurück, nämlich der Rado'sche Satz in der Ramseytheorie. Es ist in diesem Zusammenhang auch festzuhalten, dass der hiesige Satz nicht mit den auf den ungarischen Mathematiker Tibor Radó zurückgehenden Radó'schen Sätzen in der Analysis verwechselt werden sollte.

Folgerung

Aus dem Satz von Rado lässt sich viele Folgerungen gewinnen; so etwa die folgende:

Gegeben seien eine nichtleere endliche Grundmenge $E$ und darauf zwei nichtleere endliche Mengenfamilien ${\mathcal {A}}=(A_{i})_{i\in I}$ und ${\mathcal {B}}=(B_{i})_{i\in I}$ von Teilmengen $A_{i},B_{i}\subseteq E$ über einer gegebenen endlichen Indexmenge $I\neq \emptyset$.

Dann gilt:

Die beiden Mengenfamilien ${\mathcal {A}}$ und ${\mathcal {B}}$ besitzen eine gemeinsame Transversale genau dann, wenn $I$ für je zwei beliebige Indexteilmengen $J,K\subseteq I$ die Ungleichung  $|A(J)\cap B(K)|\geq |J|+|K|-|I|$ erfüllt ist.

Anwendung

Als Anwendung der obigen Folgerung erhält man ein Resultat über endliche Gruppen:

Gegeben seien eine endliche Gruppe $G$ und darin eine Untergruppe $H$ vom Index $m=(G\colon H)={\frac {|G|}{|H|}}$.

Dann gibt es zu den Links- und Rechtsnebenklassen von $G$ nach $H$ ein gemeinsames $m$-Tupel $(z_{1},\ldots ,z_{m})$ von Gruppenelementen mit

$z_{1}H\;{\dot {\cup }}\;z_{2}H\;{\dot {\cup }}\;\ldots \;{\dot {\cup }}\;z_{m}H=G=Hz_{1}\;{\dot {\cup }}\;Hz_{2}\;{\dot {\cup }}\;\ldots \;{\dot {\cup }}\;Hz_{m}$ .

Literatur

• Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1 (MR0460127). 
• Dieter Jungnickel: Transversaltheorie (= Mathematik und ihre Anwendungen in Physik und Technik. Band 39). Akademische Verlagsgesellschaft Geest & Portig K.-G., Leipzig 1982 (MR0706076). 
• Bernhard Korte, László Lovász, Rainer Schrader: Greedoids (= Algorithms and Combinatorics. Band 4). Springer Verlag, Berlin, Heidelberg 1991, ISBN 3-540-18190-3 (MR1183735). 
• James Oxley: Matroid Theory (= Oxford Graduate Texts in Mathematics. Band 21). 2. Auflage. Oxford University Press, Oxford 2011, ISBN 978-0-19-960339-8 (MR2849819). 
• Richard Rado: A theorem on independence relations. In: The Quarterly Journal of Mathematics. Oxford. Second Series. Band 13, 1942, S. 83–89 (MR0008250). 
• D. J. A. Welsh: Matroid Theory (= L.M.S. Monographs. Band 8). Academic Press, London, New York, San Francisco 1976, ISBN 0-12-744050-X (MR0427112). 
• Robin J. Wilson: Einführung in die Graphentheorie. Aus dem Englischen übersetzt von Gerd Wegner (= Moderne Mathematik in elementarer Darstellung. Band 15). Vandenhoeck & Ruprecht, Göttingen 1976 (MR0434854 – Englische Vorlage: Introduction to Graph Theory, Longman, London 1975). 

Einzelnachweise

rreferences />

KKKategorie:Diskrete Mathematik]] KKKategorie:Satz (Mathematik)|Rado (Matroidtheorie)]]

Unendliche Matroide

In der Matroidtheorie werden nicht nur Matroidstrukturen auf endlichen, sondern auch auf unendlichen Grundmengen betrachtet. In diesen Zusammenhang fällt auch das Konzept des (unendlichen) Unabhängigkeitsraums (englisch independence space). Es gibt mehrere Wege, solche Strukturen festzulegen. Ein direkter – und insbesondere aus Sicht der Algebra naheliegender – Weg setzt an mit dem Konzept des algebraischen Hüllenoperators.

Definition

Ist $S$ eine gegebene nichtleere (endliche oder unendliche) Grundmenge und ist $cl\colon {\mathcal {P}}(S)\to {\mathcal {P}}(S)\;,\;X\mapsto cl(X)\;,\;$ ein algebraischer Hüllenoperator, der zusätzlich noch der Austauscheigenschaft

(CL4) Für $A\subseteq S$ und $x,y\in S$ mit $y\in cl(A\cup x)-cl(A)$ gilt stets $x\in cl(A\cup y)$.

genügt, so nennt man das geordnete Paar $M=\left(S,cl\right)$ einen Unabhängigkeitsraums.

Ist der Hüllenoperator $cl$ nicht nur algebraisch, sondern ist darüber hinaus die stärkere Bedingung

(M) Für $A\subseteq S$ gibt es stets eine endliche Teilmenge $A_{0}\subseteq A$ mit $cl(A)=cl(A_{0})$.

erfüllt, so nennt man das geordnete Paar $M=\left(S,cl\right)$ ein Matroid.

Unabhängige Mengen, Basen, Kreise, Rangfunktion eines Matroids

eine Teilmenge $S$ und dazu ein Mengensystem ${\mathcal {I}}\subseteq {\mathcal {P}}(S)$ von $S$-Teilmengen. Für ${\mathcal {I}}$ wird nun gefordert, dass es folgender Bedingung (I4) genügt:

(I4) ${\mathcal {I}}$ hat endlichen Charakter.

Erfüllt ${\mathcal {I}}$ die oben zuerst genannten drei Unabhängigkeitsaxiome (I1), (I2) und (I3) und zudem das zuletzt aufgeführte vierte Unabhängigkeitsaxiom (I4), so nennt man das geordnete Paar $M=\left(E,{\mathcal {I}}\right)$ ein Matroid. Zu beachten ist, dass bei Vorliegen einer endlichen Grundmenge das Unabhängigkeitsaxiom (I4) trivialerweise erfüllt ist.

Weiter ist wichtig, dass ein endliches und ebenso ein unendliches Matroid $M$ stets die Eigenschaft hat, dass für jede endliche Teilmenge $F\subseteq E$ das geordnete Paar $M|_{F}=\left(F,{\mathcal {I|_{F}}}\right)$ mit ${\mathcal {I|_{F}}}\{I\in {\mathcal {I}}\colon I\subseteq F\}$ stets ein Matroid im obigen Sinne ist.

Literatur

• Martin Aigner: Combinatorial Theory (= Die Grundlehren der Mathematischen Wissenschaften. Band 234). Springer Verlag, Berlin, Heidelberg, New York 1979, ISBN 3-540-90376-3 (MR0542445). 
• Dieter Jungnickel: Transversaltheorie (= Mathematik und ihre Anwendungen in Physik und Technik. Band 39). Akademische Verlagsgesellschaft Geest & Portig K.-G., Leipzig 1982 (MR0706076). 
• D. J. A. Welsh: Matroid Theory (= L.M.S. Monographs. Band 8). Academic Press, London, New York, San Francisco 1976, ISBN 0-12-744050-X (MR0427112). 

Einzelnachweise

rreferences />

Heiratssatz

Der Heiratssatz, oder auch Satz von Hall, benannt nach Philip Hall, ist ein mathematischer Satz aus der Kombinatorik bzw. aus der Theorie der endlichen Mengen aus dem Jahre 1935. Er gilt als Ausgangspunkt der Matching-Theorie in der Graphentheorie.

Problemstellung

$1\in A_{1}$, $2\in A_{2}$, $5\in A_{3}$ und $7\in A_{4}$ ist eine mögliche Auswahl.

Die Mengen $A_{1},A_{2},A_{3}$ verletzen die Hall-Bedingungen, da deren Vereinigung nur 2 Elemente enthält.

Gegeben seien eine natürliche Zahl $n$, eine endliche Menge $X$ und endlich viele Teilmengen $A_{1},\ldots ,A_{n}$ von $X$, die nicht notwendigerweise alle verschieden sein müssen. Dann ist die Frage:

Gibt es ein „Vertretersystem“ (englisch system of distinct representatives), also Elemente $x_{i}\in A_{i}$   $(i=1,\ldots ,n)$ derart, dass die $x_{1},\ldots ,x_{n}$ alle verschieden sind?

Oder etwas allgemeiner:

Gegeben seien eine endliche Indexmenge $I$ und dazu eine Familie ${\mathcal {A}}=(A_{i})_{i\in I}$ endlicher Mengen. Dann ist die Frage:

Existiert für ${\mathcal {A}}$ eine „injektive Auswahlfunktion“

$a\colon I\to \bigcup _{i\in I}A_{i}$?

Interpretation

Folgende Interpretation führte zum weitverbreiteten Begriff Heiratssatz:

Gegeben seien eine endliche Menge $I$ heiratswilliger Frauen und dazu eine endliche Menge $X$ von mit diesen Frauen befreundeten Männern. Für jede Frau $i\in I$ sei $A_{i}\subseteq X$ die Menge der mit $i$ befreundeten Männer.

Dann ist die Frage:

Lassen sich die Frauen mit den Männern so verheiraten, dass jede Frau einen der mit ihr befreundeten Männer heiratet, ohne dass die Monogamieregel verletzt wird? Eine Veranschaulichung des Heiratssatzes findet sich in dem Beitrag von Konrad Jacobs in den Selecta Mathematica I.

Notwendige Bedingung

Eine solche Heirat verlangt, dass jede Frau $i$ einen Mann $x_{i}\in A_{i}$ zur Heirat auswählt, ohne dass dabei zwei Frauen denselben Mann heiraten. Dies muss nicht nur für die Gesamtheit der Frauen gelten, sondern auch für jede beliebige Teilmenge. Es ist also offensichtlich notwendig, dass je $k$ Frauen immer mit mindestens $k$ Männern befreundet sind.

Dies bedeutet: Für jede Teilmenge $I_{0}\subseteq I$ muss es in der Vereinigungsmenge $\bigcup _{i\in I_{0}}A_{i}$ immer mindestens $|I_{0}|$ Elemente geben.

Zur Existenz einer Auswahl der verlangten Art erhalten wir exakt die folgende notwendige Bedingung, die man auch die Hall-Bedingung oder hallsche Bedingung (englisch Hall’s condition) nennt:

Für jede Teilmenge $I_{0}\subseteq I$ ist $|\bigcup _{i\in I_{0}}A_{i}|\geq |I_{0}|$.

Heiratssatz

Der Heiratssatz sagt nun aus, dass die Hall-Bedingung für die Existenz einer Auswahl nicht nur notwendig, sondern auch hinreichend ist:

Es seien $I$ und ${\mathcal {A}}$ wie oben beschrieben. Dann sind folgende Aussagen äquivalent:

• Es existiert für ${\mathcal {A}}$ eine injektive Auswahlfunktion

$a\colon I\to \bigcup _{i\in I}A_{i},\quad i\mapsto x_{i}\in A_{i}$.

• Die Hall-Bedingung ist erfüllt.

Beweise und verwandte Sätze

Ein direkter Beweis kann mittels Induktion über die Anzahl $|I|$ der Mengen $A_{i}$ geführt werden. Ein solcher Beweis findet sich in den Proofs from THE BOOK von Martin Aigner und Günter Ziegler. Der Satz lässt sich ebenfalls direkt auf den Satz von Dilworth zurückführen. Wie sich zeigt, lassen sich der Heiratssatz, der Satz von Dilworth und der Satz von König leicht gegenseitig auseinander herleiten.

Graphentheoretische Darstellung

Die blauen Kanten bilden ein Matching, in dem alle Knoten aus A vorkommen.

Der Heiratssatz von Hall lässt sich wie folgt graphentheoretisch darstellen. Es sei $G$ ein bipartiter Graph mit Bipartition $\{A,B\}$. Ein Matching ist eine Menge von verschiedenen Kanten, die keine Knoten des Graphen gemeinsam haben. Für eine Teilmenge $S\subset A$ sei $N(S)$ die Menge aller zu $S$ benachbarten Punkte, die wegen der Bipartitheit notwendigerweise eine Teilmenge von $B$ sind. Die Frage nach einem Matching, in dem alle Knoten $a\in A$ vorkommen, ist die Frage nach einer Auswahl von paarweise verschiedenen Knoten $b_{a}\in N(\{a\})$ für alle $a\in A$. Der Heiratssatz lautet in diesem Kontext:

Für einen bipartiten Graphen mit Bipartition $\{A,B\}$ sind folgende Aussagen äquivalent:

• Es gibt ein Matching, in dem jeder Knoten aus $A$ vorkommt.
• Für alle Teilmengen $S\subseteq A$ gilt $|N(S)|\geq |S|$.

Verallgemeinerungen

In der Literatur zum Heiratssatz findet sich eine große Anzahl von Verallgemeinerungen und Erweiterungen unter verschiedenen Maßgaben:

Verallgemeinerung nach Philip A. Ostrand

Diese Verallgemeinerung (Satz von Ostrand) verschärft den Heiratssatz in der Weise, dass hier eine untere Schranke zur Abschätzung der Anzahl der Vertretersysteme angegeben wird, mit der sich der Heiratssatz unmittelbar ergibt:

Gegeben seien eine natürliche Zahl $n$ und dazu eine endliche Familie ${\mathcal {A}}=(A_{1},\ldots ,A_{n})$ endlicher Mengen. Diese sei in folgendem Sinne aufsteigend angeordnet:

$|A_{1}|\leq |A_{2}|\leq \ldots \leq |A_{n}|$

Die Anzahl der Vertretersysteme von ${\mathcal {A}}$ werde mit $v_{\mathcal {A}}$ bezeichnet.

Dann gilt:

Erfüllt ${\mathcal {A}}$ die Hall-Bedingung, so ist

$v_{\mathcal {A}}\geq \prod _{i=1}^{n}{\operatorname {max} \left(1,\ \left|A_{i}\right|-i+1\right)}$.

Die Verbindung zum Heiratssatz ergibt sich aus der Beobachtung, dass für $i=1,\ldots ,n$ durchweg ${max(1,|A_{i}|-i+1)}>0$ gilt. Der Satz von Ostrand sagt also insbesondere aus, dass bei Gültigkeit der Hall-Bedingung die Anzahl der Vertretersysteme mindestens $1$ sein muss, dass also in diesem Falle ein Vertretersystem existiert.

Wie der niederländische Mathematiker Jacobus Hendricus van Lint zeigen konnte, ist die oben genannte Schranke, wenn allein die Anzahlen $|A_{i}|$ bekannt sind, die bestmögliche.

Verallgemeinerung nach Rado

→ Hauptartikel: Satz von Rado

Diese Verallgemeinerung, welche auf Richard Rado zurückgeht, bringt den Heiratssatz in Verbindung mit der Matroidtheorie. Ausgangspunkt ist hier die folgende Frage:

Unter welchen Bedingungen existiert zu einem gegebenen Matroid ${\mathcal {M}}=(X;{\mathcal {U}})$ und zu einer gegebenen endlichen Familie ${\mathcal {A}}=(A_{i})_{i\in I}$ von $X$-Teilmengen ein „Vertretersystem“ $(a_{i})_{i\in I}$ derart, dass die Teilmenge $A=\{a_{i}:i\in I\}$ „unabhängig“ ist?

Eine solche Teilmenge $A$ nennt man auch eine „unabhängige Transversale“.

Kurz und knapp formuliert ist die in Rede stehende Frage also so zu stellen:

Unter welchen Bedingungen hat ein gegebenes Matroid ${\mathcal {M}}$ zu einer gegebenen endlichen Teilmengenfamilie ${\mathcal {A}}$ eine unabhängige Transversale?

Die Antwort auf diese Frage gibt der Satz von Rado, welcher folgendes besagt:

${\mathcal {M}}$ hat zu ${\mathcal {A}}$ eine unabhängige Transversale dann und nur dann, wenn für jede Teilfamilie ${\mathcal {A}}_{H}=(A_{i})_{i\in H}$   $(H\subseteq I)$ die Ungleichung $\rho (\bigcup _{i\in H}A_{i})\geq |H|$ erfüllt ist.

Die letzte Bedingung nennt man kurz Rados Bedingung (englisch Rado’s condition) oder auch Hall-Rado-Bedingung (englisch Hall-Rado condition) oder ähnlich. Sie bedeutet, dass für jedes $H\subseteq I$ die zugehörige Vereinigungsmenge eine unabhängige Teilmenge mit mindestens $|H|$ Elementen umfasst. Von ihr aus gelangt man zur Hall-Bedingung, indem man als Rangfunktion die Anzahlfunktion $|\cdot |\colon {\mathcal {P}}(X)\to \mathbb {N} _{0}$ nimmt, welche jeder Teilmenge $T\subseteq X$ die Anzahl ihrer Elemente $|T|$ zuordnet. In dem zur Anzahlfunktion gehörigen Matroid sind alle Teilmengen von $X$ unabhängig. So erweist sich der Heiratssatz als Spezialfall des Satzes von Rado.

Erweiterung auf den unendlichen Fall

Zum Heiratssatz und zum Satz von Rado (und ebenso zum Satz von Dilworth) gibt es erweiterte Versionen, welche (u. a.) den Fall einbeziehen, dass die Grundmenge unendlich ist. Die Beweise dieser transfiniten Versionen setzen allerdings üblicherweise als entscheidendes Hilfsmittel das Lemma von Zorn bzw. den Satz von Tychonoff ein, gehen also vom Auswahlaxiom aus.

Literatur

• Martin Aigner, Günter M. Ziegler: Proofs from THE BOOK. Springer Verlag, Berlin (u. a.) 1991, ISBN 3-540-63698-6. 
• Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1 (MR0460127). 
• Heinz-Richard Halder, Werner Heise: Einführung in die Kombinatorik. Hanser Verlag, München (u. a.) 1976, ISBN 3-446-12140-4 (MR0498160). 
• Konrad Jacobs (Hrsg.): Selecta Mathematica I (= Heidelberger Taschenbücher. Band 49). Springer-Verlag, Berlin / Heidelberg / New York 1969, S. 103–141. 
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). 2., völlig neu bearbeitete und erweiterte Auflage. de Gruyter, Berlin (u. a.) 2004, ISBN 3-11-016727-1. 
• Dieter Jungnickel: Transversaltheorie (= Mathematik und ihre Anwendungen in Physik und Technik. Band 39). Akademische Verlagsgesellschaft Geest & Portig K.-G., Leipzig 1982 (MR0706076). 
• L. Lovász, M. D. Plummer: Matching Theory (= North-Holland Mathematics Studies. Band 121). North-Holland, Amsterdam (u. a.) 1986, ISBN 0-444-87916-1 (MR0859549). 
• Heinz Lüneburg: Kombinatorik (= Elemente der Mathematik vom höheren Standpunkt aus. Band 6). Birkhäuser Verlag, Basel / Stuttgart 1971, ISBN 3-7643-0548-7 (MR0335267). 
• Leonid Mirsky: Transversal Theory (= North-Holland Mathematics Studies. Band 121). Academic Press, New York / London 1971, ISBN 0-12-498550-5 (MR0282853). 
• L. Mirsky, Hazel Perfect: Systems of representatives. In: J. Math. Anal. Appl. Band 15, 1966, S. 520–568 (sciencedirect.com; MR0204300). 
• Philip. A. Ostrand: Systems of distinct representatives, II. In: J. Math. Anal. Appl. Band 32, 1970, S. 1–4 (ac.els-cdn.com [PDF]).  MR0280385.
• R. Rado: A theorem on independence relations. In: Quart. J. Math. (Oxford). Band 13, 1942, S. 83–89 (qjmath.oxfordjournals.org [PDF] MR0008250). 
• Philip F. Reichmeider: The Equivalence of Some Combinatorial Matching Theorems. Polygonal Publishing House, Washington NJ 1984, ISBN 0-936428-09-0 (MR0781348). 
• D. J. A. Welsh: Matroid Theory (= L.M.S. Monographs. Band 8). Academic Press, London (u. a.) 1976, ISBN 0-12-744050-X (MR0427112). 
• Hermann Weyl: Almost periodic invariant vector sets in a metric vector space. In: Amer. J. Math. Band 71, 1949, S. 178–205, JSTOR:2372104 (MR0028530). 

Einzelnachweise und Anmerkungen

KKKategorie:Diskrete Mathematik]] KKKategorie:Satz (Graphentheorie)]] KKKategorie:Satz (Mathematik)|Hall, Satz von]]