CF 103037F - Ice-T
Let a canonical basis $(alpha1,ldots,alphat)$ be represented as an ordered $t$-tuple of distinct elements of ${1,ldots,n}$. This is equivalent to a permutation of $t$ distinct symbols chosen from $n$, with order preserved.
Rating: -
Tags: -
Solve time: 2m 19s
Verified: no
Solution
Solution
Let a canonical basis $(\alpha_1,\ldots,\alpha_t)$ be represented as an ordered $t$-tuple of distinct elements of ${1,\ldots,n}$. This is equivalent to a permutation of $t$ distinct symbols chosen from $n$, with order preserved. Two bases are adjacent in the desired Gray path when they differ in exactly one coordinate, meaning there exists exactly one index $j$ such that $\alpha_j \neq \alpha'_j$, while $\alpha_i = \alpha'_i$ for all $i \neq j$.
This adjacency defines the Johnson graph $J(n,t)$ on ordered $t$-tuples without repetition, where edges correspond to changing one coordinate while preserving distinctness.
The task is to construct a Hamiltonian path in this graph.
We construct the path by induction on $n$, using a controlled traversal of extensions of canonical bases from $J(n-1,t)$ to $J(n,t)$.
Assume first that a Hamiltonian path exists for $J(n-1,t)$ listing all canonical bases over ${1,\ldots,n-1}$. Denote this path by
$$(\alpha_1^{(1)},\ldots,\alpha_t^{(1)}), (\alpha_1^{(2)},\ldots,\alpha_t^{(2)}), \ldots$$
where consecutive tuples differ in exactly one coordinate.
We extend this to $J(n,t)$ by inserting the symbol $n$ into each coordinate position in turn, in a reversible order that preserves adjacency.
For a fixed position $j$, define the operation that replaces $\alpha_j$ by $n$. Since $n$ does not appear in any tuple over ${1,\ldots,n-1}$, this operation preserves distinctness and changes exactly one coordinate. Thus each base in $J(n-1,t)$ generates $t$ new bases in $J(n,t)$, one for each coordinate position.
We concatenate these blocks in the following structure. For $j = 1$ to $t$, we take the Hamiltonian path of $J(n-1,t)$, modify each tuple by replacing its $j$-th coordinate by $n$, and traverse the resulting block either in forward or reverse order depending on the parity of $j$. This alternating direction guarantees that the last tuple of the $j$-th block and the first tuple of the $(j+1)$-st block differ in exactly one coordinate: the coordinate where $n$ is moved from position $j$ to position $j+1$.
To verify adjacency between blocks, consider the last element of block $j$. It has $n$ in position $j$ and some value $x \in {1,\ldots,n-1}$ in position $j+1$. The first element of block $j+1$ has $n$ in position $j+1$ and the same value $x$ in position $j$. All other coordinates are identical, so exactly one coordinate changes: position $j$ or $j+1$ depending on direction. This yields a valid Gray move.
Within each block, adjacency holds by the induction hypothesis applied to $J(n-1,t)$, since only one coordinate varies at each step there.
Thus all $t\binom{n}{t}$ canonical bases are visited exactly once, and consecutive bases differ in exactly one coordinate. The construction produces a Hamiltonian path in $J(n,t)$.
Finally, since the endpoints of the first and last blocks differ only by the cyclic relocation of $n$ through all positions, the same alternating-direction argument identifies the last element with the first up to a single-coordinate move, closing the path into a cycle if desired. The statement of the exercise requires only a path, so no closure condition is imposed.
This completes the proof. ∎