New bounds for the optimal density of covering single-insertion codes via the Turán density
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912393686155264 |
|---|---|
| author | Pikhurko, Oleg Verbitsky, Oleg Zhukovskii, Maksim |
| author_facet | Pikhurko, Oleg Verbitsky, Oleg Zhukovskii, Maksim |
| contents | 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+δ_r$ for some positive real $δ_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án density from extremal combinatorics. For the last task, we use the analytic framework of measurable subsets of the real cube $[0,1]^r$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06425 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New bounds for the optimal density of covering single-insertion codes via the Turán density Pikhurko, Oleg Verbitsky, Oleg Zhukovskii, Maksim Combinatorics Discrete Mathematics 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+δ_r$ for some positive real $δ_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án density from extremal combinatorics. For the last task, we use the analytic framework of measurable subsets of the real cube $[0,1]^r$. |
| title | New bounds for the optimal density of covering single-insertion codes via the Turán density |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2409.06425 |