\documentclass[12pt,twoside]{article}
\usepackage{latex-macros/course}

\begin{document}
\paper{sn3}{Supplemental Notes 3}{Hall's Marriage Theorem}

\subsection{Statements of Hall's Marriage Theorem}

\begin{theorem}
[Hall's Marriage Theorem]
\footnote{This material is from James
Tanton, \emph{Solve This, Math Activities for Students and Clubs},
Mathematical Association of America, c. 2001, pp. 181-3.}
Let $A_1, A_2, ..., A_n$ be sets with the property that the union of any
$k$ of them ($1 \leq k \leq n$) contains at least $k$ distinct elements.
Then it is possible to select $n$ distinct objects, one from each set.
\end{theorem}

Note: The condition placed on the sets in Hall's Marriage Theorem is not
trivial.  Potentially some sets could be empty or some elements could
appear in more than one set.

The reference to marriage arises from the following (terribly dated)
interpretation of the theorem: suppose $n$ women each make a list of the
names of men they would like to marry.  As long as any $r$ women mention
at least $r$ distinct names among them, $1 \leq r \leq n$, then it is
possible to find satisfactory marriage arrangements for all (assuming the
men are willing)!

Still another way to formulate Hall's Theorem is in terms of bipartite
graphs.  Assume wlog that the graphs are 2-colored black and white.  A
\emph{black perfect matching} is a mapping from each black node to an
adjacent white node, such that no two black nodes map to the same white
node, \ie the mapping is an injection.  Say a white node is \emph{adjacent
to a set} of black nodes if it is adjacent (connected by an edge) to at
least one of these black nodes.  A set of black nodes is called a
\emph{bottleneck} if its set of adjacent white nodes is strictly smaller
than it is.

Clearly, if there is a bottleneck, then there can't be a black perfect
matching.  Hall's Theorem says that this necessary condition is also
sufficient: if there is no bottleneck, then there is a black perfect
matching.

\subsection{Examples}

Hall's Marriage Theorem guarantees the possibility of selecting four cards
of distinct suits, one each from any four separate piles of 13 cards from
a standard deck of 52.

Likewise, there will always be 13 cards of distinct denominations, one
from each of 13 piles of four cards.  In this case, think of each pile as
the set of one to four the distinct card denominations that appear in that
pile.  Notice that among any $k$ piles of cards at least $k$ distinct
denominations appear---by the Generalized Pigeonholing Principle, there
are at least that many distinct denominations among any 4k cards.  Thus
the existence of one card of each denomination spread out across 13 piles
is assured by the Theorem.

Pulling in this big theorem is comforting---but not completely
satisfactory.  Although it assures us that these feats can always be
accomplished, it gives absolutely no indication of how to perform them!
Trial and error works well enough for the simple four-pile problem, but
not with 13 piles.  Is there a general procedure for pulling out a
selection of distinct denominations from 13 piles of four cards?

Fortunately there is: choose an arbitrary pile containing an Ace, then one
containing a two, and so on, doing this for as long as possible until you
get stuck.  Place these selected piles in a row.  Suppose you have
selected a total of ten piles, containing an Ace, and two through ten,
respectively.  This scenario leaves three untouched piles.  If any of the
12 cards in those three piles is a Jack, Queen, or King then you are not
really stuck; you can continue a little further (but perhaps not in the
usual sequential order).  If you are truly stuck, select any card in, say,
the 11th pile, and go to one of the ten piles that corresponds to the
number of that card.  Thus if you select a three you go to the third pile.
Turn a card in that third pile over (to make it conspicuous) and move to
the pile that corresponds to the number of that turned card.  Keep doing
this to create a chain of piles and turned cards, until you eventually hit
upon a pile that contains a card not in the initial list; in our case,
until we come upon a Jack, Queen, or King.  (Note: One can prove that you
will not fall into a closed loop of choices.)  Now shift all the piles one
place back along the chain of piles to obtain a configuration that allows
you to add one more pile to the initial list of ten.  Repeat this process
until you solve the puzzle completely.

\subsection{Proof by Induction}

This method of chain shifting is known in the literature as the technique
of \emph{augmenting paths} and is the basis for efficient procedures for
finding perfect matchings and related ``network flow'' problems.  This is
described in many combinatorics texts\footnote{For example, Ian Anderson
presents a procedural proof using augmenting paths in his book \emph{A
First Course in Combinatorial Mathematics}, Oxford Applied Mathematics and
Computer Science Series, Clarendon Press, Oxford, 1974.}, but we shall not
develop this method here.

Instead, we'll go back to the man-woman marriage terminology and give a
simple proof by:

\begin{proof}
Strong induction on the number, $n$, of women.

\textbf{Base case} ($n=1$).  If there is just a single woman with at least
one name on her list, then she can satisfactorily marry.  

\textbf{Induction step} ($n>1$).

\textbf{Case I.} Suppose these women's lists satisfy the stronger condition
that among any $r$ lists, $1 \leq r <n$, at least $r +1$ distinct names are
mentioned.  Select one woman.  She has at least two names on her list ($r =
1$ case).  Have her marry one of these men (Poindexter).  This leaves $n-1$
women to marry.

The lists possessed by these $n-1$ women have the property that among any
$r$ of them ($1 \leq r <n)$ at least $r + 1$ distinct names are mentioned.
One of these names could be Poindexter's who is no longer available for
marriage.  But we can still say that among any $r$ lists, at least $r$
distinct names of available men are mentioned.  This is all we need to
invoke the induction hypothesis for these remaining $n-1$ women.  Thus we
have a means to marry all $n$ women in this scenario.

\textbf{Case II.}  Suppose this stronger condition does not hold.  Thus
there is subgroup of $r_0$ women ($1 \leq r_0 < n$) such that among their
lists precisely $r_0$ distinct names are mentioned.  By the induction
hypothesis for $r_0 < n$, we can marry these women.  This leaves $m =
n-r_0 < n$ women to consider.

Is it true that among these $m$ women's lists any $r$ of them ($1 \leq r
\leq m$) mention at least $r$ distinct names of available men?  The answer
is yes!  If not, say some $r$ of these women mention fewer than $r$ available
men.  Then these $r$ women plus the $r_0$ women above have mentioned fewer
in $r_0 + r$ men in total.  This contradicts the property satisfied by
these lists.

Thus we can invoke the strong induction hypothesis for the remaining $m$
women and successfully have them marry as well.  This completes the proof
by induction.
\end{proof}

\begin{problem}
The induction proof can read as a recursive procedure to construct a
marriages for $n$ woman in terms of constructing marriages for smaller
sets of women.  Why isn't this procedure very efficient?
\end{problem}


\begin{problem}
A deck of cards is shuffled and dealt into 26 piles of two cards.  Is it
possible to select a black Ace from one pile, a Red ace from another, a
black two from a third, a red two from a fourth, and so on all the way
down to a black King and a red King from the two remaining piles?
\end{problem}


\end{document}
