Permutation reconstruction from minors (Q2500985)

Summary: 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 \choose 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+\log_2 k\) and \(N_k < {k^2\over4} + 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.