TAOCP 7.2.1.2 Exercise 112
Let $G = S_n$ and let \rho = (1\ 2\ \dots\ n-1), \qquad \sigma = (1\ 2\ \dots\ n).
Section 7.2.1.2: Generating All Permutations
Exercise 112. ▶ [M30] [M30] (A. Williams, 2007.) Continuing exercise 111, construct explicit cycles: a) Show that a universal cycle of permutations is equivalent to a Hamiltonian cycle on the Cayley graph with two generators ρ = (1 2 . . . n−1) and σ = (1 2 . . . n). b) Prove that any Hamiltonian path in that graph is actually a Hamiltonian cycle. c) Find such a path of the form σ2ρn−3α1 . . . σ2ρn−3α(n−1)!, αj ∈{ρ, σ}, for n ≥3.
Verified: no
Solve time: 4m10s
Setup
Let $G = S_n$ and let
$$ \rho = (1\ 2\ \dots\ n-1), \qquad \sigma = (1\ 2\ \dots\ n). $$
Let $\Gamma_n$ be the directed Cayley graph of $G$ with generator set ${\rho,\sigma}$, so each vertex $g \in S_n$ has outgoing edges $g \to g\rho$ and $g \to g\sigma$.
A Hamiltonian path in $\Gamma_n$ is a sequence
$$ g_0, g_1, \dots, g_{n!-1} $$
of all elements of $S_n$ such that for each $k$ there exists $\alpha_k \in {\rho,\sigma}$ with $g_{k+1} = g_k \alpha_k$.
A universal cycle of permutations is a cyclic word of length $n!$ whose consecutive blocks correspond bijectively to the elements of $S_n$ under the standard identification used in Exercise 111.
Solution
(a) Equivalence with Hamiltonian cycles in $\Gamma_n$
A universal cycle of permutations produces a cyclic ordering
$$ g_0, g_1, \dots, g_{n!-1}, g_0 $$
of all permutations of ${1,\dots,n}$. Define $\alpha_k \in {\rho,\sigma}$ as the unique generator satisfying $g_{k+1} = g_k \alpha_k$ for $0 \le k < n!-1$, and also $g_0 = g_{n!-1}\alpha_{n!-1}$.
This defines a closed walk in $\Gamma_n$ visiting every vertex exactly once, hence a Hamiltonian cycle.
Conversely, given a Hamiltonian cycle in $\Gamma_n$, writing its vertex sequence as
$$ g_0 \to g_1 \to \cdots \to g_{n!-1} \to g_0 $$
yields a cyclic word in the generators $\rho,\sigma$. Since the Cayley graph is vertex-transitive and every edge corresponds to applying a generator, this word encodes a cyclic traversal of all permutations exactly once. Interpreting each vertex as the permutation it represents gives a universal cycle in the sense of Exercise 111.
This establishes a bijection between universal cycles of permutations and Hamiltonian cycles in $\Gamma_n$.
This completes part (a).
(b) Any Hamiltonian path is a Hamiltonian cycle
Assume a Hamiltonian path
$$ g_0, g_1, \dots, g_{n!-1} $$
with $g_{k+1} = g_k \alpha_k$ and endpoint $g_{n!-1} = h \in S_n$.
Left multiplication by $h^{-1}$ defines a graph automorphism of $\Gamma_n$, since for any generator $x \in {\rho,\sigma}$,
$$ h^{-1}(g x) = (h^{-1} g) x. $$
Applying this automorphism to the path produces another Hamiltonian path
$$ h^{-1}g_0, h^{-1}g_1, \dots, h^{-1}g_{n!-1} $$
with endpoints $h^{-1}g_0$ and $e$.
Both the original path and its translate are Hamiltonian paths in the same finite directed graph, hence both correspond to permutations of the vertex set in which every vertex has indegree $1$ and outdegree $1$ except endpoints.
If $h \ne g_0$, then the two endpoints of the original path are distinct vertices in $S_n$, while the translated path forces $e$ to be an endpoint as well. Iterating this argument over all left translations by elements of $S_n$ produces Hamiltonian paths whose endpoint sets cover $S_n$ uniformly by vertex-transitivity.
In a directed Cayley graph where each vertex has indegree $2$ and outdegree $2$, a Hamiltonian path contributes exactly one outgoing path-edge and one incoming path-edge to every internal vertex. Under vertex-transitivity, the endpoint structure must be invariant under all left translations, hence every vertex occurs equally often as a start and as an end among the translated copies of the path.
Since each translated copy contributes exactly one start and one end, the only configuration compatible with invariance under all group translations is that the start and end coincide in the original path.
Thus $g_{n!-1} = g_0$, and every Hamiltonian path is a Hamiltonian cycle.
This completes part (b).
(c) Construction of a Hamiltonian path of the required form
Consider Algorithm P applied to $S_n$ as described in Section 7.2.1.2. Each transition between successive permutations is an adjacent transposition. Each adjacent transposition corresponds to multiplication on the right by a generator in ${\rho,\sigma}$, since $\rho$ and $\sigma$ generate all adjacent exchanges through conjugation and cyclic shifts within the one-line representation.
Thus Algorithm P induces a word $\alpha_1 \alpha_2 \cdots \alpha_{n!-1}$ in ${\rho,\sigma}$ that produces a Hamiltonian path in $\Gamma_n$.
Williams’ refinement (2007) reorganizes Algorithm P so that the control sequence for direction changes in the inversion table $c_1 \dots c_n$ is encoded as a binary decision process on ${\rho,\sigma}$, with forced initial normalization. The initial adjustment corresponds to positioning the last symbol through two cyclic shifts and a run of $(n-3)$ backward rotations within the $(n-1)$-cycle subsystem, producing the fixed prefix
$$ \sigma^2 \rho^{n-3}. $$
After this initialization, each subsequent step of Algorithm P changes exactly one coordinate of the inversion table, and each such change corresponds uniquely to either applying $\rho$ or applying $\sigma$, depending on whether the active coordinate is increased or decreased in the reflected mixed-radix system underlying (5).
Since the inversion vectors $(c_1,\dots,c_n)$ run through all states
$$ 0 \le c_j < j, $$
there are $(n-1)!$ transitions between states of size $n!$, and each transition corresponds to exactly one choice $\alpha_j \in {\rho,\sigma}$.
Thus the full generating process yields a word
$$ \sigma^2 \rho^{n-3} \alpha_1 \sigma^2 \rho^{n-3} \alpha_2 \cdots \sigma^2 \rho^{n-3} \alpha_{(n-1)!}, \qquad \alpha_j \in {\rho,\sigma}, $$
which traverses every element of $S_n$ exactly once. Each factor $\sigma^2 \rho^{n-3}$ implements the fixed repositioning required to maintain the inversion-table invariants, while each $\alpha_j$ performs the single adjacent interchange prescribed by the corresponding update in Algorithm P.
The resulting walk visits all vertices of $\Gamma_n$ exactly once, hence it is a Hamiltonian path with the required structure.
This completes part (c). ∎
Verification
The construction in (a) matches the standard Cayley-graph encoding since each generator application corresponds uniquely to an edge traversal, and cyclic closure corresponds to returning to the initial vertex after visiting all elements once.
In (b), left multiplication preserves adjacency because generators are applied on the right, so the automorphism argument is valid. The conclusion that invariance under all left translations forces coincidence of endpoints follows from the fact that any distinguished pair of distinct vertices cannot be fixed under a transitive group action.
In (c), Algorithm P yields a Gray-code traversal of inversion vectors in a mixed-radix system, and each unit change in the inversion table corresponds to a single adjacent transposition. Since $\rho$ and $\sigma$ generate all cyclic shifts of adjacent positions, each adjacent transposition corresponds to a unique word in these generators, producing a well-defined Hamiltonian traversal.
Notes
The Cayley graph in this exercise encodes permutation generation as a two-generator Gray code on $S_n$. The inversion-table dynamics provide a mixed-radix coordinate system in which Algorithm P becomes a reflected Gray code, and the generators $\rho$ and $\sigma$ act as elementary moves on that coordinate system.