Heiratssatz/inputs/heiratssatz.tex

Man stelle sich vor, wir haben eine Menge $M$ von Männern und eine Menge  $F$
von Frauen, die wir verheiraten wollen.
Jeder Mann gibt zudem an, welche Frauen er möglicherweise heiraten wollen
würde.
Wann ist es möglich, die Männer mit den Frauen zu verheiraten, sodass jeder
Mann eine seiner Wunschfrauen bekommt, und natürlich keine Frau doppelt
verheiratet wird?
\\
Wir können dies graphentheoretisch formulieren, indem wir einen bipartiten
Graphen zeichenn, deren Hälften die Männer und Frauen sind, wobei wir einen
Knoten zwischen einem Mann und einer Frau zeichen, wenn der Mann diese Frau
potenziell heiraten will. 'Zu verheiraten' heißt hier also, eine Menge von
Kanten auszuwählen, sodass jeder Mann eine entsprechende Kante hat, und jede
Frau höchstens eine. \\
Man kann nun mehr oder weniger offensichtliche Bedingungen feststellen, die
gelten müssen, hierzu zählen:
\begin{itemize}
    \item
          Jeder Mann sollte mindestens eine Frau mögen.
    \item
          Es sollte mindestens so viele Frauen wie Männer geben
    \item
          Wenn zwei Männer jeweils nur eine Frau mögen, so darf dies nicht die gleich
          sein.
\end{itemize}
Nach einer Weil könnte man auch auf folgendes kommen:
\begin{itemize}
    \item
          Für
          Jede Teilmenge $N\subset M$ von (manchen) Männern, muss es mindestens
          $\abs{N}
          $ viele Frauen geben, die von einem dieser Männer gemocht wird.
          Nehmen wir nämlich an, dass wir die Männer verheiraten können, so sind dies
          (mindestens) die $\abs{N} $ vielen Partnerinnen der Männer.
\end{itemize}
Diese Bedingung nennt man auch Halls Heiratsbedingung, benannt nach Paul Hall,
der diesen Sachverhalt das erste Mal untersuchte.
Das überraschende ist nun, dass diese Bedingung bereits ausreicht:
\begin{theorem}[Hall, 1935] Gegeben sei ein bipartiter Graph mit den
    Knotenmengen $M$ und $F$.
    Dann gibt es ein vollständiges Matching von den Männern (in die Frauen) genau
    dann, wenn für jede Teilmenge  $M'\subset M$ gilt, dass $\abs{M'}
    \leq
    \abs{N(M')}  $.
\end{theorem}
\begin{remark}
    Wir bezeichnen hierbei mit $N(M')$ die Nachbarschaft der Knotenmenge  $M'$,
    also  alle Knoten, die von $M'$ mit genau einer Kante erreichbar sind (in
    unserem fall genau die Frauen).
\end{remark}
\begin{proof}
    Starke Induktion nach der Anzahl der Männer.
    Für $n=1$ gibt es nichts zu zeigen.
    Betrachte nun  $n+1$ Männer  $m_1,\ldots m_{n+1}$ und
    setze $M=
    \left\{m_1,\ldots,m_n\right\} $.
    Wir wollen 2 Fälle unterscheiden:
    \begin{itemize}
        \item
              \textbf{Fall 1}: Die
              Hall-Bedingung ist für Teilmengen von $M$ immer 'lasch' (nicht scharf), d.h.
              für jede Teilmenge  $M'\subset M$ gilt $\abs{N(M')} \geq
              \abs{M'}+1 $ . \\
              Dann verheiraten wir $m_{n+1}$ mit einer seiner
              Wunschpartnerinnen und stellen fest, dass nach Induktion die Menge $M$ die
              Hall-Bedingung (auch mit der fehlenden Frau) immer noch erfüllt, Induktion
              liefert uns ein Matching.
        \item
              \textbf{Fall 2}: Dies ist nicht der Fall, d.h. es gibt eine Teilmenge
              $M'\subset M$, sodass $\abs{ N(M')} = \abs{M'} $ ist.
              Dann verheiraten wir zunächst mittels Induktion die Männer aus $M'$.
              Es bleibt zu überprüfen, dass die Hall-Bedingung nun noch für alle Teilmengen
              von  $M\setminus M'$ gilt, wobei bereits verheiratete Frauen nicht mehr zur
              Nachbarschaft zählen.
              Nehmen wir also an, es gibt eine Menge von $k$ Männern, die nicht aus  $M'$
              sind, sodass es  $x<k$ viele Frauen gibt, die diese heiraten können.
              Dann können diese  $K$ Männer zusammen mit den Männern aus  $M'$ (also	$k+
              \abs{M'} $ viele Männer) zusammen höchstens
              $x+\abs{N(M')}  = x+\abs{M'} $
              viele Frauen heiraten, und somit ist die Hall-Bedingung für die ursprüngliche
              Belegung auch verletzt.
              Somit hält sie immer noch, und per Induktion verheiraten wir auch die
              restlichen Männer und sind fertig.
    \end{itemize}
\end{proof}
Folgende Aufgaben können mit Halls Heiratssatz nun gelöst werden:
\begin{example}
    \begin{enumerate}[label=\protect\circled{\arabic*}]
        \item
              Wir
              betrachten ein herkömmliches Kartenset $2,3,\ldots,B,D,K,A$ in 4 Farben,
              mischen dieses, und verteilen dieses auf Stapel zu je 4 Karten.
              Ist es immer möglich, aus jedem der Stapel eine Karte zu wählen, sodass wir
              jeden Karten\textit{wert} genau einmal gewählt haben?
        \item
              Auf einem Blatt Papier werden auf der Vorder- und Rückseite jeweils $n$
              Polygone gezeichnet, die die gleiche Fläche haben.
              Ist es immer möglich,  $n$ Löcher in das Papier zu stechen, sodass auf beiden
              Seiten (gleichzeitig) jede der Flächen genau ein Loch hat?
        \item
              Gegeben seien  $n$ Teilmengen  $S_1,\ldots S_n$ (evtl. leer) von $\left
              \{1,\ldots,n\right\} $.
              Für jedes $k\leq n$ wissen wir, dass die Vereinigung von $k$ der $n$ Mengen
              mindestens  $k$ Elemente enthält.
              Zeige, dass es eine Permutation $\pi$ gibt, sodass $\pi(i) \in
              S_i$ für
              $i=1,\ldots,n$.
              (Also dass wir aus jeder Menge einen Wert wählen können, sodass wir jeden Wert
              genau einmal gewählt haben).
        \item
              (IMO SL 2010, C2)
              Auf einem Planeten gibt es $2^n$ viele Länder, wobei  $n\geq 4$ gelte.
              Jedes Land hat eine Flagge, die aus $n$ blauen oder roten Einheitsquadraten in
              einer (horizontalen) Reihe besteht, wobei keine 2 Länder die gleiche Flagge
              besitzen.
              Wir nennen eine Menge $M$ von  $n$ Ländern  $fancy$, wenn wir ihre Flaggen
              (untereinander) so anordnen können, sodass die Diagonale des resultierdenden
              $n\times n$-Quadrats einfarbig ist.
              Eine Menge von Ländern heiße inspirierend, wenn diese eine fancy Teilmenge
              besitzt.
              Man bestimme das kleinste $m$, sodass jede Menge von mindestens  $m$ Ländern
              inspirierend ist.
    \end{enumerate}
\end{example}