Heiratssatz

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.[1] Er gilt als Ausgangspunkt der Matching-Theorie in der Graphentheorie.[2]

Problemstellung[Bearbeiten]

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

Folgende Interpretation führte zum weitverbreiteten Begriff Heiratssatz:[3]

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?[4]Eine Veranschaulichung des Heiratssatzes findet sich in dem Beitrag von Konrad Jacobs in den Selecta Mathematica I.[5]

Notwendige Bedingung[Bearbeiten]

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

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

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| \ge |I_0|.

Heiratssatz[Bearbeiten]

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.
  • Die Hall-Bedingung ist erfüllt.

Beweise und verwandte Sätze[Bearbeiten]

Ein direkter Beweis kann mittels Induktion über die Anzahl |I| der Mengen A_i geführt werden. Ein solcher Beweis findet sich in denProofs from THE BOOK von Martin Aigner und Günter Ziegler.[8] 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.[9]

Graphentheorische Darstellung[Bearbeiten]

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

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)|\ge |S|.

Verallgemeinerungen[Bearbeiten]

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

Verallgemeinerung nach Philip A. Ostrand[Bearbeiten]

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:[11][12][13]

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

Dann gilt:

Erfüllt \mathcal A die Hall-Bedingung , so ist
v_{\mathcal A} \geq \prod_{i=1}^n {max(1,|A_i| - i +1)} .


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

Verallgemeinerung nach Rado[Bearbeiten]

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 gegebenem 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?[16][17]

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:[18][19][20][21]

\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) \ge |H| erfüllt ist.[22]


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 \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[Bearbeiten]

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 [23][24].

Literatur[Bearbeiten]

Einzelnachweise und Fußnoten[Bearbeiten]

  1. P. Hall: On representation of subsets, Quart. J. Math. (Oxford) 10 (1935), Seiten 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: In: Amer. J. Math.. 71, S. 202 ff.
  4.  Aigner-Ziegler: S. 134-136.
  5.  Jacobs: Selecta Mathematica I. S. 103 ff.
  6.  Halder-Heise: S. 145-149.
  7. Dabei bezeichnet |I_0| die Anzahl der Elemente von I_0.
  8.  Aigner-Ziegler: S. 134-136.
  9.  Jungnickel, Konrad Jacobs: S. 27 ff.
  10. Winfried Hochstättler: Algorithmische Mathematik, Springer-Verlag (2010), ISBN 3-642-05421-8, Satz 4.36
  11.  Ostrand: In: J. Math. Anal. Appl.. 32, S. 1-4.
  12.  Halder-Heise: S. 145-149.
  13. Die Notwendigkeit des Erfülltseins der hallschen Bedingung wird hierbei als evident angesehen.
  14. Dies ist also die Anzahl der injektiven Auswahlfunktionen a \colon \{ 1 , \ldots , n \} \to A_1 \cup \ldots \cup A_n für \mathcal A = (A_1, \ldots, A_n). Hier gilt im Allgemeinen, wenn nichts weiter vorausgesetzt wird, v_{\mathcal A} = 0.
  15.  Halder-Heise: S. 149.
  16. X ist die gegebene endliche Grundmenge, in der alle A_i enthalten sind und  \mathcal U ist das zugehörige System der unabhängigen Teilmengen.
  17. Stellt man den Zusammenhang mit der oben beschriebenen injektiven Auswahlfunktion a \colon I \to \bigcup_{i \in I} A_i her, so ist (a_i)_{i \in I}= (a(i))_{i \in I}, wobei die Teilmenge A genau die a-Bildmenge von I ist, zu der sie auf diesem Wege in umkehrbar eindeutiger Beziehung steht.
  18.  Rado: In: Quart. J. Math. (Oxford). 13, S. 83 ff.
  19.  Aigner: S. 246 ff.
  20.  Mirsky: S. 93 ff.
  21.  Welsh: S. 97 ff.
  22. \rho \colon \mathcal P(X) \to \N_0 ist die zu \mathcal M gehörige Rangfunktion.
  23.  Welsh: S. 389 ff.
  24. Siehe hierzu auch Rados Auswahlprinzip.