# Über theorem on unavoidable patterns?

Let $A$ be an alphabet of $k$ symbols, and $p$ a pattern. An example of a pattern is $p=XX$, where $X$ is any finite string of symbols from $A^+$. Avoiding $p$ is avoiding any subword repeated twice in a row. Such strings are called square-free.

It is well known that there are no infinite binary ($k=2$) strings of symbols that are square-free (in fact, only $0$, $1$, $01$, $10$, $010$, and $101$ are square-free), but there are infinite ternary ($k=3$) square-free strings, as proved by Axel Thue.

Other examples: the patterns $X$ and $XYX$ are unavoidable on any alphabet.

My question is:

Q. Is there a theorem of the form: Any alphabet $A$ with $|A| \le k$ cannot avoid any patterns $p$ of the form [some description of these patterns $p$ as a function of $k$], i.e., there are no infinite strings that avoid these $p$?

In other words, is there a pattern to—a characterization of—the patterns that are unavoidable, for a given $k$? Or are there, to date, only claims that specific patterns are unavoidable?

-
mathoverflow.net/questions/93997/avoidable-words is relevant, if not a duplicate. –  The Masked Avenger Jul 19 at 1:51

According to the 2013 paper "Computing the Partial Word Avoidability Indices of Ternary Patterns" by Blanchet-Sadri, Lohr, and Scott,

The problem of deciding whether a given pattern is avoidable has been solved [1, 14], but the one of deciding whether it is k-avoidable has remained open.

So, it seems to be an open problem.

-
Thanks, Bjørn! [14] is Zimin's 1984 paper. Apparently Zimin characterized unavoidable patterns. But as you indicate, without restriction to $k$ symbols. –  Joseph O'Rourke Jul 19 at 1:31
@JosephO'Rourke An interesting factoid that you didn't mention is that the famous Thue-Morse word 01101001... avoids the pattern XYXYX, and such words are called "overlap-free" (or "irreducible" or "strongly cube-free") because any overlap of a word with itself would have to follow such a pattern. –  Bjørn Kjos-Hanssen Jul 19 at 1:43
The English language does not consist of irreducible words only, however, as there is "alfalfa". –  Bjørn Kjos-Hanssen Jul 19 at 1:44
Great example! Maybe entente qualifies as an overlap word, but it is really French (cf. détente). Surely overlap words exist in many languages... –  Joseph O'Rourke Jul 19 at 1:57