TY - JOUR

T1 - The sequence reconstruction of permutations with Hamming metric

AU - Wang, Xiang

AU - Fu, Fang-Wei

AU - Konstantinova, Elena v.

N1 - The authors would like to express their sincere gratefulness to the editor and the three anonymous reviewers for their valuable suggestions and comments which have greatly improved this paper. The work of X. Wang is supported by the National Natural Science Foundation of China (Grant No. 12001134). The work of F.-W. Fu is supported by the National Key Research and Development Program of China (Grant No. 2022YFA1005000), the National Natural Science Foundation of China (Grant Nos. 12141108, 62371259, 12226336), the Fundamental Research Funds for the Central Universities of China (Nankai University), and the Nankai Zhide Foundation. The work of Elena V. Konstantinova is supported by the state contract of the Sobolev Institute of Mathematics (Project No. FWNF-2022-0017).

PY - 2024/10/26

Y1 - 2024/10/26

N2 - In the combinatorial context, one of the key problems in sequence reconstruction is to find the largest intersection of two metric balls of radius r. In this paper we study this problem for permutations of length n distorted by Hamming errors and determine the size of the largest intersection of two metric balls with radius r whose centers are at distance . Moreover, it is shown that for any an arbitrary permutation is uniquely reconstructible from four distinct permutations at Hamming distance at most two from the given one, and it is proved that for any an arbitrary permutation is uniquely reconstructible from distinct permutations at Hamming distance at most three from the permutation. It is also proved that for any an arbitrary permutation is uniquely reconstructible from distinct permutations at Hamming distance at most four from the permutation. Finally, in the case of at most r Hamming errors and sufficiently large n, it is shown that at least distinct erroneous patterns are required in order to reconstruct an arbitrary permutation.

AB - In the combinatorial context, one of the key problems in sequence reconstruction is to find the largest intersection of two metric balls of radius r. In this paper we study this problem for permutations of length n distorted by Hamming errors and determine the size of the largest intersection of two metric balls with radius r whose centers are at distance . Moreover, it is shown that for any an arbitrary permutation is uniquely reconstructible from four distinct permutations at Hamming distance at most two from the given one, and it is proved that for any an arbitrary permutation is uniquely reconstructible from distinct permutations at Hamming distance at most three from the permutation. It is also proved that for any an arbitrary permutation is uniquely reconstructible from distinct permutations at Hamming distance at most four from the permutation. Finally, in the case of at most r Hamming errors and sufficiently large n, it is shown that at least distinct erroneous patterns are required in order to reconstruct an arbitrary permutation.

UR - https://www.webofscience.com/wos/woscc/full-record/WOS:001335086500005

U2 - 10.1007/s10623-024-01509-4

DO - 10.1007/s10623-024-01509-4

M3 - Article

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

SN - 0925-1022

ER -