Improvements on Permutation Reconstruction from Minors

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,\dots ,k$ preserving order. 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 (\hat{I}\text{c◯}(\sqrt{\ln n}))$ and $O(\sqrt{n\ln n})$. These results imply better bounds of a well-studied parameter $N_d$, which is the smallest number such that any permutation of length $n\ge N_d$ can be reconstructed by its $(n-d)$-minors. The new bounds are $d+\exp (\hat{I}\text{c◯}(\sqrt{\ln d}))<N_d<d+O(\sqrt{d\ln d})$ asymptotically, and the previous bounds were $d+{\log }_{2}d<N_d<d^2/4+2d+4$.

10 pages, 2 tables