Improvements on permutation reconstruction from minors
Authors:
- Yiming MaYMYiming Ma
- Wenjie ZhongWZWenjie Zhong
- Xiande ZhangXZXiande Zhang
- 1 January 2026
- journal article
- Published by American Institute of Mathematical Sciences (AIMS) in Advances in Mathematics of Communications
- Vol. 21, 95-106
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 $.
Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Reconstruction of hypermatrices from subhypermatricesJournal of Combinatorial Theory, Series A, 2024
- Reconstructing Young tableauxJournal of Combinatorial Theory, Series A, 2022
- Portable and Error-Free DNA-Based Data StorageScientific Reports, 2017
- Reconstruction of matrices from submatricesMathematics of Computation, 2009
- The solution to the partition reconstruction problemJournal of Combinatorial Theory, Series A, 2009
- Reconstruction from subsequencesJournal of Combinatorial Theory, Series A, 2003
- Efficient Reconstruction of Sequences from Their Subsequences or SupersequencesJournal of Combinatorial Theory, Series A, 2001
- On a Reconstruction Problem for SequencesJournal of Combinatorial Theory, Series A, 1997
- Classical Orthogonal Polynomials of a Discrete Variable1991
- Finding approximate patterns in stringsJournal of Algorithms, 1985