New bounds for the optimal density of covering single-insertion codes via the Tur\'an density
<|reference_start|>New bounds for the optimal density of covering single-insertion codes via the Tur\'an density: We prove that the density of any covering single-insertion code $C\subseteq X^r$ over the $n$-symbol alphabet $X$ cannot be smaller than $1/r+\delta_r$ for some positive real $\delta_r$ not depending on $n$. This improves the volume lower bound of $1/(r+1)$. On the other hand, we observe that, for all sufficiently large $r$, if $n$ tends to infinity then the asymptotic upper bound of $7/(r+1)$ due to Lenz et al (2021) can be improved to $4.911/(r+1)$.   Both the lower and the upper bounds are achieved by relating the code density to the Tur\'an density from extremal combinatorics. For the last task, we use the analytic framework of measurable subsets of the real cube $[0,1]^r$.<|reference_end|>
@article{pikhurko2024new,
    title={New bounds for the optimal density of covering single-insertion codes
  via the Tur\'an density},
    author={Oleg Pikhurko, Oleg Verbitsky, and Maksim Zhukovskii},
    journal={arXiv preprint arXiv:2409.06425},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.06425},
    primaryClass={math.CO cs.DM}
}