Unavoidable pattern

In mathematics and theoretical computer science, a pattern(term) is a sequence of characters over some alphabet $\Delta$.

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 word $w$ matches(encounters) pattern $p$ if there exists a factor of $w$, which is also an instance of $p$. Otherwise, $w$ avoids $p$. If $w$ avoids $p$, $w$ is also called $p$-free.

A pattern $p$ is unavoidable on a finite alphabet $\Sigma$ if there exists $n\in \mathrm {N}$, word $x$ matches $p$ for all $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.

When a pattern $p$ is said to be unavoidable and does not specify an alphabet, then $p$ is unavoidable for any finite alphabet. Conversely, a pattern $p$ is said to be avoidable if $p$ is avoidable on some finite alphabet.

Zimin words

Main article: Sesquipower

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 unavoidable if and only if it's a factor of a Zimin word.

Given a finite alphabet $\Sigma$, let $f(n,|\Sigma |)$ representing the smallest $m\in \mathrm {Z} ^{+}$ such that $w$ matches $Z_{n}$ for all $w\in \Sigma ^{m}$. We have following properties:

• $f(1,q)=1$
• $f(2,q)=2q+1$
• $f(3,2)=29$
• $f(n,q)\leq {^{n-1}q}=\underbrace {q^{q^{\cdot ^{\cdot ^{q}}}}} _{n-1}$

Given a pattern $p$, let $n$ representing the number of distinct characters of $p$. $p$ is avoidable if $|p|\geq 2^{n}$. Hence $Z_{n}$ is one of the longest unavoidable patterns constructed by alphabet $\Delta =\{x_{1},x_{2},...,x_{n}\}$.

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.

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

Graph pattern avoidance

Given a graph $G=(V,E)$, a coloring $c:E\rightarrow \Delta$ is said to match the pattern $p$ if there exists a simple path $P=[e_{1},e_{2},...,e_{r}]$ in $G$ such that the sequence of colors $c(P)=[c(e_{1}),c(e_{2}),...,c(e_{r})]$ matches $p$. Otherwise, $c$ is said to avoid $p$ or $p$-free.

The pattern chromatic number $\pi _{p}(G)$ is the minimal number of distinct colors needed for a $p$-free coloring $c$ over the graph $G$.

let $G_{n}$ representing all the graphs with maximum degree no more than $n$. let $\pi _{p}(n)=max\{\pi _{p}(G):G\in G_{n}\}$

A pattern $p$ is avoidable on graphs if $\pi _{p}(n)$ is bounded by a constant $c_{p}$.

An avoidable pattern $p$ on words can be expressed as a specific case of avoidance on graphs, hence $\pi _{p}(P_{n})\leq c_{p}$ for all $n\in \mathrm {Z} ^{+}$ where $P_{n}$ is a graph of $n$ vertexs concatenated.

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$ have avoidability index of 3.
  • others have avoidability index of 2.

Open problems

• Is there an avoidable pattern $p$ such that the avoidability index of $p$ is 6?

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.