Grasshopper avoidance of patterns (Q727190)

Summary: Motivated by a geometrical Thue-type problem, we introduce a new variant of the classical pattern avoidance in words, where jumping over a letter in the pattern occurrence is allowed. We say that pattern \(p\in E^+\) occurs with jumps in a word \(w=a_1a_2\ldots a_k \in A^+\), if there exist a non-erasing morphism \(f\) from \(E^\ast\) to \(A^*\) and a sequence \((i_1, i_2, \ldots, i_l)\) satisfying \(i_{j+1}\in\{i_j+1, i_j+2 \}\) for \(j=1, 2, \ldots, l-1\), such that \(f(p) = a_{i_1}a_{i_2}\ldots a_{i_l}.\) For example, a pattern \(xx\) occurs with jumps in a word \(abdcadbc\) (for \(x \mapsto abc\)). A pattern \(p\) is grasshopper \(k\)-avoidable if there exists an alphabet \(A\) of \(k\) elements, such that there exist arbitrarily long words over \(A\) in which \(p\) does not occur with jumps. The minimal such \(k\) is the grasshopper avoidability index of \(p\). It appears that this notion is related to two other problems: pattern avoidance on graphs and pattern-free colorings of the Euclidean plane. In particular, we show that a sequence avoiding a pattern \(p\) with jumps can be a tool to construct a line \(p\)-free coloring of \(\mathbb{R}^2\). In our work, we determine the grasshopper avoidability index of patterns \(\alpha^n\) for all \(n\) except \(n=5\). We also show that every doubled pattern is grasshopper \((2^7+1)\)-avoidable, every pattern on \(k\) variables of length at least \(2^k\) is grasshopper 37-avoidable, and there exists a constant \(c\) such that every pattern of length at least \(c\) on 2 variables is grasshopper 3-avoidable (those results are proved using the entropy compression method).