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

DOI10.1109/TIT.2016.2620160zbMATH Open1359.94798arXiv1602.08073OpenAlexW2963304363MaRDI QIDQ2979080FDOQ2979080

A. E. Holroyd

Publication date: 2 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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 not equal to 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.

Full work available at URL: https://arxiv.org/abs/1602.08073

Mathematics Subject Classification ID

Combinatorial codes (94B25) Modulation and demodulation in information and communication theory (94A14)

Cited In (11)

• Title not available (Why is that?)
• Isomorphism of maximum length circuit codes
• Snake-in-the-Box Codes for Rank Modulation
• Title not available (Why is that?)
• Sparse Kneser graphs are Hamiltonian
• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• Kneser graphs are Hamiltonian
• On a Combinatorial Generation Problem of Knuth
• Gray codes and symmetric chains
• Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric

This page was built for publication: Perfect Snake-in-the-Box Codes for Rank Modulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2979080)