The Mathematics of Marriage

linking-wedding-ringsIt’s been a while since my last blog post — one reason being that I recently got married.  In honor of that occasion, and my return to math blogging, here is a post on Hall’s Marriage Theorem.

Consider the following game of solitaire: you deal a deck of cards into 13 piles of 4 cards each, and your goal is to select one card from each pile so that no value (Ace through King) is repeated.  It is a beautiful mathematical fact that this can always been done, no matter how the cards were originally dealt!

We will deduce this from a more general result due to Philip Hall commonly known as Hall’s Marriage Theorem.  Suppose you are given finite sets A_1, A_2,\ldots, A_n and you wish to find distinct elements x_1 \in A_1,\ldots, x_n \in A_n.  (In our solitaire example, take A_j to be the values of the cards in the j^{\rm th} pile.)  Such a collection is called a transversal or SDR (system of distinct representatives).  Under what conditions is this possible?  Well, for a transversal to exist it is necessary that for each subset J \subset \{ 1,\ldots, n \}, the set A_J:= \bigcup_{j \in J} A_j contains at least \#J elements.  Hall’s theorem asserts that these conditions are also sufficient. Continue reading