Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.06503 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910129799036928 |
|---|---|
| author | Wang, Xiang Fang, Weijun Li, Han Fu, Fang-Wei |
| author_facet | Wang, Xiang Fang, Weijun Li, Han Fu, Fang-Wei |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_06503 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Some New Results on Sequence Reconstruction Problem for Deletion Channels Wang, Xiang Fang, Weijun Li, Han Fu, Fang-Wei Information Theory 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$. |
| title | Some New Results on Sequence Reconstruction Problem for Deletion Channels |
| topic | Information Theory |
| url | https://arxiv.org/abs/2601.06503 |