TY - JOUR

T1 - The sequence reconstruction problem for permutations with the Hamming distance

AU - Wang, Xiang

AU - Konstantinova, Elena V.

N1 - The authors are very grateful to both referees for carefully reviewing the manuscript and for making many useful suggestions which greatly improved the paper. Our special thanks go to the anonymous referee who suggests to give more explanations in a few proofs. The work of Xiang Wang is supported by the National Natural Science Foundation of China (Grant No. 12001134), and the work of Elena V. Konstantinova is supported by the Mathematical Center in Akademgorodok, under agreement No. 075-15-2022-281 with the Ministry of Science and High Education of the Russian Federation.

PY - 2024/9

Y1 - 2024/9

N2 - V. Levenshtein first proposed the sequence reconstruction problem in 2001. This problem studies the same sequence from some set is transmitted over multiple channels, and the decoder receives the different outputs. Assume that the transmitted sequence is at distance d from some code and there are at most r errors in every channel. Then the sequence reconstruction problem is to find the minimum number of channels required to recover exactly the transmitted sequence that has to be greater than the maximum intersection between two metric balls of radius r, where the distance between their centers is at least d. In this paper, we study the sequence reconstruction problem of permutations under the Hamming distance. In this model we define a Cayley graph over the symmetric group, study its properties and find the exact value of the largest intersection of its two metric balls for d=2r. Moreover, we give a lower bound on the largest intersection of two metric balls for d=2r-1.

AB - V. Levenshtein first proposed the sequence reconstruction problem in 2001. This problem studies the same sequence from some set is transmitted over multiple channels, and the decoder receives the different outputs. Assume that the transmitted sequence is at distance d from some code and there are at most r errors in every channel. Then the sequence reconstruction problem is to find the minimum number of channels required to recover exactly the transmitted sequence that has to be greater than the maximum intersection between two metric balls of radius r, where the distance between their centers is at least d. In this paper, we study the sequence reconstruction problem of permutations under the Hamming distance. In this model we define a Cayley graph over the symmetric group, study its properties and find the exact value of the largest intersection of its two metric balls for d=2r. Moreover, we give a lower bound on the largest intersection of two metric balls for d=2r-1.

KW - 05C25

KW - 68P30

KW - 94A15

KW - Cayley graph

KW - Hamming distance

KW - Permutation codes

KW - Sequence reconstruction

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85191941378&origin=inward&txGid=4bd6314696fe2ced3a805923203b52d2

UR - https://www.mendeley.com/catalogue/68e0abbd-d7e8-3a31-bd3b-40d653f4d95c/

U2 - 10.1007/s12095-024-00717-y

DO - 10.1007/s12095-024-00717-y

M3 - Article

VL - 16

SP - 1033

EP - 1057

JO - Cryptography and Communications

JF - Cryptography and Communications

SN - 1936-2447

IS - 5

ER -