Sequences with long range exclusions

Abstract

Given an alphabet $S$, we consider the size of the subsets of the full sequence space $S^{\mathbf{Z}}$ determined by the additional restriction that $x_i\ne x_{i+f(n)},i\in \mathbf{Z},n\in \mathbf{N}.$ Here $f$ is a positive, strictly increasing function. We review an other, graph theoretic, formulation and then the known results covering various combinations of $f$ and the alphabet size. In the second part of the paper we turn to the fine structure of the allowed sequences in the particular case where $f$ is a suitable polynomial. The generation of sequences leads naturally to consider the problem of their maximal length, which turns out highly random asymptotically in the alphabet size.

18 pages, 3 figures. Replaces earlier version, submission 1204.3439, major update