Abstract
We study the reconstruction problem of permutation sequences from their $ k $-minors, which are subsequences of length $ k $ with entries renumbered by $ 1,2,\ldots,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{(\Omega(\sqrt{\ln n}))} $ and $ O(\sqrt{n\ln n}) $. Our results determine a well-studied parameter $ N_d = d+o(d) $ asymptotically, which is the smallest number such that any permutation of length $ n\ge N_d $ can be reconstructed by its $ (n-d) $-minors. Previously, the bounds of $ N_d $ were $ d+\log_2 d<N_d<d^2/4+2d+4 $.

This publication has 23 references indexed in Scilit: