TAOCP 7.2.1.1 Exercise 50

Let $Q_n(l)$ denote the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ in exactly $l$ coordinates.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.1.1: Generating All n-Tuples

Exercise 50. ▶ [21] [21] Find a construction like that of Theorem D but with l even.

Verified: yes
Solve time: 2m37s

Let $Q_n(l)$ denote the graph on ${0,1}^n$ where two vertices are adjacent iff they differ in exactly $l$ coordinates. Theorem D gives a Hamilton cycle construction when $l$ is odd. We treat the case where $l$ is even.

When $l$ is even, flipping $l$ bits preserves Hamming weight parity, so $Q_n(l)$ splits into two connected components

$$ E_n={x\in{0,1}^n : w(x)\equiv 0 \pmod 2}, \qquad O_n={x\in{0,1}^n : w(x)\equiv 1 \pmod 2}. $$

It suffices to construct a Hamilton cycle in $E_n$; the same construction then gives one in $O_n$ by toggling a fixed bit.

Construction

We encode the even-parity component $E_n$ using $(n-1)$-bit strings. Define a map

$$ \varphi : {0,1}^{n-1} \to E_n, \qquad \varphi(x_1,\dots,x_{n-1}) = (x_1,\dots,x_{n-1}, \sigma(x)), $$

where

$$ \sigma(x) = x_1 \oplus x_2 \oplus \cdots \oplus x_{n-1}. $$

Then $\varphi(x)$ always has even weight, and $\varphi$ is a bijection between ${0,1}^{n-1}$ and $E_n$.

Now consider adjacency. Let $x,y \in {0,1}^{n-1}$, and let $d = \mathrm{dist}(x,y)$. In ${0,1}^{n-1}$, assume we have an edge of the graph $Q_{n-1}(l-1)$, so $d = l-1$. Since $l-1$ is odd, flipping $l-1$ bits changes the parity of weight, hence

$$ \sigma(x) \neq \sigma(y). $$

Therefore,

$$ \mathrm{dist}(\varphi(x), \varphi(y)) = (l-1) + 1 = l. $$

So $\varphi$ maps edges of $Q_{n-1}(l-1)$ to edges of $Q_n(l)$ inside $E_n$.

Algorithm Walkthrough

  1. Since $l$ is even, observe that $l-1$ is odd, so Theorem D applies and yields a Hamilton cycle $u_0,u_1,\dots,u_{2^{n-1}-1}$ in $Q_{n-1}(l-1)$.
  2. Define the lifted sequence $v_k = \varphi(u_k)$ for all $k$.
  3. For each consecutive pair $u_k,u_{k+1}$, they differ in exactly $l-1$ positions, so their images differ in those same $l-1$ coordinates among the first $n-1$ bits, and additionally the last bit flips because parity changes.
  4. Conclude that $v_k$ and $v_{k+1}$ differ in exactly $l$ coordinates, so each step is an edge in $Q_n(l)$.
  5. Since $u_k$ is a Hamilton cycle, $v_k$ visits every vertex of $E_n$ exactly once and returns to its start, forming a Hamilton cycle in $E_n$.
  6. Obtain a Hamilton cycle in $O_n$ by fixing the first bit to $1$ instead of $0$, or equivalently by adding a fixed prefix flip to $\varphi$.

Conclusion

For even $l$, $Q_n(l)$ decomposes into two isomorphic components $E_n$ and $O_n$, and each component is Hamiltonian via the lifting map from a Hamilton cycle in $Q_{n-1}(l-1)$. This provides a construction directly analogous to Theorem D, with the parity adjustment shifting the parameter from $l$ to the odd value $l-1$.