## Abstract

Let M= (s_{1}, s_{2}, … , s_{n}) 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 language | English (US) |
---|---|

Journal | Annals of Combinatorics |

DOIs | |

State | Published - Jan 1 2018 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics

## Keywords

- Deletion channel
- Double path graph
- Permutations
- Recovery