Constructing Optimal $k$-Radius Sequences
Adrian Bondy, Zbigniew Lonc, Paweł Rzążewski · SIAM Journal on Discrete Mathematics · 2016
A $k$-radius sequence over an $n$-element alphabet $A$ is a sequence in which every two elements of $A$ appear within distance at most $k$ (where the distance is defined as the difference of indices). By a $k$-radius sequence over an $n$-element alphabet $A$ we mean a sequence in which every two elements of $A$ appear within distance at most $k$. The problem of constructing shortest possible $k$-radius sequences, motivated by some problems occurring in large data transfer, has been studied by several authors recently. In this paper we present an explicit construction of “short” $k$-radius sequences for some values of $k$ and $n$. This construction allows us to find 2-radius sequences of the shortest possible length for all but very special values of $n$. For all $n$ we construct 2-radius sequences whose length differs from the length of the shortest one only by a constant. Moreover, we construct shortest possible $k$-radius sequences when $n=2k^2+2k+1$ and $k$ is a power of a prime. Our construction depends on the existence of some other sequences that we call $k$-perfect and $k$-additive. We investigate these sequences as they seem to be interesting in themselves.