Hall's marriage theorem is a result in combinatorics that specifies when distinct elements can be chosen from a collection of overlapping finite sets. It is equivalent to several beautiful theorems in combinatorics, including Dilworth's theorem. The name comes from an application to matchmaking: given a list of potential matches among an equal number of brides and grooms, the theorem gives a necessary and sufficient condition on the list for everyone to be married to an agreeable match.
Suppose I have gifts (labeled ) to give at Christmas, to friends (Alice, Bob, Charles, Dot, Edward). Can I distribute one gift to each person so that everyone gets something they want?
Certainly this depends on the preferences of my friends. If none of them like any of the gifts, then I am out of luck. But even if they all like some of the gifts, I may still not be able to give them out satisfactorily. For instance, if none of them like gifts or , then I will have only gifts to give to my friends. Or suppose that
Alice wants: 1,3
Bob wants: 2,4,5,6
Charles wants: 2,3
Dot wants: 1,2,3
Edward wants: 2
There is still no way to distribute the gifts to make everyone happy. In fact, notice that I have four friends (Alice, Charles, Dot, Edward) who only want one of the first three gifts, which makes it clear that the problem is impossible.
It turns out, however, that this is the only way for the problem to be impossible. As long as there isn't a subset of the friends that collectively likes fewer gifts than there are friends in the subset, there will always be a way to give everyone something they want. This is the crux of Hall's marriage theorem.
Let be a family of finite sets. Here is allowed to be infinite, and elements in can be repeated. A transversal for is a set and a bijection such that for all .
So a transversal consists of a choice of an element in each of the sets in ; the point is that the elements chosen must be unique even if the sets overlap. When is finite, a transversal for is often given as an ordered tuple of elements of the sets in .
Let . Then is a transversal of : pick from the first set, from the second set, from the third set. Note that if instead we try to pick from the first set and from the second set, there is no choice of element from the third set that leads to a transversal.
(Hall's Marriage Theorem) Let be a finite family of finite sets. Suppose that for every subfamily of sets in , the number of subsets in is less than or equal to the total number of elements in those subsets: Then has at least one transversal.
(1) The condition given in the theorem is clearly necessary for the existence of a transversal, because any transversal must include distinct elements from the sets in , so those sets must together contain at least elements.
(2) The condition given in the theorem is generally called the "marriage condition." So Hall's Marriage Theorem says that has a transversal if and only if it satisfies the marriage condition.
Suppose there are women and men, all of whom want to get married to someone of the opposite sex. Suppose further that the women each have a list of the men they would be happy to marry, and that every man would be happy to marry any woman who is happy to marry him, and that each person can only have one spouse.
In this case, Hall's marriage theorem says that the men and women can all be paired off in marriage so that everyone is happy, if and only if the marriage condition holds: if in any group of women, the total number of men who are acceptable to at least one of the women in the group is greater than or equal to the size of the group.
Again, it is clear that this condition is necessary. Hall's marriage theorem is that it is sufficient as well. To see why the theorem applies in this case, let be the set of men that the th woman would be happy to marry; then the marriage condition in the previous paragraph is the same as the marriage condition on the family of sets . So there is a transversal , which is a choice of an acceptable man for each woman.
Hall's marriage theorem can be restated in a graph theory context.
A bipartite graph is a graph where the vertices can be divided into two subsets and such that all the edges in the graph connect vertices from to vertices in . (So none of the vertices in or in are connected to each other.)
A matching on a graph is a choice of edges with no common vertices. It covers a set of vertices if each vertex in is an endpoint of one of the edges in the matching.
Suppose a bipartite graph has parts and . Hall's marriage theorem says that there is a matching that covers if and only if, for every subset of , the number of edges in the graph with endpoints in is .
Shuffle a deck of cards and deal piles of four cards each. Show that there is always a way to choose a card from each pile in such a way that the cards chosen contain one card of each rank (one ace, one king, etc.)
Consider the family of sets consisting of the ranks of the cards in pile . A subfamily consists of subsets, which contains the ranks of cards. Since there are only four cards of each rank, there must be at least distinct ranks. So the marriage condition is satisfied, so there is a transversal by Hall's marriage theorem. This transversal is exactly what the problem asks for.
(Putnam 2012 B3) A round-robin tournament of teams lasted for days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the games. Over the course of the tournament, each team played every other team exactly once. Can one necessarily choose one winning team from each day without choosing any team more than once?
The answer is yes. On the th day, let be the set of winning teams. Each set has elements. To show that a transversal exists, we must show that the marriage condition holds.
Suppose it does not--so there are sets whose union contains less than elements; that is, suppose there are days in which fewer than teams won at least once. In this case, there will be at least one team that lost in every one of the rounds. But the teams it lost to will all have won at least once--contradiction.
So a transversal exists, and a transversal is just a choice of a distinct winning team from each day, as desired.
Other examples are given in this page: Applications of Hall's marriage theorem.
Here is a proof using Dilworth's theorem. Suppose . Say the sets in are . Suppose the union of the sets consists of the elements . Now define a partial order on by if and only if . (And: no two are comparable and no two are comparable.)
The marriage condition implies that the largest antichain in this set is . This is because if there were a larger antichain consisting of 's and 's, those 's would contain only the 's not in the antichain, of which there are , which would violate the marriage condition.
Then by Dilworth's theorem, there is a cover by chains. Each is in exactly one chain in the cover, and the chains in the cover are either or . Since every must appear in the chain cover, the elements that appear alongside the form a transversal.