Nonrepetitive and pattern-free colorings of the plane

A classic result of Thue states that using 33 symbols one can construct an infinite nonrepetitive   sequence, that is, a sequence without two identical adjacent blocks. In this paper, we present Thue-type results concerning coloring of the Euclidean plane, related to the famous Hadwiger–Nelson problem. This old problem asks for the chromatic number of the unit distance graph of the plane, the infinite graph with the set of vertices of R2R2 and edges between points at distance 11.We solve a problem posed by Grytczuk (2008) by showing that any coloring of the unit distance graph of R2R2 in which the sequence of colors of every simple path is nonrepetitive needs more than countable number of colors. Grytczuk, Kosiński and Zmarz (2016) introduced a relaxation of this problem, by restricting the nonrepetitiveness condition to a certain class of paths. Let a path in the unit distance graph of R2R2 be called line path   if it consists of collinear points. A coloring of R2R2 is line nonrepetitive   if the sequence of colors on every line path is nonrepetitive. We present a line nonrepetitive 1818-coloring of R2R2, which improves the result of Grytczuk, Kosiński and Zmarz with 3636 colors. Furthermore, we construct a line nonrepetitive coloring, which additionally avoids palindromes and uses 3232 colors.We also consider a natural generalization of this problem to other patterns. We say that a pattern  qq (finite sequence over a set of variables EE) occurs   in a sequence ww (over an alphabet AA) if there exists a substitution ff from EE to the set of nonempty sequences over AA such that f(q)f(q) is a block in ww. A sequence wwavoids   a pattern qq if qq does not occur in ww. For a pattern qq, a coloring of R2R2 is called line  pp-free   if the sequence of colors on every line path avoids qq. We present a 99-coloring of R2R2 which is line αααααα-free and line αβαβαβαβ-free at once. Moreover, we give a non-constructive result for a class of patterns. Namely, let qq be a pattern with no variable occurring exactly once or satisfying ℓ⩾2dℓ⩾2d, where ℓℓ is the length of qq and dd is the number of variables in qq. Then there exists a line qq-free coloring of R2R2 using a finite number of colors. In fact, this result holds even if (instead of taking into account only line paths) we consider all sequences of points in R2R2 with consecutive distances in some fixed interval [a,b][a,b] and without any pair of vertices at distance smaller than a fixed ε>0ε>0.