
doi: 10.37236/6210
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^*$ 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).
Permutations, words, matrices, Thue sequence, Combinatorics on words, entropy compression, avoidable pattern
Permutations, words, matrices, Thue sequence, Combinatorics on words, entropy compression, avoidable pattern
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
