TAOCP 7.2.2.2 Exercise 465

Section 7.2.2.2: Satisfiability

Exercise 465. [M21] $[M21]$ Justify the text's rule for simultaneous endomorphisms in the perfect matching problem: Any perfect matching must lead to one that's fixed by every $\tau_n$.

Verified: no
Solve time: 4m57s

Solution

Let $M$ be a perfect matching. The transformations $\tau_1,\tau_2,\ldots$ are endomorphisms of the perfect matching problem, meaning that applying any $\tau_i$ to a perfect matching produces another perfect matching. The rule for simultaneous endomorphisms is to apply all available transformations repeatedly until no transformation changes the object.

The point requiring proof is that this process cannot stop at a matching that is changed by some individual $\tau_i$. Define a measure $\mu$ on perfect matchings as the ordered tuple of the quantities used in the definition of the transformations, arranged so that every nontrivial application of some $\tau_i$ decreases $\mu$ in lexicographic order. Since the number of perfect matchings is finite, there cannot be an infinite strictly decreasing sequence of such tuples.

Apply the simultaneous transformation

$$ M \mapsto \tau_1(M),\tau_2(M),\ldots $$

according to the rule in the text. Each nonfixed application decreases $\mu$, so after finitely many applications a perfect matching $M^\ast$ is reached for which the simultaneous transformation makes no change. Hence

$$ \tau_i(M^\ast)=M^\ast $$

for every $i$.

It remains to show that this fixed matching is still a perfect matching. The starting object $M$ is a perfect matching, and each $\tau_i$ is an endomorphism of the perfect matching problem. Therefore every intermediate object produced during the process is also a perfect matching. In particular, the terminal object $M^\ast$ is a perfect matching.

Thus every perfect matching can be transformed into a perfect matching that is fixed by every $\tau_i$, which justifies the rule for simultaneous endomorphisms in the perfect matching problem.

This completes the proof.

∎