Skip to main content
2 of 6
added 223 characters in body
user avatar
user avatar

Avoidable words

Let $u(x_1,...,x_n)$ be a word, $k\in \mathbb{N}$. We say that $u$ is $k$-avoidable if there exists an infinite word in $k$ letters $\{a_1,...,a_k\}$ which does not contain values of $u$ (i.e. words of the form $u(v_1,...,v_n)$, $v_i\in \{a_1,...,a_k\}^+$ as a subword. For example $x^3$ is 2-avoidable and $x^2$ is 3-avoidable but not 2-avoidable because two infinite words constructed by Thue and Morse avoid $x^2$ and $x^3$. All avoidable words have been described by Bean-Ehrenfeucht-McNulty and Zimin (see these slides, for example.

  • Is there an example of a $6$-avoidable but not $5$-avoidable word?

Ronald Clark in his PhD thesis proved that $$abubawacxbcycdazdcd$$ is $5$-avoidable but not $4$-avoidable (see Clark, Ronald J. The existence of a pattern which is 5-avoidable but 4-unavoidable. Internat. J. Algebra Comput. 16 (2006), no. 2, 351–367.) There were rumors that an example of a $6$-avoidable word which is not $5$-avoidable has also been constructed. What is the status of that question?

user6976