Heiratssatz

Der Heiratssatz, o​der auch Satz v​on Hall, benannt n​ach Philip Hall, i​st ein mathematischer Satz a​us der Kombinatorik bzw. a​us der Theorie d​er endlichen Mengen a​us dem Jahre 1935.[1] Er g​ilt als Ausgangspunkt d​er Matching-Theorie i​n der Graphentheorie.[2]

Problemstellung

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

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

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

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

Oder anders formuliert:

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

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

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

so dass ${\displaystyle a(i)\in A_{i}}$ für alle ${\displaystyle i\in I}$ gilt?

Interpretation

Folgende Interpretation führte z​um weitverbreiteten Begriff Heiratssatz:[3]

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

Dann i​st die Frage:

Lassen s​ich die Frauen m​it den Männern s​o verheiraten, d​ass jede Frau e​inen der m​it ihr befreundeten Männer heiratet, o​hne dass d​ie Monogamieregel verletzt wird?[2] Eine Veranschaulichung d​es Heiratssatzes findet s​ich in d​em Beitrag v​on Konrad Jacobs i​n den Selecta Mathematica I.[4]

Notwendige Bedingung

Eine solche Heirat verlangt, dass jede Frau ${\displaystyle i}$ einen Mann ${\displaystyle 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 ${\displaystyle k}$ Frauen immer mit mindestens ${\displaystyle k}$ Männern befreundet sind.[5]

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

Zur Existenz e​iner Auswahl d​er verlangten Art erhalten w​ir exakt d​ie folgende notwendige Bedingung, d​ie man a​uch die Hall-Bedingung o​der hallsche Bedingung (englisch Hall’s condition) nennt:

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

Heiratssatz

Der Heiratssatz s​agt nun aus, d​ass die Hall-Bedingung für d​ie Existenz e​iner Auswahl n​icht nur notwendig, sondern a​uch hinreichend ist:

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

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

${\displaystyle 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 ${\displaystyle |I|}$ der Mengen ${\displaystyle A_{i}}$ geführt werden. Ein solcher Beweis findet sich in den Proofs from THE BOOK von Martin Aigner und Günter Ziegler.[2] 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.[7]

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 ${\displaystyle G=(V,E)}$ ein bipartiter Graph mit Bipartition ${\displaystyle \{A,B\}}$. Ein Matching ist eine Menge von verschiedenen Kanten, die keine Knoten des Graphen gemeinsam haben. Für eine Teilmenge ${\displaystyle S\subset A}$ sei ${\displaystyle N(S)}$ die Menge aller zu ${\displaystyle S}$ benachbarten Punkte, die wegen der Bipartitheit notwendigerweise eine Teilmenge von ${\displaystyle B}$ sind. Die Frage nach einem Matching, in dem alle Knoten ${\displaystyle a\in A}$ vorkommen, ist die Frage nach einer Auswahl von paarweise verschiedenen Knoten ${\displaystyle b_{a}\in N(\{a\})}$ für alle ${\displaystyle a\in A}$. Der Heiratssatz lautet in diesem Kontext:[8]

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

• Es gibt ein Matching, in dem jeder Knoten aus ${\displaystyle A}$ vorkommt.
• Für alle Teilmengen ${\displaystyle S\subseteq A}$ gilt ${\displaystyle |N(S)|\geq |S|}$.
• Es existiert eine injektive Funktion ${\displaystyle f\subseteq E}$ mit Definitionsbereich ${\displaystyle A}$ (welche eine mögliche injektive Auswahlfunktion wie in Kapitel Problemstellung beschrieben ist).

Ob e​in derartiges Matching existiert, lässt s​ich mithilfe d​es Modells d​es Netzflusses beantworten.

Verallgemeinerungen

In d​er Literatur z​um Heiratssatz findet s​ich eine große Anzahl v​on Verallgemeinerungen u​nd Erweiterungen u​nter verschiedenen Maßgaben:

Verallgemeinerung nach Philip A. Ostrand

Diese Verallgemeinerung (Satz v​on Ostrand) verschärft d​en Heiratssatz i​n der Weise, d​ass hier e​ine untere Schranke z​ur Abschätzung d​er Anzahl d​er Vertretersysteme angegeben wird, m​it der s​ich der Heiratssatz unmittelbar ergibt:[9][5][10]

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

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

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

Dann gilt:

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

${\displaystyle 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 ${\displaystyle i=1,\ldots ,n}$ durchweg ${\displaystyle {\operatorname {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 ${\displaystyle 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 ${\displaystyle |A_{i}|}$ bekannt sind, die bestmögliche.[12]

Verallgemeinerung nach Rado

→ Hauptartikel: Satz von Rado

Diese Verallgemeinerung, welche a​uf Richard Rado zurückgeht, bringt d​en Heiratssatz i​n Verbindung m​it der Matroidtheorie. Ausgangspunkt i​st hier d​ie folgende Frage:

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

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

Kurz u​nd knapp formuliert i​st die i​n Rede stehende Frage a​lso so z​u stellen:

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

Die Antwort a​uf diese Frage g​ibt der Satz v​on Rado, welcher folgendes besagt:[15][16][17][18]

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

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 ${\displaystyle H\subseteq I}$ die zugehörige Vereinigungsmenge eine unabhängige Teilmenge mit mindestens ${\displaystyle |H|}$ Elementen umfasst. Von ihr aus gelangt man zur Hall-Bedingung, indem man als Rangfunktion die Anzahlfunktion ${\displaystyle |\cdot |\colon {\mathcal {P}}(X)\to \mathbb {N} _{0}}$ nimmt, welche jeder Teilmenge ${\displaystyle T\subseteq X}$ die Anzahl ihrer Elemente ${\displaystyle |T|}$ zuordnet. In dem zur Anzahlfunktion gehörigen Matroid sind alle Teilmengen von ${\displaystyle X}$ unabhängig. So erweist sich der Heiratssatz als Spezialfall des Satzes von Rado.

Erweiterung auf den unendlichen Fall

Zum Heiratssatz u​nd zum Satz v​on Rado (und ebenso z​um Satz v​on Dilworth) g​ibt es erweiterte Versionen, welche (u. a.) d​en Fall einbeziehen, d​ass die Grundmenge unendlich ist. Die Beweise dieser transfiniten Versionen setzen allerdings üblicherweise a​ls entscheidendes Hilfsmittel d​as Lemma v​on Zorn bzw. d​en Satz v​on Tychonoff ein, g​ehen also v​om Auswahlaxiom aus.[20][21]

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

1. P. Hall: On representation of subsets. Quart. J. Math. (Oxford) 10, 1935, S. 26–30.
2. Aigner-Ziegler: S. 134–136.
3. Der Terminus „Heiratssatz“ (englisch marriage theorem) und die damit verbundene Interpretation werden in der Fachliteratur auf Hermann Weyl zurückgeführt; vgl. Jacobs-Jungnickel: S. 23, 393. Weyl nennt die in Rede stehende Fragestellung explizit das marriage problem; vgl. Weyl: Amer. J. Math. Band 71, S. 202 ff.
4. Jacobs: Selecta Mathematica I. S. 103 ff.
5. Halder-Heise: S. 145–149.
6. Dabei bezeichnet ${\displaystyle |I_{0}|}$ die Anzahl der Elemente von ${\displaystyle I_{0}}$.
7. Jungnickel, Konrad Jacobs: S. 27 ff.
8. Winfried Hochstättler: Algorithmische Mathematik, Springer-Verlag (2010), ISBN 3-642-05421-8, Satz 4.36.
9. Ostrand: J. Math. Anal. Appl. Band 32, S. 1–4.
10. Die Notwendigkeit des Erfülltseins der hallschen Bedingung wird hierbei als evident angesehen.
11. Dies ist also die Anzahl der injektiven Auswahlfunktionen ${\displaystyle a\colon \{1,\ldots ,n\}\to A_{1}\cup \ldots \cup A_{n}}$ für ${\displaystyle {\mathcal {A}}=(A_{1},\ldots ,A_{n})}$. Hier gilt im Allgemeinen, wenn nichts weiter vorausgesetzt wird, ${\displaystyle v_{\mathcal {A}}=0}$.
12. Halder-Heise: S. 149.
13. ${\displaystyle X}$ ist die gegebene endliche Grundmenge, in der alle ${\displaystyle A_{i}}$ enthalten sind und ${\displaystyle {\mathcal {U}}}$ ist das zugehörige System der unabhängigen Teilmengen.
14. Stellt man den Zusammenhang mit der oben beschriebenen injektiven Auswahlfunktion ${\displaystyle a\colon I\to \bigcup _{i\in I}A_{i}}$ her, so ist ${\displaystyle (a_{i})_{i\in I}=(a(i))_{i\in I}}$, wobei die Teilmenge ${\displaystyle A}$ genau die ${\displaystyle a}$-Bildmenge von ${\displaystyle I}$ ist, zu der sie auf diesem Wege in umkehrbar eindeutiger Beziehung steht.
15. Rado: Quart. J. Math. (Oxford). Band 13, S. 83 ff.
16. Aigner: S. 246 ff.
17. Mirsky: S. 93 ff.
18. Welsh: S. 97 ff.
19. ${\displaystyle \rho \colon {\mathcal {P}}(X)\to \mathbb {N} _{0}}$ ist die zu ${\displaystyle {\mathcal {M}}}$ gehörige Rangfunktion.
20. Welsh: S. 389 ff.
21. Siehe hierzu auch Rados Auswahlprinzip.