Perfect Snake-in-the-Box Codes for Rank Modulation
Alexander E. Holroyd · IEEE Transactions on Information Theory · 2016
For odd n, the alternating group on n elements is generated by the permutations that jump an element from an odd position to position 1. We prove Hamiltonicity of the associated directed Cayley graph for all odd n ≠ 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.