It’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 and you wish to find **distinct** elements . (In our solitaire example, take to be the values of the cards in the 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 , the set contains at least elements. Hall’s theorem asserts that these conditions are also *sufficient*. Continue reading