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 array filled with different symbols, each of which occurs exactly once in every row, and exactly once in every column. A Latin rectangle is an array for filled with different symbols, in which each symbol occurs at most once in every row, and at most once in every column.
Suppose we have a Latin rectangle of order Then this can be extended to an Latin square.
We note that it is sufficient to show that we can extend this to a Latin rectangle of order since then we can proceed inductively to an Latin square.
Consider a bipartite graph with vertices, where the vertices on the left hand side of the bipartition correspond to the columns of the Latin rectangle, and the vertices on the right hand side correspond to the 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 regular bipartite graph. We will use Hall's marriage theorem to show that for any an -regular bipartite graph has a perfect matching.
Consider a set of size vertices from one side of the bipartition. Each vertex has neighbors, so the total number of edges coming out from is Each vertex on the other side has degree so by the pigeon hole principle, there are at least neighbors. Thus, this graph satisfies Hall's condition and has a perfect matching, as required.
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 and such that each person has an ordered list of the people in the other set. A matching between and is said to be stable if we cannot find and such that prefers to the person they are currently matched to and prefers 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
To see that the algorithm terminates with a perfect matching, observe that once a vertex in becomes matched, it never becomes unmatched. When the algorithm terminates, if there was an unmatched vertex in then it would have proposed matching to an unmatched vertex in and that proposal would have been accepted.
To see that the matching is stable, suppose that there is and that are unmatched and each prefers the other. Since prefers to its current match, must have proposed matching to at some point. Since is matched to someone other than must have chosen this match over and thus cannot prefer 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) ( Putnam 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?
2) ( ISL C2) On some planet, there are countries ). Each country has a flag units wide and one unit high composed of fields of size each field being either yellow or blue. No two countries have the same flag. We say that a set of flags is diverse if these flags can be arranged into an square so that all fields on its main diagonal will have the same color. Determine the smallest positive integer such that among any distinct flags, there exist flags forming a diverse set.
3) In a board, there are rooks in each row and each column of the board. Show that there exist rooks that belong to pairwise distinct rows and pairwise distinct columns.