Permutation Reconstruction from Minors - Raykova, Mariana (The Electronic Journal of Combinatorics, 2006)
We consider the problem of permutation reconstruction, which is a variant of graph reconstruction. Given a permutation p of length n, we delete k of its entries in each possible way to obtain n k subsequences. We renumber the sequences from 1 to n-k preserving the relative size of the elements to form (n-k)-minors. These minors form a multiset M_k(p) with an underlying set M_k’(p). We study the question of when we can reconstruct p from its multiset or its set of minors. We prove there exists an N_k for every k such that any permutation with length at least N_k is reconstructible from its multiset of (n-k)-minors. We find the bounds N_k > k+_2 k and N_k < k^24 + 2k + 4. For the number N_k’, giving the minimal length for permutations to be reconstructible from their sets of (n-k)-minors, we have the bound N_k’ > 2k. We work towards analogous bounds in the case when we restrict ourselves to layered permutations.