Marriage Problem

Latin squares could be used by dating services to organize meetings between a number n of girls and the same number n of boys. Having met all the boys, each girl comes up with a list of boys she would not mind marrying. The dating service is faced now with the task of arranging marriages so as to satisfy each girl preferences. Call the set of boys listed by the i-th girl A_i. The problem is then to pick boys, one from each list, without selecting the same boy more than once. An abstract formulation of this problem and its constructive solution by W. McWorter, Jr. is given below.

Let A₁, ..., A_n be subsets of an n-set M. The family of sets A₁, ..., A_n has a system of distinct representatives (SDR) iff there exist distinct elements x₁, ..., x_n, such that x_i is in A_i, for each i = 1, ..., n.

Let A₁, ..., A_n be subsets of an n-set M. The family of sets A₁, ..., A_n satisfies the marriage condition iff the union of any k of the sets contains at least k elements, for all k = 1, ..., n.

MARRIAGE THEOREM

A family A₁, ..., A_n of sets has a system of distinct representatives iff the family satisfies the marriage condition.

Remark

Strictly speaking, the proof below does not require the sets of boys and girls to be equipotent. However, this is a sensible assumption. For, if there are fewer boys the marriage condition fails. On the other hand, if there are fewer girls, the difference can be made up by "desperate" girls willing to marry any boy without disturbing the truth or falsity of the marriage condition.

Proof

I will prove this theorem by describing a procedure for constructing a system of distinct representatives which succeeds iff the marriage condition is satisfied. Another elegant, though less procedural, proof illuminates various phases of the algorithm. It is convenient for me to describe everything in terms of zero-one matrices. Let A = (a_ij) be an n×n matrix whose columns are labelled by the sets A₁, ..., A_n and whose rows are labelled by the elements of M (which is the union of the A_i's). For each i, j = 1, ..., n, set a_ij = 1 if the i^th element of M is in A_j and set a_ij = 0 otherwise.

Then the family has a SDR iff the matrix A has a transversal of 1's. Here is the procedure together with a proof that it constructs a transversal of 1's iff the family satisfies the marriage condition. Assume matrix A is in the form below, where, at the beginning, the upper left block with 1's on the diagonal may or may not be empty. Successive steps of the algorithm are designed to increase the size of the block.

GREEDY PHASE:

|1        |        |
|  1      |        |
|    .    |        |
|      .  |        |
|        1|        |
| --------|--------|
|         |        |
|         |   B	   |
|         |        |

If block B is empty (0×0), then we are done, the family has a SDR. If B contains a 1, interchange rows and columns (without disturbing the diagonal of ones in the upper left corner block) to put a 1 in the upper left corner of B, replace B with that obtained by using all but the first row and first column of B, and resume the greedy phase.

Otherwise, we proceed to the LABEL PHASE.

B HAS ONLY ZEROS:

|1        |        |
|  1      |        |
|    .    |        |
|      .  |   D    |
|        1|        |
| --------|--------|
|         |        |
|    C    |   0    |
|         |        |

If block C has only zeros, we are done; the family has no SDR because the sets associated with the columns of C together with a set associated with a column of B violate the marriage condition; that is, the union of these sets contains one fewer elements than the number of sets.

If a_ij = 1 in block C and a_jk = 1 in block D, then interchange columns j and k of A and resume the greedy phase with B the lower right corner block which now contains a 1.

LABEL PHASE:

|1    |       |        |
|  .  |       |   G    |
|    1|       |        |
------------------------
|     |1      |        |
|     |  .    |        |
|  F  |    .  |   0    |
|     |      1|        |
|-----|-------|--------|
|     |       |        |
|  0  |   E   |   0    |
|     |       |        |
 A

Having reached here, for every 1 in C there are only zeros in the corresponding row of D. We can re-arrange the columns of C so that all its zero columns are left of all its nonzero columns as follows. If column i of A meets C in a nonzero column of C, and column j ≥ i meets C in a zero column of C, interchange columns i and j of A followed by interchanging rows i and j of A. This leaves the 1's in the main diagonal of the upper left block of A intact amd moves a nonzero column of C to the right. It also puts the zero block just below G. Hence, after row and column interchanges, we have the picture above, with E all those columns of C which contain a 1.

If the block F contains only zeros, then we are done; the family has no SDR because the sets corresponding to the columns of F and one set corresponding to a column of G violates the marriage condition.

If a_ij = 1 in F and a_jk = 1 in G, for some k, then swap columns j and k of A. This puts a 1 in the zero block just below G. Now we can swap the k^th and i^th columns of A, putting a 1 in the lower right corner zero block. Resume the greedy phase.

Otherwise, if for every nonzero column of F, the corresponding row of G has only zeros, then let E₁ be the nonzero columns of F and let G₁ be the rows of G corresponding to the columns of E₁ (if column i meets E₁, then row i meets G₁.) If G₁ has a 1, then we can interchange a column of G₁ with a column of E₁ to put a 1 in a row that corresponds to a column of E; whence we can do another interchange to put a 1 into the lower right block of A and resume the GREEDY PHASE. Otherwise, let F₁ be the submatrix of A consisting of the columns left of E₁ and whose rows are the rows of G₁. If F₁ has only zeros, then, as with F, the marriage condition is violated. Otherwise, let E₂ be the nonzero columns of F₁ and let G₂ be the rows of G corresponding to the columns of F₂. If G₂ contains a 1, we can do a series of column swaps to put a 1 to the right of E and resume the GREEDY PHASE. Otherwise, we continue the construction of F_i's and G_i's until some G_i has a nonzero entry unless G has all entries zero, a violation of the marriage condition (if a column of G is zero, then the union of one set has no elements, a violation of the marriage condition). Thus, either the marriage condition is violated or we can do a series of swaps that puts a 1 to the right of E so we can resume the GREEDY PHASE.

Example:

A series of 4 swaps needed to put a 1 in the lower right corner.

Thus the family has an SDR iff the marriage condition is satisfied.

Corollary

If a family A₁, ..., A_n of sets has the property that |A_i| = k, for i = 1, ..., n and every element of the union of the A_i occurs in at most k of the A_i, then the family has a system of distinct representatives.

Proof

We show that the family satisfies the marriage condition. For any s, 1 < s < n, let t be the number of elements in the union of s of the A_i. Since each A_i has k elements, there are exactly ks occurences of elements in the s sets A_i. Since each element can occur in at most k sets, there are at most kt occurences of elements in the s sets A_i. Hence ks≤kt, whence s≤t. Thus the family A₁, ..., A_n satisfies the marriage condition and so has a system of distinct representatives.

This corollary is used to show that every latin rectangle can be completed to a latin square, and that every attempt to construct a latin square by transversals, i.e., place the 1's, then place the 2's, etc., can succeed.

Latin Squares

71537542