Extremal Deletion-Ball Intersections under Run-Count and Lower-Order Deletion-Ball Intersection Constraints

Abstract

Motivated by sequence reconstruction and reconstruction codes, we study extremal intersections of deletion balls over a fixed $q$-ary alphabet. Let $\hat{I}{\pounds }_q^n$ be the set of sequences of length $n$ over $\hat{I}{\pounds }_q$, and let $D_t(x)$ denote the set of all sequences obtained from $x\in \hat{I}{\pounds }_q^n$ by deleting exactly $t$ symbols. Our first result gives a finite upper bound under a lower-order deletion-correction constraint. We prove that if $x,y\in \hat{I}{\pounds }_q^n$ satisfy $D_{s-1}(x)\cap D_{s-1}(y)=\varnothing$, then \[ |D_t(x)\cap D_t(y)| \le \binom{2s}{s}\binom{n-s}{t-s}. \] For binary alphabets, this strengthens a recent asymptotic upper bound of Pham, Goyal, and Kiah (2025, JCTA). We then investigate deletion-ball intersections under simultaneous constraints on run counts and lower-order deletion-ball intersections. For fixed $0<{\hat{I}}^3\le 1$, integers $1\le s\le t$, and $m\ge 1$, we show that if $x,y\in \hat{I}{\pounds }_q^n$ have at most ${\hat{I}}^{3}n$ runs and satisfy $|D_s(x)\cap D_s(y)|\le m$, then \[ |D_t(x)\cap D_t(y)|\le \frac{mγ^{t-s}}{(t-s)!}n^{t-s}+O_{s,t,m}(n^{t-s-1}). \] Moreover, the leading term can be attainable whenever $m$ is realized by a fixed finite-length seed pair. As a consequence, we obtain a direct lifting theorem for deletion reconstruction codes, transferring reconstruction properties from radius $s$ to larger radii $t$. Finally, we establish a parallel insertion theory and derive corresponding results for insertion-ball intersections and insertion reconstruction codes.

15 pages