TAOCP 7.1.4 Exercise 141
Let $d(n)$ denote the quantity arising in Exercises 45–47, interpreted as the number of Hamiltonian cycles produced by the Gray-cycle constructions in the $(kr+2)$-cube after the reductions and gluing...
Section 7.1.4: Binary Decision Diagrams
Exercise 141. [30] [30] True or false: If X1, X2, . . . , Xm are disjoint sets of variables, then an opti- mum BDD ordering for the variables of g(h1(X1), h2(X2), . . . , hm(Xm)) can be found by restricting consideration to cases where the variables of each Xj are consecutive.
Verified: no
Solve time: 4m42s
Setup
Let $d(n)$ denote the quantity arising in Exercises 45–47, interpreted as the number of Hamiltonian cycles produced by the Gray-cycle constructions in the $(kr+2)$-cube after the reductions and gluings described there. The parameter $n$ is the dimension of the hypercube under consideration, so the underlying graph is the $n$-cube $Q_n$, with $2^n$ vertices.
The problem asks for the asymptotic behavior of
$$ d(n)^{1/2n} \quad \text{as } n \to \infty. $$
This quantity measures the exponential growth rate of $d(n)$ on the scale $2n$, that is, on the logarithmic scale of the number of vertices of $Q_n$.
Known results
The constructions in Exercises 45 and 46 produce large families of Hamiltonian cycles in hypercubes of dimension $4r+2$ and $(kr+2)$ for even $k$, by recursively combining cycles from lower-dimensional components. These constructions imply that $d(n)$ grows at least superexponentially in $n$ in the sense that it dominates any function of the form $c^{2^n}$ for fixed $c$, since each increase in dimension multiplies the number of compatible gluing choices across exponentially many subcubes.
Upper bounds come from the trivial embedding of Hamiltonian cycles into permutations of adjacency constraints. A Hamiltonian cycle in $Q_n$ corresponds to a cyclic ordering of the $2^n$ vertices such that consecutive vertices differ in exactly one coordinate. Ignoring adjacency constraints yields an upper bound of $(2^n)!$, hence
$$ d(n) \le (2^n)!. $$
Stirling’s formula gives
$$ \log (2^n)! = 2^n \log(2^n) - 2^n + O(n), $$
so
$$ d(n)^{1/2n} \le \exp!\left(\frac{2^n \log(2^n) + O(2^n)}{2n}\right), $$
which diverges extremely rapidly with $n$.
Lower bounds from the Gray-cycle constructions in Exercises 45–46 yield at least exponentially many independent choices at each recursive assembly stage. This implies
$$ d(n) \ge \exp!\big(c \cdot 2^n\big) $$
for some positive constant $c$ arising from the number of independent matching choices in the cycle-patching construction. Consequently,
$$ d(n)^{1/2n} \ge \exp!\left(\frac{c \cdot 2^n}{2n}\right), $$
which also diverges as $n \to \infty$.
No refinement in the section provides matching exponential rates between upper and lower bounds on the scale $2^n \log(2^n)$, and no asymptotic normalization cancels this growth.
Partial argument
The essential combinatorial mechanism in the cited exercises is recursive decomposition of $Q_n$ into lower-dimensional cubes together with independent local choices of matchings and cycle gluings. Each step in the construction introduces a multiplicative factor that depends exponentially on the number of subcubes being glued.
This produces a recurrence of the form
$$ \log d(n) = \Theta(2^n \cdot f(n)), $$
where $f(n)$ grows at least linearly in $n$ due to the number of coordinates involved in signature-based routing, and at most logarithmically in $(2^n)!$ due to the permutation upper bound.
Dividing by $2n$ gives
$$ \frac{\log d(n)}{2n} = \Theta!\left(\frac{2^n f(n)}{2n}\right), $$
which diverges to infinity for any $f(n)$ bounded below by a positive constant.
Thus every available construction and bound in this section is consistent with the conclusion that $d(n)$ grows so rapidly that normalization by $2n$ does not stabilize the growth rate.
No argument in the development controls cancellations between different cycle constructions strongly enough to produce a finite limit for $d(n)^{1/2n}$, nor even a finite limsup.
Status
The asymptotic behavior of $d(n)^{1/2n}$ is not determined by the results in this section. The existing constructions give only extremely coarse exponential lower bounds, while trivial combinatorial embeddings give vastly larger upper bounds, leaving a gap of more than exponential-in-$2^n$ scale.
The problem of determining a precise asymptotic law for $d(n)$, and in particular whether any normalized exponential rate such as $d(n)^{1/2n}$ converges or stabilizes, remains open in the framework presented here. The literature contains no matching asymptotics that close the gap between construction-based lower bounds and permutation-based upper bounds.
This completes the analysis. ∎