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 $Σ_q^n$ be the set of sequences of length $n$ over $Σ_q$, and let $D_t(x)$ denote the set of all sequences obtained from $x\inΣ_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Σ_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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.25822
curl -X POST /api/v1/records/arxiv/2606.25822/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.25822/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'