Perfect Snake-in-the-Box Codes for Rank Modulation

For odd n, the alternating group on n elements is generated by the permutations that jump an element from any odd position to position 1. We prove Hamiltonicity of the associated directed Cayley graph for all odd n 6= 5. (A result of Rankin implies that the graph is not Hamiltonian for n ≠ 5.) This solves a problem arising in rank modulation schemes for flash memory. Our result disproves a conjecture of Horovitz and Etzion, and proves another conjecture of Yehezkeally and Schwartz.