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 Ai. 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 A1, ..., An be subsets of an n-set M. The family of sets A1, ..., An has a system of distinct representatives (SDR) iff there exist distinct elements x1, ..., xn, such that xi is in Ai, for each i = 1, ..., n.

Let A1, ..., An be subsets of an n-set M. The family of sets A1, ..., An 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 A1, ..., An 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 = (aij) be an n×n matrix whose columns are labelled by the sets A1, ..., An and whose rows are labelled by the elements of M (which is the union of the Ai's). For each i, j = 1, ..., n, set aij = 1 if the ith element of M is in Aj and set aij = 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 aij = 1 in block C and ajk = 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 aij = 1 in F and ajk = 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 kth and ith 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 E1 be the nonzero columns of F and let G1 be the rows of G corresponding to the columns of E1 (if column i meets E1, then row i meets G1.) If G1 has a 1, then we can interchange a column of G1 with a column of E1 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 F1 be the submatrix of A consisting of the columns left of E1 and whose rows are the rows of G1. If F1 has only zeros, then, as with F, the marriage condition is violated. Otherwise, let E2 be the nonzero columns of F1 and let G2 be the rows of G corresponding to the columns of F2. If G2 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 Fi's and Gi's until some Gi 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:

1 0 0 0 1
1 1 0 0 0
0 1 1 0 0
0 0 1 1 0
0 0 0 1 0

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 A1, ..., An of sets has the property that |Ai| = k, for i = 1, ..., n and every element of the union of the Ai occurs in at most k of the Ai, 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 Ai. Since each Ai has k elements, there are exactly ks occurences of elements in the s sets Ai. Since each element can occur in at most k sets, there are at most kt occurences of elements in the s sets Ai. Hence ks≤kt, whence s≤t. Thus the family A1, ..., An 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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

 62637824

Search by google: