8
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Do you have experimental results for small $n$? My guess would be for all $n$ not equal to $3$, since there is so much freedom in the choices. $\endgroup$ – WhatsUp May 29 '19 at 11:35
  • $\begingroup$ I haven't been able to do it for $n=4$ (which is not a proof it is not doable) $\endgroup$ – Dominic van der Zypen May 29 '19 at 12:08
  • $\begingroup$ Update: Robert Israel just showed below that $n=4$ does have a Hamiltonian path (which is even a cycle). $\endgroup$ – Dominic van der Zypen May 29 '19 at 13:17
  • $\begingroup$ You should be able to generate such a path by applying a shift (12...n) n-1 times in succession, followed by a derangement which is a product of a shift and some permutation. The question becomes which derangements besides a cycle do you need to generate all permutations in this order. Gerhard "It's Another Kind Of Algebra" Paseman, 2019.05.29. $\endgroup$ – Gerhard Paseman May 29 '19 at 15:45
19
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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]]$$

$\endgroup$
  • 4
    $\begingroup$ There is this result by Dirac that states that if the minimum degree of a graph $G=(V,E)$ is larger than $|V(G)|/2$ then $G$ has a Hamiltonian cycle. Maybe such an argument can be applied here? $\endgroup$ – Dominic van der Zypen May 29 '19 at 14:25
  • 6
    $\begingroup$ @DominicvanderZypen The vertex degree here is only about $|V|/e$, so it is a bit short of what you want. $\endgroup$ – fedja May 29 '19 at 14:27
  • 3
    $\begingroup$ Here is a short program for sage that gives you a Hamiltonian cycle for $n=5$: $\verb|G = lambda n: Graph([Permutations(n), lambda pi1, pi2: all(e != f for e, f in zip(pi1, pi2))])|$ $\verb|G(5).hamiltonian_cycle(algorithm='backtrack')|$ $\endgroup$ – Martin Rubey May 29 '19 at 15:24
  • 1
    $\begingroup$ @DominicvanderZypen Actually, you can derive the existence of the Hamiltonian cycle drom Dirac's criterion but you have to apply it to some other graph. Let me know if it is still of any interest to you. $\endgroup$ – fedja May 30 '19 at 1:27
  • 1
    $\begingroup$ @DominicvanderZypen OK, posted. $\endgroup$ – fedja Jun 2 '19 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.