Arranging all permutations on $\{1,\ldots,n\}$ such that there are no common points

Question

If $n>0$ is an integer, let $[n]=\{1,\ldots,n\}$. Let $S_n$ denote the set of all permutations (bijections) $\pi:[n]\to[n]$.

For which positive integers $n$ is there a bijection $\Phi:[n!]\to S_n$ such that for all $x\in[n!-1]$ we have $ (\Phi(x))(k) \neq (\Phi(x+1))(k) \text{ for all }k\in [n]$?

---

Note. This can be formulated in the language of Hamiltonian paths: Put a graph structure on $S_n$ saying that $\pi_1,\pi_2\in S_n$ form an edge if $\pi_1(k)\neq \pi_2(k)$ for all $k\in[n]$, and find a Hamiltonian path in this graph.

Answer 1

We are basically looking at the Cayley graph of $S_n$ where the generating set is the set of all derangements. The question is whether this graph is Hamiltonian.

I will quote here a paper by Rasmussen and Savage, several further references on this problem can be found there

David J. Rasmussen, Carla D. Savage: Hamilto-connected derangement graphs on $S_n$, Discrete Mathematics, Volume 133, Issues 1–3, Pages 217-223; DOI: 0012-365X(94)90028-0, Zbl 0808.05069, MR1298976

Abstract. We consider the derangements graph in which the vertices are permutations of $\{1,\dots,n\}$. Two vertices are joined by an edge if the corresponding permutations differ in every position. The derangements graph is known to be hamiltonian and it follows from a recent result of Jung that every pair of vertices is joined by a Hamiltonian path. We use this result to settle an open question, by showing that it is possible, for any n and k satisfying $2\le k\le n$ and $k\ge3$, to generate permutations of $\{1,\dots,n\}$ so that successive permutations differ in $k$ consecutive positions. In fact, the associated $k$-consecutive derangements graph is also Hamilton-connected.

Answer 2

it is still of interest to me, I would be glad to hear about it!

OK, sorry for the delay. This elementary argument is, probably, well-known but I was too lazy to make a thorough search, so if somebody has a reference to something similar, it will be appreciated.

Consider all cyclic shifts of a permutation $\pi$. Note that any two of them can be placed next to each other, so we can try to make them single blocks. Let's denote the corresponding blocks by $C$ (there are $(n-1)!$ of them). Now two blocks $C'$ and $C''$ are possible to place next to each other if the corresponding permutations $\pi'$ and $\pi''$ have the property that some cyclic shift of $\pi''$ has no common elements with $\pi'$. When we try to consider all cyclic shifts of $\pi''$, each element of $\pi'$ has only one chance to coincide with the element of the shift of $\pi''$ in the same position, so we have total of $n$ coincidences. If some shift of $\pi''$ has 2 or more common elements with $\pi'$, then there is another shift with no common elements. Now, shift both $\pi'$ and $\pi''$ so that $1$ is in the same position. If no other elements coincide, we have a derangement of length $n-1$. Thus, only about $(n-1)!/e$ blocks are incompatible with a given block, so we can make a Hamiltonian cycle of blocks such that every 2 adjacent blocks are compatible (with accurate count, it works for $n\ge 4$). It remains to place permutations without common elements at the junction points. Note that once we have $\pi'\in C'$ and $\pi''\in C''$ without common elements, any simultaneous cyclic shift of those will give you another pair without common elements. Thus we have $\ge n$ pairs that we can place at any particular junction. Just place them one by one in any order and notice that when you do any junction, you can have at most 2 conflicts with 2 adjacent junctions, so if $n\ge 3$, the Hamiltonian cycle of blocks can be upgraded to a Hamiltonian cycle of permutations.

Answer 3

For $n=4$ it is doable. A Hamiltonian cycle is $$[[1, 2, 3, 4], [2, 1, 4, 3], [1, 3, 2, 4], [2, 4, 1, 3], [1, 3, 4, 2], [2, 1, 3, 4], [1, 2, 4, 3], [2, 3, 1, 4], [1, 4, 2, 3], [2, 3, 4, 1], [1, 4, 3, 2], [3, 1, 2, 4], [2, 4, 3, 1], [4, 1, 2, 3], [3, 2, 1, 4], [4, 1, 3, 2], [3, 2, 4, 1], [4, 3, 1, 2], [3, 4, 2, 1], [4, 2, 1, 3], [3, 1, 4, 2], [4, 2, 3, 1], [3, 4, 1, 2], [4, 3, 2, 1], [1, 2, 3, 4]]$$