Skirting the $n$-tuples
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908802556624896 |
|---|---|
| author | Adriaensen, Sam Ihringer, Ferdinand Martin, William J. Villagrán, Ralihe R. |
| author_facet | Adriaensen, Sam Ihringer, Ferdinand Martin, William J. Villagrán, Ralihe R. |
| contents | Let $n\ge 2$ and $q\ge 2$ be given. The set $X = \mathbb Z_q^n$ is a metric space of diameter $n$ under the Hamming metric $d(\cdot,\cdot)$. We seek a smallest set $S\subseteq X$ that ``skirts'' every $q$-ary $n$-tuple in the sense that every $x\in X$ is at distance $n$ from at least one element of $S$. Thus we aim to compute the total domination number $f(n,q)$ of the graph $G(n,q)$ with vertex set $X$ and edge set $\{ xy \, \| \, d(x,y)=n\}$. We provide constructions and bounds for this number, establishing $f(n,q) = C_q^{(1+o(1))n}$ for some constants $2=C_2>C_3 \geq \cdots$ which we are only able to estimate at the present time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_01080 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Skirting the $n$-tuples Adriaensen, Sam Ihringer, Ferdinand Martin, William J. Villagrán, Ralihe R. Combinatorics 05B40, 05B15, 05B99, 05C69, 94B65 Let $n\ge 2$ and $q\ge 2$ be given. The set $X = \mathbb Z_q^n$ is a metric space of diameter $n$ under the Hamming metric $d(\cdot,\cdot)$. We seek a smallest set $S\subseteq X$ that ``skirts'' every $q$-ary $n$-tuple in the sense that every $x\in X$ is at distance $n$ from at least one element of $S$. Thus we aim to compute the total domination number $f(n,q)$ of the graph $G(n,q)$ with vertex set $X$ and edge set $\{ xy \, \| \, d(x,y)=n\}$. We provide constructions and bounds for this number, establishing $f(n,q) = C_q^{(1+o(1))n}$ for some constants $2=C_2>C_3 \geq \cdots$ which we are only able to estimate at the present time. |
| title | Skirting the $n$-tuples |
| topic | Combinatorics 05B40, 05B15, 05B99, 05C69, 94B65 |
| url | https://arxiv.org/abs/2602.01080 |