Nonrepetitive colorings of $R^d$
Abstract
The results of Thue state that there exists an infinite sequence over 3 symbols without 2 identical adjacent blocks, which we call a 2-nonrepetitive sequence, and also that there exists an infinite sequence over 2 symbols without 3 identical adjacent blocks, which is a 3-nonrepetitive sequence. An $r$-repetition is defined as a sequence of symbols consisting of $r$ identical adjacent blocks, and a sequence is said to be $r$-nonrepetitive if none of its subsequences are r-repetitions. Here, we study colorings of Euclidean spaces related to the work of Thue. A coloring of $R^d$ is said to be $r$- nonrepetitive of no sequence of colors derived from a set of collinear points at distance 1 is an $r$-repetition. In this case, the coloring is said to avoid r-repetitions. It was proved in [9] that there exists a coloring of the plane that avoids 2-repetitions using 18 colors, and conversely, it was proved in [3] that there exists a coloring of the plane that avoids 43-repetitions using only 2 colors. We specifically study $r$-nonrepetitive colorings for fixed number of colors : for a fixed number of colors k and dimension d, the aim is to determine the minimum multiplicity of repetition $r$ such that there exists an r-nonrepetitive coloring of $R^d$ using $k$ colors.
We prove that the plane, $R^2$, admits a 2- and a 3-coloring avoiding 33- and 18- repetitions, respectively.