Permutations Resilient to Deletions

Let M= (s₁, s₂, … , 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.