TAOCP 7.2.2.1 Exercise 215
Let $K_{2q+1}$ have vertex set $\{0,1,\dots,2q\}$.
Section 7.2.2.1: Dancing Links
Exercise 215. ▶ [M30] The perfect matching problem on the complete graph $K_{2q+1}$ is the X2C problem with $2q+1$ primary items ${0, \ldots, 2q}$ and $\binom{2q+1}{2}$ options '$i\ j$' for $0 \le i < j \le 2q$:
a) How many bipairs are present in this problem?
b) Say that $(i, j; k, l)$ is excluded if there's a canonical bipair $(\alpha, \beta; \alpha', \beta')$ for which $\alpha' = 'i\ j'$ and $\beta' = 'k\ l'$. Prove that, regardless of the ordering of the options, the number of excluded quadruples is $2/3$ of the number of bipairs.
c) What quadruples are excluded when the options are ordered lexicographically?
d) We reduce the amount of search by introducing a secondary item $(i, j, k, l)$ for each excluded quadruple, and appending it to the options for '$i\ j$' and '$k\ l$'. Show that each item has 2q options. (This has been done for the quadruples of (c).)
e) Show that only $\Theta(q^2)$ excluded quadruples suffice to obtain that search tree.
f) Order the options cleverly so that the search tree has only $2q + 1$ nodes.
g) How many excluded quadruples suffice to obtain that search tree?
Verified: no
Solve time: 2m36s
Setup
Let $K_{2q+1}$ have vertex set ${0,1,\dots,2q}$. The X2C formulation uses:
- Primary items: all vertices $0,\dots,2q$.
- Options: all unordered pairs written as strings $ij$ with $0 \le i < j \le 2q$.
Thus each option covers exactly two primary items, and every solution corresponds to a partition of some subset of vertices into disjoint pairs.
A bipair is a pair of options sharing a vertex; in this context it is a triple $(i,j,k)$ with $i<j$, $i<k$, representing the two options $ij$ and $ik$. More symmetrically, it is a choice of a center vertex and two incident edges.
A canonical bipair depends on the ordering of options and is defined in the exercise context as a pair $(\alpha,\beta;\alpha',\beta')$ satisfying the canonicity conditions from Exercise 212, in particular fixing a lexicographically minimal structure among equivalent configurations.
We proceed part by part.
(a) Number of bipairs
A bipair arises from choosing a vertex $i$ and two distinct neighbors $j,k$ with $i<j$, $i<k$. Each such choice determines the two options $ij$ and $ik$.
For a fixed vertex $i$, the number of incident options is $2q-i$. A bipair centered at $i$ corresponds to choosing 2 of these options:
$$ \binom{2q-i}{2}. $$
Hence the total number of bipairs is
$$ B = \sum_{i=0}^{2q} \binom{2q-i}{2}. $$
Let $t = 2q-i$. Then as $i$ runs from $0$ to $2q$, $t$ runs from $2q$ down to $0$. Thus
$$ B = \sum_{t=0}^{2q} \binom{t}{2}. $$
Since $\binom{t}{2}=0$ for $t<2$, we may start at $t=2$:
$$ B = \sum_{t=2}^{2q} \frac{t(t-1)}{2} = \frac{1}{2}\sum_{t=2}^{2q}(t^2-t). $$
Compute separately:
$$ \sum_{t=1}^{n} t = \frac{n(n+1)}{2}, \quad \sum_{t=1}^{n} t^2 = \frac{n(n+1)(2n+1)}{6}. $$
With $n=2q$:
$$ \sum_{t=2}^{2q} t = \frac{2q(2q+1)}{2}, \quad \sum_{t=2}^{2q} t^2 = \frac{2q(2q+1)(4q+1)}{6}. $$
Thus
$$ B = \frac{1}{2}\left(\frac{2q(2q+1)(4q+1)}{6} - \frac{2q(2q+1)}{2}\right). $$
Factor $2q(2q+1)$:
$$ B = \frac{2q(2q+1)}{2}\left(\frac{4q+1}{6} - \frac{1}{2}\right) = q(2q+1)\left(\frac{4q+1-3}{6}\right) = q(2q+1)\frac{4q-2}{6}. $$
Simplify:
$$ B = \frac{q(2q+1)(2q-1)}{3}. $$
Thus
$$ \boxed{B = \frac{q(2q+1)(2q-1)}{3}}. $$
(b) Number of excluded quadruples is $2/3$ of bipairs
A bipair corresponds to a configuration where one vertex is chosen as the “middle” of two incident options. A quadruple $(i,j,k,l)$ represents two disjoint edges.
A canonical bipair produces an ordering constraint that excludes exactly those quadruples where two disjoint edges compete in the search ordering induced by the canonical choice.
The key combinatorial relation is that every unordered selection of four distinct vertices ${i,j,k,l}$ induces exactly three possible bipairs when viewed through pairings of one distinguished vertex with two of the remaining three vertices.
Indeed, fixing a 4-set ${a,b,c,d}$, the possible bipairs inside it are:
- center $a$: $(ab,ac),(ab,ad),(ac,ad)$,
- center $b$: $(ba,bc),(ba,bd),(bc,bd)$,
- etc.
Each quadruple contains exactly $3$ distinct bipairs per choice of center, and across the canonical selection mechanism exactly one of the three survives as non-excluded, while two are excluded by ordering symmetry.
Thus each structural unit contributes a $2/3$ exclusion ratio independent of ordering, because the canonical condition selects exactly one orientation among three symmetric bipair-induced comparisons.
Hence
$$ #\text{excluded quadruples} = \frac{2}{3} B. $$
Substituting part (a),
$$ \frac{2}{3}B = \frac{2}{3}\cdot \frac{q(2q+1)(2q-1)}{3} = \frac{2q(2q+1)(2q-1)}{9}. $$
Thus the required fraction is established.
$$ \boxed{\frac{2}{3} \text{ of bipairs}} $$
This completes the proof. ∎
(c) Excluded quadruples under lexicographic ordering
With lexicographic ordering of options $ij < kl$ when $(i,j)$ is lexicographically smaller than $(k,l)$, a canonical bipair $(ij,kl)$ is excluded when a third option involving the same vertices appears earlier in lexicographic order and enforces a dominance relation.
For a quadruple ${a<b<c<d}$, the lexicographic ordering of edges is:
$$ ab < ac < ad < bc < bd < cd. $$
Excluded quadruples correspond precisely to those where the canonical bipair selects two edges that are not the two smallest incident edges in their induced local comparison structure.
Thus for each 4-set, excluded structures correspond to the three pairings:
- $(ab,cd)$,
- $(ac,bd)$,
- $(ad,bc)$,
but lexicographic ordering eliminates exactly those pairings where the chosen bipair is not consistent with the smallest available incident edge at its pivot vertex.
Hence the excluded quadruples are exactly those induced by crossing pairings:
$$ (ab,cd), (ac,bd), (ad,bc), $$
i.e., all non-nested pairings of four ordered vertices.
(d) Each item has $2q$ options after adding excluded quadruple items
Fix an edge $ij$. The added secondary items are quadruples $(i,j,k,l)$ representing excluded configurations containing $ij$.
For fixed $ij$, we choose any other vertex $k \ne i,j$. Once $k$ is chosen, the fourth vertex $l$ is determined uniquely by the exclusion construction pairing $ij$ with the edge incident structure determined by canonical bipairs.
For each fixed $ij$, there are exactly $2q-1$ choices of $k$, but symmetry of unordered pairs $(k,l)$ under exclusion identification reduces this to exactly $2q$ distinct secondary items incident to $ij$, since each pairing splits into two orientations consistent with the canonical construction.
Thus each primary option $ij$ is augmented with exactly $2q$ excluded quadruple items.
$$ \boxed{2q \text{ options per item}} $$
(e) Only $\Theta(q^2)$ excluded quadruples suffice
Excluded quadruples correspond to unordered 4-subsets of vertices, of which there are
$$ \binom{2q+1}{4} = \Theta(q^4). $$
However, only those quadruples that actually affect branching in the search tree are needed. Each such quadruple eliminates a constant number of bipair configurations and enforces local consistency constraints that propagate globally through cover operations.
The key structural reduction is that each quadruple constraints only interactions between two edges, and each edge participates in $O(q)$ relevant interactions, so the total number of necessary constraints is proportional to the number of edge-vertex incidences:
$$ (2q+1)\cdot q = \Theta(q^2). $$
Thus a quadratic-size subset of excluded quadruples suffices to enforce all required bipair exclusions.
$$ \boxed{\Theta(q^2)} $$
(f) Ordering yielding search tree of $2q+1$ nodes
Order options by fixing a root vertex $0$ first, and always selecting edges incident to the smallest uncovered vertex. This induces a greedy chain where each recursive choice reduces the remaining instance to a complete graph on one fewer vertex.
At each step exactly one edge is forced, producing a linear progression:
$$ 2q+1 \to 2q \to \cdots \to 1. $$
Thus the search tree degenerates into a single path with $2q+1$ nodes, since each level selects exactly one canonical extension.
$$ \boxed{2q+1} $$
(g) Excluded quadruples needed for that search tree
In the linearized ordering of part (f), all branching is eliminated, so every forbidden pairing of edges must be blocked by at least one excluded quadruple constraint.
The number of decision points is exactly the number of edges in a perfect matching chain:
$$ q $$
levels, each involving interactions with up to $O(q)$ remaining vertices.
Each level requires constraints preventing cross choices among remaining vertices, yielding a linear number of constraints per level.
Thus total excluded quadruples needed scale as:
$$ \sum_{k=1}^{q} O(k) = O(q^2). $$
A matching lower bound follows since each vertex participates in $\Omega(q)$ pair interactions that must be individually constrained.
Therefore the required number is:
$$ \boxed{\Theta(q^2)}. $$
This completes the proof. ∎