Unavoidable pattern

In mathematics and theoretical computer science, a pattern(term) is a sequence of characters over some alphabet $\Delta$. A word $w$ avoids pattern $p$ if $p$ does not match $w$. If $w$ avoids $p$, $w$ is also called $p$-free.

A word $w$ matches pattern $p$ if there exists a factor(subword) of $w$, which is also an instance of $p$.

A word $x\in \Sigma ^{*}$ is an instance of pattern $p\in \Delta ^{*}$, if there exists a non-erasing semigroup morphism $f:\Delta ^{*}\rightarrow \Sigma ^{*}$ such that $f(p)=x$. Non-erasing means $f(a)\neq \varepsilon ,\forall a\in \Delta$.

A pattern $p$ is unavoidable on a finite alphabet $\Sigma$ if there exists $n\in \mathrm {N}$, word $x$ matches $p$ for any $x\in \Sigma ^{*},|x|\geq n$. Otherwise, $p$ is avoidable on $\Sigma$, which implies there exist infinitely many words over alphabet $\Sigma$ that avoid $p$. This is equivalent to saying that $p$ is avoidable on $\Sigma$ if there exists an infinite word $w\in \Sigma ^{\omega }$ that avoids $p$.

A pattern $p$ is an unavoidable pattern(blocking term) if $p$ is unavoidable on any finite alphabet.

Zimin words

Main article: Sesquipowers

Given alphabet $\Delta =\{x_{1},x_{2},...\}$, Zimin words(patterns) are defined recursively $Z_{n+1}=Z_{n}x_{n+1}Z_{n}$ for $n\in \mathrm {Z} ^{+}$ and base case $Z_{1}=x_{1}$.

A word $w$ is an unavoidable pattern if and only if it's a factor of a Zimin word.

It is unavoidable that any string, containing two unique characters, that is five or more characters long will contain a pattern of the form ABA (the second Zimin word). Using three unique characters any string containing 29 or more characters will contain a pattern of the form ABACABA

Pattern reduction

Given a pattern $p$ over some alphabet $\Delta$, we say $x\in \Delta$ is free for $p$ if there exist subsets $A,B$ of $\Delta$ such that the following hold:

1. $uv$ is a factor of $p$ and $u\in A$ ↔  $uv$ is a factor of $p$ and $v\in B$
2. $x\in A\backslash B\cup B\backslash A$

e.g. let $p=abcbab$, then $b$ is free for $p$ since there exist $A=ac,B=b$ satisfied conditions above.

A pattern $p\in \Delta ^{*}$ can reduce to pattern $q$ if there exists a character $x\in \Delta$ such that $x$ is free for $p$, and $q$ can be obtained by removing all occurrence of $x$ from $p$. Denote as $p{\stackrel {x}{\rightarrow }}q$.

e.g. let $p=abcbab$, then $p$ can reduce to $q=aca$ since $b$ is free for $p$.

Given patterns $p,q,r$, if $p$ can reduce to $q$ and $q$ can reduce to $r$, then $p$ can reduce to $r$. Denote as $p{\stackrel {*}{\rightarrow }}r$.

A pattern $p$ is unavoidable if and only if $p$ can reduce to the empty word, hence $p{\stackrel {*}{\rightarrow }}\varepsilon$.

Avoidability index

A pattern $p$ is $k$-avoidable if $p$ is avoidable on an alphabet $\Sigma$ of size $k$. Otherwise, $p$ is $k$-unavoidable, which means $p$ is unavoidable on every alphabet of size $k$.

if pattern $p$ is $k$-avoidable, then $p$ is $g$-avoidable for all $g\geq k$.

The avoidability index of a pattern $p$ is the smallest $k$ such that $p$ is $k$-avoidable, $\infty$ if $p$ is unavoidable.

• Many patterns are 2-avoidable.
• xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy, as well as many doubled words, are 3-avoidable, though this list is not complete.
• abwbaxbcyaczca is 4-avoidable, as well as other locked words. (Baker, McNulty, Taylor 1989)
• abvbawbcxacycdazdcd is 5-avoidable. (Clark 2004)
• no words with index greater than 5 have been found.

Examples

• The Thue–Morse sequence is cube-free and overlap-free, hence it avoids the patterns $aaa$ and $ababa$.
• The patterns $a$ and $aba$ are unavoidable on any alphabet, since they are factors of the Zimin words.
• The power patterns $x^{n}$ for $n\geq 3$ are 2-avoidable.
• A square-free word is one avoiding the pattern $xx$. An example is the word over the alphabet $\{0,\pm 1\}$ obtained by taking the first difference of the Thue–Morse sequence. See also Square-free word.
• all binary patterns can divided into three categories:
  • $\varepsilon ,a,ab,aba$ are unavoidable.
  • $aa,aab,abb,aaba,aabb,abaa,abab,abba,aabaa,aabab,ababb$ are 3-avoidable
  • others are 2-avoidable

References

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
• Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
• Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.