The sequence reconstruction problem for permutations with the Hamming distance

2025-04-24 0 0 218.29KB 24 页 10玖币

侵权投诉

arXiv:2210.11864v2 [math.CO] 5 Aug 2023

The sequence reconstruction problem for permutations

with the Hamming distance

Xiang Wanga, Elena V. Konstantinova∗b,c,d

aFaculty of Science, Beijing University of Technology, Beijing, 100124, China,

E-mail address: xwang@bjut.edu.cn

bSobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk 630090, Russia

cNovosibirsk State University, Pirogova str. 2, Novosibirsk, 630090, Russia

dThree Gorges Mathematical Research Center, China Three Gorges University, 8

University Avenue, Yichang 443002, Hubei Province, China

E-mail address: e konsta@math.nsc.ru

Abstract

V. Levenshtein ﬁrst 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 diﬀerent

outputs. Assume that the transmitted sequence is at distance dfrom some

code and there are at most rerrors in every channel. Then the sequence

reconstruction problem is to ﬁnd 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 dis-

tance 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 deﬁne a Cayley graph over the symmetric group, study its proper-

ties and ﬁnd 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.

Keywords: Sequence reconstruction; Permutation codes; Hamming

distance; Cayley graph

Mathematics Subject Classiﬁcation (2000) 68P30, 05C25, 94A15

∗Corresponding author: Elena V. Konstantinova

Preprint submitted to arXiv August 8, 2023

1. Introduction

The sequence reconstruction problem was proposed in coding theory by

V. Levenshtein [8] in 2001 as a local reconstruction of sequences in the model

where the same sequence is transmitted over multiple channels, and the de-

coder receives all the distinct outputs. This problem is stated as follows.

Let Sbe a set of all sequences of length n,ρbe a metric in S, and

Br(x) = {y∈S|ρ(x, y)6r}be a metric ball of radius rcentered at x∈S.

For any integer d>1, the minimum number of transmission channels has

to be greater than the maximum intersection of two metric balls centered at

elements of Sdenoted as follows:

N(n, d, r) = max

x1,x2∈S,ρ(x1,x2)>d|Br(x1)∩Br(x2)|.(1)

The problem of determining N(n, d, r) is the sequence reconstruction problem.

The model above is presented by an error graph where vertices correspond

to sequences and edges connect vertices under error transmissions. From a

graph-theoretical point of view, this is the problem of reconstructing a vertex

by its neighbours being at a given distance from the vertex [6]. In [8, 9] this

problem was completely solved for the Hamming graph and the Johnson

graph. The main advantage in getting exact values of the minimum number

of transmission channels required to recover the transmitted sequence exactly

is that both graphs are distance-regular. This structural property allows to

apply general approaches to solve the problem for any vertex in a graph.

The situation is completely changed whenever a graph is not a distance-

regular. In [6] the main diﬃculties in solving this problem for Cayley graphs

over the symmetric group and the hyperoctahedral group that are not distance-

regular graphs are discussed. In particular, this problem was studied in [3, 5]

over permutations with reversal errors and was completely solved for r= 1.

However, even for r= 2 there are only lower bounds on (1) obtained. To get

these bounds, all possible cases of neighbourhoods of a vertex are considered.

The same diﬃculties are appeared in [4, 10] when the reconstruction prob-

lem is solved for the transposition graph. To get a complete solution, the

reconstruction of elements in the symmetric group is considered with paying

attention to conjugacy classes to which group elements belong [10].

A particular case of transposition errors, namely, transpositions of two

adjacent elements of a permutation lead to a Cayley graph over the symmet-

ric group known as the bubble-sort graph (see [6] for details). The distance

in this graph is called the bubble-sort distance in computer science [7] or

Kendall’s τ-metric in statistics [2]. Despite this graph is an induced subgraph

of the transposition graph, the complete solution of the sequence reconstruc-

tion problem of permutations distorted by these errors is still unknown. Since

the bubble-sort graph is not distance-transitive this cause diﬃculties in ﬁnd-

ing (1) in a general case. Some particular cases were solved in [12, 13].

In this paper, we study the sequence reconstruction problem of permu-

tations by the single Hamming errors. First, we present some properties of

|Br(π)∩Br(τ)|over the symmetric group with the Hamming distance for any

permutations πand τ. Then we deﬁne the Cayley graph Symn(H), n >2,

over the symmetric group Symngenerated by cycles of length at least two

and show that the distance between two permutations in this graph is the

Hamming distance. Since the graph Symn(H) is a vertex-transitive graph, we

study N(n, d, r) = maxπ∈Symnπ6=In|Br(In)∩Br(π)|,where Inis the identity

permutation, the distance between πand Inis at least d, and n>r>d

The rest of this paper is organised as follows. In Section 2, we formally

give deﬁnitions and notation with respect to the sequence reconstruction

problem over permutations under the Hamming distance. In Section 3, the

properties of the Cayley graph Symn(H), n >2,are studied. In particular,

it is shown that this graph is not distance regular. In Sections 4 and 5

we present the key technical lemma and obtain N(n, d, r) for d= 2r. In

Section 6 we give the lower bound on the value of N(n, d, r) for d= 2r−1.

2. Preliminaries

Let Symn, n >2,be the symmetric group of permutations π= [π1π2. . . πn]

written as strings in one-line notation, where πi=π(i) for any 1 6i6n,

with the identity element In= [1 2 . . . n]. It is well-known fact that any per-

mutation can be expressed as a product of disjoint cycles. For any π∈Symn,

let disc(π) = [1h12h2...nhn] be the cycle type of π, where hiis the number of

cycles of length i. We omit components with hi= 0 in disc(π). For example,

the cycle type of π= (1 2)(3 4 5)(6 7 8) ∈Sym8is written as disc(π) = [2132].

For any two permutations πand τ, the Hamming distance between them

is the number of positions in which these permutations diﬀer:

d(π, τ) = |{i∈[n]|πi6=τi}|,(2)

where [n] = {1,2, ..., n −1, n}.

Let Br(π) = {τ∈Symn|d(π, τ)6r}and Sr(π) = {τ∈Symn|d(π, τ) =

r}be a metric ball and a metric sphere of radius rcentered at a permutation

π. The sizes of Br(π) and Sr(π) do not depend on a permutation πunder

the Hamming distance [1]. For convenience, we put Br(n) = |Br(π)|and

Sr(n) = |Sr(π)|for any π∈Symn.

Now we give some useful deﬁnitions and notations on enumerative com-

binatorics following by R. Stanley [11]. A derangement of order ris a per-

mutation πwith no ﬁxed points, i.e., πi6=ifor any i∈[r]. The number Dr

of distinct derangements on relements is given by the following formula:

Dr=r!

i=0

(−1)i

i!.

Then the size of Sr(n) is given as follows:

Sr(n) = n

rDr,

and the size of Br(n) is presented as follows:

Br(n) = 1 +

i=1

Si(n) = 1 +

i=1 n

iDi.

For two integers dand r, let I(n, d, r) be the size of the maximum inter-

section of two metric balls of radius rand at distance dbetween their centers

π, τ ∈Symnsuch that:

I(n, d, r) = max

π,τ ∈Symn,d(π,τ )=d|Br(π)∩Br(τ)|.

The formula (1) can be rewritten in terms of permutations as follows:

N(n, d, r) = max

π,τ ∈Symn,d(π,τ )>d|Br(π)∩Br(τ)|= max

k>dI(n, k, r).(3)

We say that C⊂Symnis a (n, d)-permutation code under the Hamming

distance for 1 6d6n, if d(π, τ)>dfor any distinct permutations π, τ ∈C.

Assume a permutation π∈Cis transmitted over Nchannels, where Cis an

(n, d)-permutation code, and there are at most rerrors on each channel such

that all channel outputs diﬀer from each other. V. Levenshtein [8] proved

that the minimum number of channels that guarantees the decoder decodes

successfully any transmitted codeword from Cis given by N(n, d, r) + 1.

3. The Cayley graph over the symmetric group with the Hamming

distance

In this section, we deﬁne a Cayley graph over the symmetric group of per-

mutations with the Hamming distance and give some properties of sequence

reconstruction in this Cayley graph.

Let Symn(H), n >2,be the Cayley graph over the symmetric group Symn

generated by cycles of length at least two from the following set:

H={γ∈Symn|disc(γ) = [1n−ii1], i ∈[n]\{1}}.(4)

If γ∈Hwith disc(γ) = [1n−ii1] then it is obvious that disc(γ−1) = [1n−ii1],

and hence H=H−1. For any π∈Symnand any γ∈Hwith disc(γ) =

[1n−ii1] and disc(γ−1) = [1n−ii1], the weight of an edge {π, π γ}in Symn(H)

is deﬁned as i, where π γ(j) = γ(π(j)) for any j∈[n]. The distance d(π, τ)

between two permutations πand τin this graph is deﬁned as the length of

the shortest path between πand τ, that is the least sum of lengths of disjoint

cycles transforming πinto τ. By (2), we have the following statement.

Lemma 1. The distance between two permutations in Symn(H), n >2,is

the Hamming distance.

Proof. For any two permutations π, τ of the graph Symn(H), the distance

between πand τis the least sum of lengths of disjoint cycles transforming π

into τ, where each cycle contributes a value with the length of the cycle to

the Hamming distance between πand τ. Therefore, the lemma follows.

The number of permutations of a given cycle type is as follows.

Lemma 2. [11, Proposition 1.3.2] The number of permutations π∈Symn

of cycle type [1n−ii1]is equal to n!

(n−i)!·i.

Thus, by Lemma 2, it follows that

|{π|π∈Symn, disc(π) = [1n−ii1]}| =n!

(n−i)! ·i,

for any i∈[n]\{1}. Moreover, there exists an edge of weight d(π, π γ) = i

for any π∈Symnand any γ∈Hwith disc(γ) = [1n−ii1], 2 6i6n. By (4),

we immediately have:

|H|=

i=2

(n−i)! ·i.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.11864v2[math.CO]5Aug2023ThesequencereconstructionproblemforpermutationswiththeHammingdistanceXiangWanga,ElenaV.Konstantinova∗b,c,daFacultyofScience,BeijingUniversityofTechnology,Beijing,100124,China,E-mailaddress:xwang@bjut.edu.cnbSobolevInstituteofMathematics,Ak.Koptyugav.4,Novosibirsk63...

展开>> 收起<<

The sequence reconstruction problem for permutations with the Hamming distance.pdf

共24页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

The sequence reconstruction problem for permutations with the Hamming distance

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: