Skirting the $n$-tuples

Abstract

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\Vert 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\ge \cdots$ which we are only able to estimate at the present time.

7 pages