Grasshopper avoidance of patterns
type: Item
instance of: scholarly article
title: Grasshopper avoidance of patterns
zbMATH Open document ID: 1351.05007
author: Michał Dębski
author: Urszula Pastwa
author: Krzysztof Węsek
published in: The Electronic Journal of Combinatorics
publication date: 2016-12-06T00:00:00Z
full work available at URL: v23i4p17
review text: 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).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6661369
zbMATH Keywords: Thue sequence
zbMATH Keywords: avoidable pattern
zbMATH Keywords: entropy compression
MaRDI profile type: Publication
cites work: Avoidable patterns in strings of symbols
cites work: Exponential lower bounds for the number of words of uniform length avoiding a pattern
cites work: The origins of combinatorics on words
cites work: Unavoidable binary patterns
cites work: THE EXISTENCE OF A PATTERN WHICH IS 5-AVOIDABLE BUT 4-UNAVOIDABLE
cites work: Pattern avoidance: themes and variations
cites work: Non-repetitive tilings
cites work: Thue-like sequences and rainbow arithmetic progressions
cites work: Pattern avoidance on graphs
cites work: Thue type problems for graphs, points, and numbers
cites work: Nonrepetitive colorings of line arrangements
cites work: On a generalization of Thue sequences
cites work: Q4529547
cites work: Q4681771
cites work: A constructive proof of the Lovász local lemma
cites work: A generator of morphisms for infinite words
cites work: Doubled patterns are 3-avoidable
cites work: Application of entropy compression in pattern avoidance
cites work: Every binary pattern of length six is avoidable on the two-letter alphabet
cites work: Avoidable patterns on two letters
cites work: Chromatic Number of the Plane & Its Relatives, History, Problems and Results: An Essay in 11 Parts
cites work: Nonrepetitive and pattern-free colorings of the plane
cites work: BLOCKING SETS OF TERMS
description: scientific article; zbMATH DE number 6661369