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](http://en.wikipedia.org/wiki/Square-free_word)*.


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](http://en.wikipedia.org/wiki/Avoidable_pattern#Examples).


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?



Über theorem on unavoidable patterns?
According to the 2013 paper ["Computing the Partial Word Avoidability Indices of
Ternary Patterns"](https://www.uncg.edu/cmp/research/patterns2/TernaryPatterns.pdf) 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.


