Permutations Resilient to Deletions

Noga Alon, Steve Butler, Ron Graham, Utkrisht C. Rajkumar

Research output: Contribution to journalArticlepeer-review

Abstract

Let M= (s1, s2, … , sn) be a sequence of distinct symbols and σ a permutation of { 1 , 2 , … , n}. Denote by σ(M) the permuted sequence (sσ ( 1 ), sσ ( 2 ), … , sσ ( n )). For a given positive integer d, we will say that σ is d-resilient if no matter how d entries of M are removed from M to form M and d entries of σ(M) are removed from σ(M) to form σ(M) (with no symbol being removed from both sequences), it is always possible to reconstruct the original sequence M from M and σ(M) . Necessary and sufficient conditions for a permutation to be d-resilient are established in terms of whether certain auxiliary graphs are acyclic. We show that for d-resilient permutations for [n] to exist, n must have size at least exponential in d, and we give an algorithm to construct such permutations in this case. We show that for each d and all sufficiently large n, the fraction of all permutations on n elements which are d-resilient is bounded away from 0.

Original languageEnglish (US)
JournalAnnals of Combinatorics
DOIs
StatePublished - Jan 1 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Keywords

  • Deletion channel
  • Double path graph
  • Permutations
  • Recovery

Fingerprint Dive into the research topics of 'Permutations Resilient to Deletions'. Together they form a unique fingerprint.

Cite this