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

Motivated by sequence reconstruction and reconstruction codes, we study extremal intersections of deletion balls over a fixed $q$-ary alphabet. Let ${\mathrm{\Sigma }}_q^n$ be the set of sequences of length $n$ over ${\mathrm{\Sigma }}_q$, and let $D_t(x)$ denote the set of all sequences obtained from $x\in {\mathrm{\Sigma }}_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 {\mathrm{\Sigma }}_q^n$ satisfy $D_{s-1}(x)\cap D_{s-1}(y)=\mathrm{\varnothing }$, then $$\mathrm{\mid }{D}_t(x)\cap D_t(y)\mathrm{\mid }\le \left(\genfrac{}{}{0px}{}{2s}{s}\right)\left(\genfrac{}{}{0px}{}{n-s}{t-s}\right)\mathrm{.}$$ 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<\gamma \le 1$, integers $1\le s\le t$, and $m\ge 1$, we show that if $x,y\in {\mathrm{\Sigma }}_q^n$ have at most $\gamma n$ runs and satisfy $\mathrm{\mid }{D}_s(x)\cap D_s(y)\mathrm{\mid }\le m$, then $$\mathrm{\mid }{D}_t(x)\cap D_t(y)\mathrm{\mid }\le \frac{m{\gamma }^{t-s}}{(t-s)!}{n}^{t-s}+O_{s,t,m}(n^{t-s-1})\mathrm{.}$$ 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.