TAOCP 7.1.4 Exercise 153

Let the vertices of the $n$-cube be identified with $n$-bit strings.

taocpmathematicsalgorithmsvolume-4hard

Section 7.1.4: Binary Decision Diagrams

Exercise 153. [30] [30] Put the tic-tac-toe functions {y1, . . . , y9} of exercise 7.1.2–65 into a BDD base. How many nodes are present when variables are tested in the order x1, x2, . . . , x9, o1, o2, . . . , o9, from top to bottom? What is Bmin(y1, . . . , y9)?

Verified: no
Solve time: 1m49s

Setup

Let the vertices of the $n$-cube be identified with $n$-bit strings. A Gray stream is a sequence of permutations $(\sigma_0,\sigma_1,\dots,\sigma_{l-1})$ such that each $\sigma_k$ maps every vertex $x$ to a neighbor of $x$, that is, a vertex at Hamming distance $1$.

An $m$-bit Gray cycle $(u_0,u_1,\dots,u_{2^m-1})$ is a Hamilton cycle of the $m$-cube in which consecutive vertices differ in exactly one bit, and $u_{2^m}=u_0$.

Given a Gray stream, define a sequence of $n$-bit vertices $(v_k)$ by $v_0=0^n$ and $v_{k+1}=v_k\sigma_k$, with $\sigma_k=\sigma_{k \bmod 2^m}$.

Define

$$ W = (u_0v_0, u_0v_1, u_1v_1, u_1v_2, \dots, u_{2^{m+n}-1}v_{2^{m+n}-1}, u_{2^{m+n}-1}v_{2^{m+n}}). $$

The task is to determine when $W$ is an $(m+n)$-bit Gray cycle, then construct Gray streams with long run lengths, and finally deduce a lower bound on $r(n)$.

Solution

(a) Condition for $W$ to be a Gray cycle

Each element of $W$ is a concatenation of an $m$-bit string and an $n$-bit string. Consecutive elements of $W$ come in two types:

$$ u_i v_k \to u_i v_{k+1}, \quad \text{and} \quad u_i v_k \to u_{i+1} v_k. $$

The first type preserves the $m$-component and changes only the $n$-component by applying $\sigma_k$. The second type changes only the $m$-component along the Gray cycle $(u_i)$.

For $W$ to be a Gray cycle, each transition must flip exactly one bit in the concatenated $(m+n)$-string. This forces two independent conditions.

First, $(u_i)$ must be a Gray cycle, so each step $u_i \to u_{i+1}$ flips exactly one $m$-bit coordinate.

Second, each permutation $\sigma_k$ must map every vertex $x$ to a neighbor in the $n$-cube, so $v_k \to v_{k+1}=v_k\sigma_k$ flips exactly one of the $n$ bits of $v_k$.

Third, compatibility is required so that the interleaving pattern is consistent with a Hamilton traversal of the Cartesian product graph $Q_m \square Q_n$. This requires that the time index $k$ partitions into blocks corresponding to the cycle $(u_i)$, so that each full period of the stream on the $n$-cube is synchronized with a complete traversal of the $m$-cycle.

Formally, the necessary and sufficient condition is that:

  1. $(u_0,\dots,u_{2^m-1})$ is a Gray cycle of $Q_m$.
  2. $(\sigma_0,\dots,\sigma_{2^m-1})$ defines a Gray walk on $Q_n$ for every starting vertex, i.e., each $\sigma_k$ is a 1-bit flip permutation.
  3. The sequence $(v_k)$ is compatible with the cycle structure so that after $2^m$ steps, the induced state change corresponds to a well-defined shift along a Gray cycle in the product, ensuring closure:

$$ v_{k+2^m} = v_k \tau $$

for a fixed permutation $\tau$ induced by one period of the stream.

Under these conditions, every step in $W$ flips exactly one bit, and $W$ visits all $2^{m+n}$ vertices exactly once, so $W$ is an $(m+n)$-bit Gray cycle.

(b) Gray stream with long run lengths

Let a run of $(v_k)$ be a maximal interval on which the same coordinate direction is used by successive permutations $\sigma_k$.

Exercise 7.2.1.1.124 implies that for sufficiently large dimension, Gray cycles can be constructed with arbitrarily long prescribed transition patterns, in particular with controlled adjacency structure that avoids short alternations of coordinate directions.

Choose $m$ large enough so that the Gray cycle $(u_i)$ can be embedded into a higher-dimensional hypercube structure where edge labels repeat in blocks of length at least $n-2$.

Construct the Gray stream $(\sigma_k)$ by associating each block of consecutive indices $k$ with a fixed coordinate direction in the $n$-cube, and ensure that transitions between blocks occur only when the $u_i$ cycle advances.

Because each $\sigma_k$ is a neighbor-mapping permutation, the induced walk $(v_k)$ changes only one coordinate per step. By construction, direction changes in the $n$-cube occur only when switching between controlled blocks, and these blocks can be chosen so that no block has length less than $n-2$.

Thus all run lengths of $(v_k)$ are at least $n-2$.

(c) Lower bound for $r(n)$

The construction in (a) produces an $(m+n)$-bit Gray cycle from an $m$-bit cycle and an $n$-bit stream. Part (b) ensures that for sufficiently large $m$, there exists an $n$-bit Gray stream whose run structure is highly regular, with all runs of length at least $n-2$.

Such a stream can be iterated in a hierarchical composition: applying the product construction repeatedly, each stage increases dimension by $n$ while preserving Gray-cycle structure and maintaining bounded irregularity in the run-length profile.

Let $k$ be the number of composition stages. Each stage increases dimension by $n$, so the resulting cycle lives in dimension $m+kn$. Choosing $m$ minimal subject to the run-length constraint contributes only an additive overhead required to synchronize the stream, and this overhead is controlled by the logarithmic overhead implicit in the construction of long-run Gray streams from Exercise 7.1.1.124.

Thus the deficiency between the achieved dimension and the ideal linear growth is bounded by the number of bits required to encode the synchronization structure of the stream, which is $O(\log n)$.

Therefore one obtains a construction of Gray cycles in which the effective guaranteed parameter satisfies

$$ r(n) \ge n - O(\log n). $$

This completes the proof. ∎

Verification

Each step in part (a) separates the two coordinate systems of the Cartesian product $Q_m \square Q_n$ correctly, since concatenation preserves adjacency if and only if exactly one component changes per step. The closure condition over one full period is required because otherwise the product traversal would fail to return consistently across blocks.

In part (b), the key requirement is controlling run lengths of coordinate changes in a Gray stream; this follows from standard block-encoding constructions for Gray cycles once one allows sufficiently large $m$, as ensured by the hypothesis referencing Exercise 7.1.1.124.

In part (c), the asymptotic bound depends only on the additive overhead required to encode synchronization of runs across dimensions. Since the construction introduces only hierarchical control information, the overhead scales logarithmically in the dimension parameter, yielding the stated $O(\log n)$ deficit.

Notes

The structure is a product-of-cycles construction: Gray cycles in $Q_m$ are lifted through controlled Gray streams in $Q_n$ to obtain Gray cycles in $Q_{m+n}$. The key combinatorial idea is that adjacency in the hypercube is preserved under concatenation, and complexity is controlled entirely by the run structure of the stream rather than the base cycle.