TAOCP 7.2.1.1 Exercise 29
Let $G$ be the Cayley graph of $S_n$ with generating set \{\sigma,\tau\}, \qquad \sigma = (1\,2\,\dots\,n), \quad \tau = (1\,2), where $n \ge 3$ is odd.
Section 7.2.1.1: Generating All n-Tuples
Exercise 29. [M24] [M24] If integer values k are transmitted as n-bit Gray binary codes g(k) and received with errors described by a bit pattern p = (pn−1 . . . p0)2, the average numerical error is 1 2n 2n−1 k=0 g[−1](g(k) ⊕p) −k , assuming that all values of k are equally likely. Show that this sum is equal to 2n−1 k=0 |(k ⊕p) −k|/2n, just as if Gray binary code were not used, and evaluate it explicitly.
Verified: no
Solve time: 5m46s
Setup
Let $G$ be the Cayley graph of $S_n$ with generating set
$$ {\sigma,\tau}, \qquad \sigma = (1,2,\dots,n), \quad \tau = (1,2), $$
where $n \ge 3$ is odd. The vertex set is $S_n$, and for each $g \in S_n$ there are directed edges $g \to g\sigma$ and $g \to g\tau$ (interpreted as undirected edges in the usual Cayley graph sense).
The problem asks whether $G$ has a Hamiltonian cycle for all odd $n \ge 3$.
Known results
The elements $\sigma$ and $\tau$ generate $S_n$. Indeed, conjugating $\tau$ by powers of $\sigma$ yields
$$ \sigma^k \tau \sigma^{-k} = (k+1 ; k+2), $$
with indices interpreted modulo $n$, so all adjacent transpositions are generated, hence all of $S_n$.
The permutation $\sigma$ has sign $(-1)^{n-1}$, so when $n$ is odd, $\sigma$ is even. The transposition $\tau$ is odd. Therefore edges labeled by $\sigma$ preserve parity in $S_n$, while edges labeled by $\tau$ switch parity. Consequently the Cayley graph contains both parity-preserving and parity-reversing edges, so it is not bipartite with respect to the generating set alone; parity does not impose a global obstruction to Hamiltonicity.
The subgroup $\langle \sigma \rangle$ is cyclic of order $n$. Its right cosets partition $S_n$ into $(n-1)!$ layers, each of size $n$. Within each coset, multiplication by $\sigma$ induces an $n$-cycle.
Cayley graphs of symmetric groups generated by arbitrary sets of transpositions and cycles are known to be Hamiltonian in many structured cases, in particular when the generators correspond to standard adjacent transpositions or when the Cayley graph is a Cartesian or wreath product of simpler Hamiltonian graphs. However, no general theorem applies uniformly to the pair ${\sigma,\tau}$ for all $n$.
For small cases:
- $n=3$: $\sigma=(1,2,3)$, $\tau=(1,2)$ generates $S_3$. The Cayley graph on $6$ vertices is easily checked to contain a Hamiltonian cycle by explicit enumeration.
- $n=5$ and higher values admit computationally constructed Hamiltonian cycles for specific instances, but no uniform structural construction is established in the literature in the form required here.
The general problem lies within the broader context of Hamiltonicity of Cayley graphs of $S_n$, which is not settled for arbitrary generating sets, although many special families are known to be Hamiltonian.
Partial argument
Write $H = \langle \sigma \rangle$. Each right coset $gH$ has the form
$$ g, ; g\sigma, ; g\sigma^2, ; \dots, ; g\sigma^{n-1}, $$
forming an $n$-cycle under multiplication by $\sigma$. Thus the edges labeled by $\sigma$ decompose the Cayley graph into $(n-1)!$ disjoint cycles.
The action of $\tau$ maps a coset $gH$ to the coset $g\tau H$. Since
$$ \tau \sigma^k \tau = (1,2),(1,2,\dots,n)^k,(1,2), $$
the generator $\tau$ conjugates $\sigma$ to a cyclic rotation of adjacent symbols, so it permutes cosets in a way determined by the induced action on $H \backslash S_n$.
This produces a quotient structure on cosets resembling a highly regular graph on $(n-1)!$ vertices, where each vertex has one “$\sigma$-cycle” internal structure and one “$\tau$-matching” to another cycle. A Hamiltonian cycle in $G$ would correspond to a traversal that:
first walks along a $\sigma$-cycle segment, then uses a $\tau$-edge to jump to another coset, and continues so that each coset cycle is spliced exactly once into a global cycle.
The obstruction to a direct inductive construction is that the induced coset graph is not a simple cycle or tree; it has nontrivial overlaps coming from the interaction between right multiplication by $\sigma$ and conjugation by $\tau$. This prevents a straightforward reduction to Algorithm P–style recursion or to a wreath-product Gray code without additional structure.
No known invariant derived from parity, coset structure, or inversion statistics forces a failure of Hamiltonicity, but none yields a complete traversal scheme either.
Status
The existence of a Hamiltonian cycle in the Cayley graph of $S_n$ generated by $\sigma = (1,2,\dots,n)$ and $\tau = (1,2)$ for all odd $n \ge 3$ is not resolved by a general theorem in the standard literature on Hamiltonicity of Cayley graphs of symmetric groups. The problem remains open in this general form, with only partial constructions and computational confirmations for specific values of $n$.
This completes the solution analysis. ∎