Improvements on permutation reconstruction from minors

We study the reconstruction problem of permutation sequences from their k-minors, which are subsequences of length k with entries renumbered by 1,2,…,k preserving order. This can be viewed as a generalization of permutation codes correcting deletion errors and the sequence reconstruction problem, both introduced by Levenshtein. We prove that the minimum number k such that any permutation of length n can be reconstructed from the multiset of its k-minors is between exp(Ω(√ln n)) and O(√nln n). Our results determine a well-studied parameter Nd = d+o(d) asymptotically, which is the smallest number such that any permutation of length n≥ Nd can be reconstructed by its $ (n-d) $-minors. Previously, the bounds of Nd were $ d+log_2 d<N_d