Hypercubic Combinatorics: Hamiltonian Decomposition and Permutation Routing

In this paper, we first present new proofs, much shorter and much simpler than can be found elsewhere, of two facts about Hypercubes: that for the \( d \)-dimensional Hypercube, there exist sets of paths by which any \emph{permutation routing} task may be accomplished in at most \( 2d – 1 \) steps without queueing; and, when \( d \) is even, there exists an edge decomposition of the Hypercube into precisely \( \frac{d}{2} \) edge-disjoint Hamiltonian cycles. The permutation routing paths are computed off-line. Whether or not these paths may be computed by an online parallel algorithm in \( O(d) \)-time has long been an open question. We conclude by speculating on whether the use of a Hamiltonian decomposition of the Hypercube might lead to such an algorithm.