论文标题
与锤距的排列的序列重建问题
The sequence reconstruction problem for permutations with the Hamming distance
论文作者
论文摘要
V. Levenshtein在2001年首先提出了序列重建问题。该问题研究了模型，其中某些集合的相同序列在多个通道上传输，解码器接收到不同的输出。假设传输序列在距离某些代码的距离为$ d $，并且每个频道中最多都有$ r $错误。然后，序列重建问题是找到精确恢复的传输序列所需的最小频道数量，该序列必须大于两个半径$ r $的公制球之间的最大相交，其中其中心之间的距离至少为$ d $。在本文中，我们研究了在锤距离距离下排列的序列重建问题。在此模型中，我们在对称组上定义了一个Cayley图，研究其属性，并以$ d = 2r $的形式找到其两个度量球的最大交叉点的确切值。此外，我们以$ d = 2R-1 $的两个度量球的最大交叉点给出了一个下限。
V. Levenshtein first proposed the sequence reconstruction problem in 2001. This problem studies the model where 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$.
