# Ü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 '14 at 1:51

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 '14 at 1:31