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 endliche Menge $X$ und eine endliche Anzahl $A_{1},\ldots ,A_{n}$ von Teilmengen aus $X$, die nicht notwendigerweise alle verschieden sein müssen. Kann man Elemente $x_{i}\in A_{i}$ derart auswählen, dass die $x_{1},\ldots ,x_{n}$ alle verschieden sind?

Folgende folkloristische Interpretation führte zum weit-verbreiteten Begriff Heiratssatz. Gegeben seien eine Menge $\{1,\ldots ,n\}$ heiratswilliger Frauen und eine Menge $X$ von dazu in Frage kommenden Männern. Für jede Frau $i$ sei $A_{i}\subset X$ die Menge der von $i$ bevorzugten Männer. Kann man nun eine Massenhochzeit so einrichten, dass alle Frauen einen bevorzugten Mann heiraten? Für jede Frau $i$ ist dazu ein Mann $x_{i}\in A_{i}$ zu wählen und bei vorherrschender Monogamie können keine zwei Frauen denselben Mann heiraten, das heißt die ausgewählten Männer $x_{1},\ldots ,x_{n}$ müssen paarweise verschieden sein.

Wenn es eine Auswahl $x_{i}\in A_{i}$ von der verlangten Art gibt, so muss es für jede Teilmenge $I\subseteq \{1,\ldots ,n\}$ zu jedem Index $i\in I$ ein geeignetes $x_{i}\in A_{i}$ geben, so dass die $x_{i},i\in I$ paarweise verschieden sind, insbesondere muss es also in $\bigcup _{i\in I}A_{i}$ wenigstens $|I|$ viele Elemente geben, wobei $|I|$ die Anzahl der Elemente in $I$ bezeichnet. Zur Existenz einer Auswahl der verlangten Art erhalten wir also folgende notwendige Bedingungen, die man auch die Hall-Bedingungen nennt:

Für jede Teilmenge $I\subseteq \{1,\ldots ,n\}$ ist $|\bigcup _{i\in I}A_{i}|\geq |I|$.

Heiratssatz

Der Heiratssatz sagt aus, dass die Hall-Bedingungen für die Existenz einer Auswahl auch hinreichend sind:

Es seien $X$ eine endliche Menge und $A_{1},\ldots ,A_{n}$ Teilmengen von $X$. Dann sind folgende Aussagen äquivalent:

• Es gibt $x_{i}\in A_{i}$ derart, dass die $x_{1},\ldots ,x_{n}$ paarweise verschieden sind.
• Die Hall-Bedingungen sind erfüllt.

Ein Beweis kann mittels Induktion über die Anzahl $n$ der Mengen $A_{i}$ geführt werden. Ein kurzer Beweis findet sich in Proofs from THE BOOK von Martin Aigner und Günter Ziegler.

Graphentheorie

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

Der Heiratssatz von Hall lässt sich wie folgt graphentheoretisch deuten. 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|$.

Siehe auch

Der Heiratssatz ist eng verwandt mit

• Satz von Dilworth
• Satz von König,

das heißt diese drei Sätze lassen sich leicht gegenseitig auseinander herleiten.

Eine schöne Veranschaulichung des Heiratssatzes findet sich bei Konrad Jacobs.

Erweiterung auf den unendlichen Fall

Zum Heiratssatz (und ebenso zum Satz von Dilworth) gibt es eine erweiterte Version, welche den Fall einbezieht, dass die Grundmenge unendlich ist. Der Beweis dieser transfiniten Version setzt allerdings üblicherweise als entscheidendes Hilfsmittel das Lemma von Zorn ein, geht also vom Auswahlaxiom aus .

Literatur

• 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 und 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 und 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 ([1]).  MR0204300
• Philip F. Reichmeider: The Equivalence of Some Combinatorial Matching Theorems. Polygonal Publishing House, Washington, NJ 1984, ISBN 0-936428-09-0.  MR0781348