Some New Results on Sequence Reconstruction Problem for Deletion Channels
Provides a combinatorial result for the sequence reconstruction problem under deletion channels, relevant to coding theory and information theory.
The paper establishes a lower bound on the maximum intersection size of two metric balls of radius t for deletion channels, and proves it is tight for t=4, settling an open question by confirming that N(n,3,4)=20n-166 for n≥13.
Levenshtein first introduced the sequence reconstruction problem in $2001$. In the realm of combinatorics, the sequence reconstruction problem is equivalent to determining the value of $N(n,d,t)$, which represents the maximum size of the intersection of two metric balls of radius $t$, given that the distance between their centers is at least $d$ and the sequence length is $n$. In this paper, We present a lower bound on $N(n,3,t)$ for $n\geq \max\{13,t+8\}$ and $t \geq 4$. For $t=4$, we prove that this lower bound is tight. This settles an open question posed by Pham, Goyal, and Kiah, confirming that $N(n,3,4)=20n-166$ for all $n \geq 13$.