Unavoidable pattern

In mathematics and theoretical computer science, a pattern is an unavoidable pattern if it's unavoidable on any finite alphabet.

Definitions

Pattern

Like a word, a pattern (also referred to as term) is a sequence of characters over some alphabet.

The minimum multiplicity of pattern $p$ is $m(p)=min(count_{p}(x):x\in p)$ where $count_{p}(x)$ is the number of occurrence of character $x$ in pattern $p$. In other words, it is the number of occurrences in $p$ of the least frequently occurring character in $p$.

Instance

Given finite alphabets $\Sigma$ and $\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$, where $\Sigma ^{*}$ denotes the Kleene star of $\Sigma$. Non-erasing means that $f(a)\neq \varepsilon$ for all $a\in \Delta$, where $\varepsilon$ denotes the empty string.

Avoid / Match

A word $w$ is said to match, or encounter, a pattern $p$ if a substring of $w$ is an instance of $p$. Otherwise, $w$ is said to avoid $p$, or to be $p$-free. This definition can be generalized to the case of an infinite $w$, based on a generalized definition of "substring".

Avoidability / Unavoidability on a specific alphabet

A pattern $p$ is unavoidable on a finite alphabet $\Sigma$ if each sufficiently long word $x\in \Sigma ^{*}$ must match $p$; formally: if $\exists n\in \mathrm {N} .\ \forall x\in \Sigma ^{*}.\ (|x|\geq n\implies p{\text{ matches }}x)$. Otherwise, $p$ is avoidable on $\Sigma$, which implies there exist infinitely many words over alphabet $\Sigma$ that avoid $p$.

By Kőnig's lemma, pattern $p$ is avoidable on $\Sigma$ if, and only if, there exists an infinite word $w\in \Sigma ^{\omega }$ that avoids $p$.

Avoidable / Unavoidable pattern

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

If a pattern is said to be unavoidable and not limited to a specific alphabet, then it's unavoidable for any finite alphabet by default. Conversely, if a pattern is said to be avoidable and not limited to a specific alphabet, then it's avoidable on some finite alphabet by default.

$k$-avoidable / $k$-unavoidable

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$.

Given a finite set of avoidable patterns $S=\{p_{1},p_{2},...,p_{i}\}$, there exist an infinte word $w\in \Sigma ^{\omega }$ such that $w$ avoids all patterns of $S$. Let $\mu (S)$ denote the size of minimal alphabet $\Sigma ^{'}$such that $\exists w^{'}\in {\Sigma ^{'}}^{\omega }$ avoids all patterns of $S$.

Avoidability index

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

Properties

• Let pattern $q$ be an instance of avoidable pattern $p$, then $q$ is also avoidable.
• Let avoidable pattern $p$ be a factor of pattern $q$, then $q$ is also avoidable.
• A pattern $q$ is unavoidable if and only if $q$ is a factor of some unavoidable pattern $p$.
• Given an unavoidable pattern $p$ and a character $a$ not in $p$, then $pap$ is unavoidable.
• Given an unavoidable pattern $p$, then the reflection $p^{R}$ is unavoidable.
• Given an unavoidable pattern $p$, there exist a character $a$ such that $a$ occurs excatly once in $p$.
• Given a pattern $p$, let $n\in \mathrm {N}$ represents the number of distinct characters of $p$. if $|p|\geq 2^{n}$, then $p$ is avoidable.

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}$.

Unavoidability

All Zimin words are unavoidable.

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 |)$ represents 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}$

$Z_{n}$ is the longest unavoidable patterns constructed by alphabet $\Delta =\{x_{1},x_{2},...,x_{n}\}$ since $|Z_{n}|=2^{n}-1$

Pattern reduction

Free letter

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.

Reduce

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$.

Transitivity

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$.

Unavoidability

A pattern $p$ is unavoidable if and only if $p$ can reduce to a word of length one, hence $p{\stackrel {*}{\rightarrow }}w$ where $|w|=1$.

Graph pattern avoidance

Avoid / Match on a specific graph

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

Similarly, a vertex coloring $c:V\rightarrow \Delta$ matches pattern $p$ if there exists a simple path $P=[c_{1},c_{2},...,c_{r}]$ in $G$ such that the sequence $c(P)$ matches $p$.

Pattern chromatic number

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

Let $\pi _{p}(n)=max\{\pi _{p}(G):G\in G_{n}\}$ where $G_{n}$ is the set of all simple graphs with a maximum degree no more than $n$.

Similarly, $\pi _{p}^{'}(G)$ and $\pi _{p}^{'}(n)$ are defined on edge coloring.

Avoidability / Unavoidability on graphs

A pattern $p$ is avoidable on graphs if $\pi _{p}(n)$ is bounded by $c_{p}$, where $c_{p}$ only depend on $p$.

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

Probabilistic bound on $\pi _{p}(n)$

There exist an absolute constant $c$, such that $\pi _{p}(n)\leq cn^{\frac {m(p)}{m(p)-1}}\leq cn^{2}$ for all pattern $p$ with $m(p)\geq 2$.

Given a pattern $p$, let $n$ represents the number of distinct characters of $p$. if $|p|\geq 2^{n}$, then $p$ is avoidable on graphs.

Explicit colorings

Given a pattern $p$ such that $count_{p}(x)$ is even for all $x\in p$, then $\pi _{p}^{'}(K_{2}^{k})\leq 2^{k}-1$ for all $k\geq 1$ where $K_{n}$ is the complete graph of $n$ vertices.

Given a pattern $p$ such that $m(p)\geq 2$, and an arbitary tree $T$. Let $S$ be the set of all avoidable subpatterns and their reflections of $p$, then $\pi _{p}(T)\leq 3\mu (S)$.

Given a pattern $p$ such that $m(p)\geq 2$, and a tree $T$ with degree $n\geq 2$. Let $S$ be the set of all avoidable subpatterns and their reflections of $p$, then $\pi _{p}^{'}(T)\leq 2(n-1)\mu (S)$.

Examples

• The Thue–Morse sequence is cube-free and overlap-free, hence it avoids the patterns $aaa$ and $ababa$.
• A square-free word is one avoiding the pattern $xx$. The word over the alphabet $\{0,\pm 1\}$ obtained by taking the first difference of the Thue–Morse sequence is an example of infinite square-free words.
• 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.
• 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.
• $abwbaxbcyaczca$ has avoidability index of 4, as well as other locked words.
• $abvacwbaxbcycdazdcd$ has avoidability index of 5.
• The repetitive threshold $RT(n)$ is the infimum of exponent $k$ such that $x^{k}$ is avoidable on the alphabet of size $n$. See also Dejean's theorem.

Open problems

• Is there an avoidable pattern $p$ such that the avoidability index of $p$ is 6?
• Given an arbitary pattern $p$, is there an algorithm to determine the avoidability index of $p$?
• Are all avoidable patterns also avoidable on graphs?

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.