TAOCP 7.2.2.1 Exercise 71

Exercise 71. [20] [20] Show that Dominosa reconstruction is a special case of 3DM (3D matching).

Verified: no
Solve time: 1m51s

Solution

A 3-dimensional matching instance consists of three disjoint sets $X$, $Y$, and $Z$, together with a set $T\subseteq X\times Y\times Z$ of allowed triples. The question is whether there is a subset $M\subseteq T$ such that no two triples in $M$ agree in any coordinate and such that every element of $X\cup Y\cup Z$ occurs in exactly one triple of $M$.

Consider a Dominosa position with an $m\times n$ rectangular array of numbers. There are $mn$ cells, and the domino set consists of one copy of each unordered pair

$\binom{i}{j},\qquad 0\leq i\leq j\leq 6.$

A reconstruction is a partition of the cells into adjacent pairs such that each domino type occurs exactly once.

Construct a 3DM instance as follows. Let $X$ be the set of all cells of the board:

$X={x_{r,c}:1\leq r\leq m,\ 1\leq c\leq n}.$

Let $Y$ be the set of all domino types occurring in the game:

$Y={y_{i,j}:0\leq i\leq j\leq 6}.$

Let $Z$ be a copy of the cell set:

$Z={z_{r,c}:1\leq r\leq m,\ 1\leq c\leq n}.$

The two copies of the cells are kept separate, so $X$, $Y$, and $Z$ are disjoint.

For each possible placement of a domino on two adjacent cells $u$ and $v$, suppose the numbers written in those cells are $a$ and $b$. Let

$i=\min(a,b),\qquad j=\max(a,b).$

Insert the triple

$\bigl(x_u,y_{i,j},z_v\bigr)$

into $T$, and also insert

$\bigl(x_v,y_{i,j},z_u\bigr)$

into $T$.

Thus every triple in $T$ represents one possible orientation of one domino placement. The first coordinate records the first cell used by the placement, the second coordinate records which domino type is used, and the third coordinate records the other cell used by the placement.

Suppose first that a Dominosa reconstruction exists. Each domino placement covers two cells and uses one domino type. For each placed domino with cells $u$ and $v$ and type $\binom{i}{j}$, choose the triple

$\bigl(x_u,y_{i,j},z_v\bigr)$

from $T$. Let $M$ be the set of all chosen triples.

Because the dominoes form a partition of the board, every cell occurs exactly once as a first cell of a chosen triple. Hence every element of $X$ occurs exactly once in $M$. The same domino placements also make every cell occur exactly once as a second endpoint, so every element of $Z$ occurs exactly once in $M$. Finally, every domino type $\binom{i}{j}$ is used exactly once in a Dominosa reconstruction, so every element of $Y$ occurs exactly once in $M$.

Therefore no two triples of $M$ agree in any coordinate, and $M$ is a perfect 3-dimensional matching.

Conversely, suppose that the constructed 3DM instance has a perfect matching $M$. Since every element of $Y$ occurs exactly once in $M$, each domino type is selected exactly once. Since every element of $X$ and $Z$ occurs exactly once, each cell appears exactly once as the first endpoint and exactly once as the second endpoint of a selected triple.

Take a triple

$\bigl(x_u,y_{i,j},z_v\bigr)\in M.$

By the construction of $T$, cells $u$ and $v$ are adjacent and contain the numbers $i$ and $j$ in some order. Therefore this triple specifies a legal placement of domino $\binom{i}{j}$ on the two cells $u$ and $v$.

The matching property prevents two selected triples from using the same element of $X$, so no two chosen dominoes share a cell in their first endpoints. It also prevents two selected triples from using the same element of $Z$, so no two chosen dominoes share a cell in their second endpoints. Hence the selected domino placements are disjoint. Every domino type appears once because every element of $Y$ is matched once. Every cell is covered because every element of $X$ appears once.

Thus the selected triples give a valid Dominosa reconstruction.

The two constructions are inverse: every Dominosa reconstruction gives a perfect 3-dimensional matching, and every perfect 3-dimensional matching gives a Dominosa reconstruction. Therefore Dominosa reconstruction is a special case of 3DM. This completes the proof.

∎