Sequences with long range exclusions

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≠x_{i+f(n)},i\in \mathbf{Z},n\in \mathbf{N}\mathrm{.}$ 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.