4 added 1176 characters in body

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 of George McNulty's talk, for example.

Update Since according to James Currie, the above is almost as much as we know, as far as the lower bound is concerned, here is the best upper bounds I know. Let $k$ ibe the number of letters in an avoidable word $u$, $n=n(k)$ is the minimal $n$ such that all such $u$ are $n$-avoidable. An exponential upper bound for $n(k)$ was found in the original papers by Bean-Ehrenfeucht-McNulty and Zimin, quadratic upper bound - in my paper, 1987 (I considered a more complicated problem of avoidability of identities) and a linear upper bound $9k+20$ in Baker, McNulty, Taylor, Growth problems for avoidable words. Theoret. Comput. Sci. 69 (1989), no. 3, 319–345. The best upper bound I know is $n(k)\le 3\lfloor k/2\rfloor+3$. It was proved by Irina Mel'nichuk in "On the existence of infinite finitely generated free semigroups in some varieties of semigroups", Leningrad Algebraic Systems with One Operation and Relations (1985), pp. 74–83. George McNulty claims in the talk I linked to above that Mel'nichuk proved the upper bound $k+6$ in 1988, but I could not find a reference. The question is whether $k(n)$ is bounded by a constant.

3 added 324 characters in body

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?

The word $x^3$ is 2-avoidable but not 1-avoidable.

The word $x^2$ is $3$-avoidable (Thue) but not 2-avoidable (obvious).

Walter's word $$abwbcxcayba$$ is 4-avoidable but not $3$-avoidable.

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.)

It is of course hard to believe that every avoidable word is $5$-avoidable (or $C$-avoidable for any constant $C$). 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?

2 added 223 characters in body

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 $5$-avoidable 6$-avoidable but not$4$-avoidable 5$-avoidable word?

Ronald Clark in his PhD thesis claimed proved that $$abubawacxbcycdazdcd$$ is such $5$-avoidable but not $4$-avoidable (see Clark, Ronald J. The existence of a wordpattern which is 5-avoidable but 4-unavoidable. But his thesis Internat. J. Algebra Comput. 16 (UCLA, 20012006), no. 2, 351–367.) does There were rumors that an example of a $6$-avoidable word which is not seem to be published$5$-avoidable has also been constructed. What is the status of that resultquestion?

1