Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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
1  
@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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.