Applications of Hall's Marriage Theorem

Hall's marriage theorem has many applications in different areas of mathematics. We will look at the applications of creating Latin squares, having a stable marriage, and seeking college admission.

Recall that a Latin square is an $n \times n$ array filled with $n$ different symbols, each of which occurs exactly once in every row, and exactly once in every column. A Latin rectangle is an $m \times n$ array for $m \leq n$ filled with $n$ different symbols, in which each symbol occurs at most once in every row, and at most once in every column.

Suppose we have a $k \times n$ Latin rectangle of order $n.$ Then this can be extended to an $n \times n$ Latin square. $_\square$

---

We note that it is sufficient to show that we can extend this to a $(k+1) \times n$ Latin rectangle of order $n,$ since then we can proceed inductively to an $n \times n$ Latin square.

Consider a bipartite graph with $2n$ vertices, where the $n$ vertices on the left hand side of the bipartition correspond to the $n$ columns of the Latin rectangle, and the $n$ vertices on the right hand side correspond to the $n$ symbols of the Latin rectangle. There is an edge between a vertex on the left and a vertex on the right if the corresponding column does not contain the corresponding symbol. Observe that a perfect matching in this graph corresponds to a new row that we can add to our Latin rectangle.

The graph we constructed is a $m = n-k$ regular bipartite graph. We will use Hall's marriage theorem to show that for any $m,$ an $m$-regular bipartite graph has a perfect matching.

Consider a set $P$ of size $p$ vertices from one side of the bipartition. Each vertex has $m$ neighbors, so the total number of edges coming out from $P$ is $pm.$ Each vertex on the other side has degree $m,$ so by the pigeon hole principle, there are at least $\frac{pm}{m} = p$ neighbors. Thus, this graph satisfies Hall's condition and has a perfect matching, as required. $_\square$

The Stable marriage problem is related problem to the marriage problem. Instead of each vertex only having some neighbors in the opposite side, it has an ordered ranking of all vertices in the opposite side.

Suppose we have two sets of people of equal size $A$ and $B$ such that each person has an ordered list of the people in the other set. A matching between $A$ and $B$ is said to be stable if we cannot find $a \in A$ and $b \in B$ such that $a$ prefers $b$ to the person they are currently matched to and $b$ prefers $a$ to the person they are currently matched to.

The Gale-Shapley algorithm is one method of finding a stable marriage. The algorithm is as follows:

1
2
3
4
5

Every vertex begins unmatched.
While there is an unmatched vertex in the set A
    each unmatched vertex in A proposes to match with its most preferred B vertex it has not already tried to match with
        if the B vertex was unmatched then these vertices are now matched
        if the B vertex was matched, it chooses its preferred vertex of the proposed one or the existing match, the other vertex remains or becomes unmatched

To see that the algorithm terminates with a perfect matching, observe that once a vertex in $B$ becomes matched, it never becomes unmatched. When the algorithm terminates, if there was an unmatched vertex in $A,$ then it would have proposed matching to an unmatched vertex in $B$ and that proposal would have been accepted.

To see that the matching is stable, suppose that there is $a \in A$ and $b \in B$ that are unmatched and each prefers the other. Since $a$ prefers $b$ to its current match, $a$ must have proposed matching to $b$ at some point. Since $b$ is matched to someone other than $a,$ $b$ must have chosen this match over $a$ and thus cannot prefer $a$ to its current match.

One application of this is in dealing with network traffic in the internet. When handling large amounts of traffic over a large quantity of servers, you need to decide which server to send traffic to. The traffic's preferences are generally the costs, which could be money or time related, associated with using certain servers. The servers' preferences are generally based on how reliable their communication is with where the traffic is originating.

Another related problem is known as the college admissions problem. Consider a group of colleges and a group of students. Each student is interested in attending some of the colleges and each college is interested in accepting some of the students, but each also has preferences as to which ones they would like to accept. We would like to find a stable matching assigning students to colleges so that there is no student/college pair where the student would rather be going to that college than the one they are going to and the college would rather have that student than some other one they have accepted.

Notice that this is slightly different from the stable marriage problem, since a student does not necessarily want to go to all the colleges, and a college does not want to accept all the students.

This problem is one that occurs in the real world when the National Resident Matching Program attempts to match medical students to hospitals for their residency.

1) ($2012$ Putnam B3) A round-robin tournament of $2n$ teams lasted for $2n-1$ 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 $n$ 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?

2) ($2010$ ISL C2) On some planet, there are $2^N$ countries $(N \geq 3$). Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1,$ each field being either yellow or blue. No two countries have the same flag. We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set.

3) In a $2n \times 2n$ board, there are $n$ rooks in each row and each column of the board. Show that there exist $2n$ rooks that belong to pairwise distinct rows and pairwise distinct columns.