Unavoidable pattern

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

Definitions

Pattern

Like a word, a pattern (also called term) is a sequence of symbols over some alphabet.

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

Instance

Given finite alphabets ${\displaystyle \Sigma }$ and ${\displaystyle \Delta }$, a word ${\displaystyle x\in \Sigma ^{*}}$ is an instance of the pattern ${\displaystyle p\in \Delta ^{*}}$ if there exists a non-erasing semigroup morphism ${\displaystyle f:\Delta ^{*}\rightarrow \Sigma ^{*}}$ such that ${\displaystyle f(p)=x}$, where ${\displaystyle \Sigma ^{*}}$ denotes the Kleene star of ${\displaystyle \Sigma }$. Non-erasing means that ${\displaystyle f(a)\neq \varepsilon }$ for all ${\displaystyle a\in \Delta }$, where ${\displaystyle \varepsilon }$ denotes the empty string.

Avoidance / Matching

A word ${\displaystyle w}$ is said to match, or encounter, a pattern ${\displaystyle p}$ if a factor (also called subword or substring) of ${\displaystyle w}$ is an instance of ${\displaystyle p}$. Otherwise, ${\displaystyle w}$ is said to avoid ${\displaystyle p}$, or to be ${\displaystyle p}$-free. This definition can be generalized to the case of an infinite ${\displaystyle w}$, based on a generalized definition of "substring".

Avoidability / Unavoidability on a specific alphabet

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

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

Maximal ${\displaystyle p}$-free word

Given a pattern ${\displaystyle p}$ and an alphabet ${\displaystyle \Sigma }$. A ${\displaystyle p}$-free word ${\displaystyle w\in \Sigma ^{*}}$ is a maximal ${\displaystyle p}$-free word over ${\displaystyle \Sigma }$ if ${\displaystyle aw}$ and ${\displaystyle wa}$ match ${\displaystyle p}$ ${\displaystyle \forall a\in \Sigma }$.

Avoidable / Unavoidable pattern

A pattern ${\displaystyle p}$ is an unavoidable pattern (also called blocking term) if ${\displaystyle p}$ is unavoidable on any finite alphabet.

If a pattern is unavoidable and not limited to a specific alphabet, then it is 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 is avoidable on some finite alphabet by default.

${\displaystyle k}$-avoidable / ${\displaystyle k}$-unavoidable

A pattern ${\displaystyle p}$ is ${\displaystyle k}$-avoidable if ${\displaystyle p}$ is avoidable on an alphabet ${\displaystyle \Sigma }$ of size ${\displaystyle k}$. Otherwise, ${\displaystyle p}$ is ${\displaystyle k}$-unavoidable, which means ${\displaystyle p}$ is unavoidable on every alphabet of size ${\displaystyle k}$.[2]

If pattern ${\displaystyle p}$ is ${\displaystyle k}$-avoidable, then ${\displaystyle p}$ is ${\displaystyle g}$-avoidable for all ${\displaystyle g\geq k}$.

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

Avoidability index

The avoidability index of a pattern ${\displaystyle p}$ is the smallest ${\displaystyle k}$ such that ${\displaystyle p}$ is ${\displaystyle k}$-avoidable, and ${\displaystyle \infty }$ if ${\displaystyle p}$ is unavoidable.[1]

Properties

• A pattern ${\displaystyle q}$ is avoidable if ${\displaystyle q}$ is an instance of an avoidable pattern ${\displaystyle p}$.[3]
• Let avoidable pattern ${\displaystyle p}$ be a factor of pattern ${\displaystyle q}$, then ${\displaystyle q}$ is also avoidable.[3]
• A pattern ${\displaystyle q}$ is unavoidable if and only if ${\displaystyle q}$ is a factor of some unavoidable pattern ${\displaystyle p}$.
• Given an unavoidable pattern ${\displaystyle p}$ and a symbol ${\displaystyle a}$ not in ${\displaystyle p}$, then ${\displaystyle pap}$ is unavoidable.[3]
• Given an unavoidable pattern ${\displaystyle p}$, then the reversal ${\displaystyle p^{R}}$ is unavoidable.
• Given an unavoidable pattern ${\displaystyle p}$, there exists a symbol ${\displaystyle a}$ such that ${\displaystyle a}$ occurs exactly once in ${\displaystyle p}$.[3]
• Let ${\displaystyle n\in \mathrm {N} }$ represent the number of distinct symbols of pattern ${\displaystyle p}$. If ${\displaystyle |p|\geq 2^{n}}$, then ${\displaystyle p}$ is avoidable.[3]

Zimin words

Main article: Sesquipower

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

Unavoidability

All Zimin words are unavoidable.[4]

A word ${\displaystyle w}$ is unavoidable if and only if it is a factor of a Zimin word.[4]

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

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

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

Pattern reduction

Free letter

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

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

For example, let ${\displaystyle p=abcbab}$, then ${\displaystyle b}$ is free for ${\displaystyle p}$ since there exist ${\displaystyle A=ac,B=b}$ satisfying the conditions above.

Reduce

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

For example, let ${\displaystyle p=abcbab}$, then ${\displaystyle p}$ can reduce to ${\displaystyle q=aca}$ since ${\displaystyle b}$ is free for ${\displaystyle p}$.

Locked

A word ${\displaystyle w}$ is said to be locked if ${\displaystyle w}$ has no free letter; hence ${\displaystyle w}$ can not be reduced.[6]

Transitivity

Given patterns ${\displaystyle p,q,r}$, if ${\displaystyle p}$ reduces to ${\displaystyle q}$ and ${\displaystyle q}$ reduces to ${\displaystyle r}$, then ${\displaystyle p}$ reduces to ${\displaystyle r}$. Denote this relation by ${\displaystyle p{\stackrel {*}{\rightarrow }}r}$.

Unavoidability

A pattern ${\displaystyle p}$ is unavoidable if and only if ${\displaystyle p}$ reduces to a word of length one; hence ${\displaystyle \exists w}$ such that ${\displaystyle |w|=1}$ and ${\displaystyle p{\stackrel {*}{\rightarrow }}w}$.[7][4]

Graph pattern avoidance[8]

Avoidance / Matching on a specific graph

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

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

Pattern chromatic number

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

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

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

Avoidability / Unavoidability on graphs

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

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

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

There exists an absolute constant ${\displaystyle c}$, such that ${\displaystyle \pi _{p}(n)\leq cn^{\frac {m(p)}{m(p)-1}}\leq cn^{2}}$ for all patterns ${\displaystyle p}$ with ${\displaystyle m(p)\geq 2}$.[8]

Given a pattern ${\displaystyle p}$, let ${\displaystyle n}$ represent the number of distinct symbols of ${\displaystyle p}$. If ${\displaystyle |p|\geq 2^{n}}$, then ${\displaystyle p}$ is avoidable on graphs.

Explicit colorings

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

Given a pattern ${\displaystyle p}$ such that ${\displaystyle m(p)\geq 2}$, and an arbitrary tree ${\displaystyle T}$, let ${\displaystyle S}$ be the set of all avoidable subpatterns and their reflections of ${\displaystyle p}$. Then ${\displaystyle \pi _{p}(T)\leq 3\mu (S)}$.[8]

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

Examples

• The Thue–Morse sequence is cube-free and overlap-free; hence it avoids the patterns ${\displaystyle xxx}$ and ${\displaystyle xyxyx}$.[2]
• A square-free word is one avoiding the pattern ${\displaystyle xx}$. The word over the alphabet ${\displaystyle \{0,\pm 1\}}$ obtained by taking the first difference of the Thue–Morse sequence is an example of an infinite square-free word.[9][10]
• The patterns ${\displaystyle x}$ and ${\displaystyle xyx}$ are unavoidable on any alphabet, since they are factors of the Zimin words.[11][1]
• The power patterns ${\displaystyle x^{n}}$ for ${\displaystyle n\geq 3}$ are 2-avoidable.[1]
• All binary patterns can be divided into three categories:[1]
  • ${\displaystyle \varepsilon ,x,xyx}$ are unavoidable.
  • ${\displaystyle xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy}$ have avoidability index of 3.
  • others have avoidability index of 2.
• ${\displaystyle abwbaxbcyaczca}$ has avoidability index of 4, as well as other locked words.[6]
• ${\displaystyle abvacwbaxbcycdazdcd}$ has avoidability index of 5.[12]
• The repetitive threshold ${\displaystyle RT(n)}$ is the infimum of exponents ${\displaystyle k}$ such that ${\displaystyle x^{k}}$ is avoidable on an alphabet of size ${\displaystyle n}$. Also see Dejean's theorem.

Open problems

• Is there an avoidable pattern ${\displaystyle p}$ such that the avoidability index of ${\displaystyle p}$ is 6?
• Given an arbitrarily pattern ${\displaystyle p}$, is there an algorithm to determine the avoidability index of ${\displaystyle p}$?[1]
• Are all avoidable patterns also avoidable on graphs?[13]

References

1. Lothaire, M. (2002). Algebraic Combinatorics on Words. Cambridge University Press.
2. Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Soc. p. 127. ISBN 978-0-8218-7325-0.
3. Schmidt, Ursula (1987-08-01). "Long unavoidable patterns". Acta Informatica. 24 (4): 433–445. doi:10.1007/BF00292112. ISSN 1432-0525.
4. Zimin, A. I. (1984). "Blocking Sets of Terms". Mathematics of the USSR-Sbornik. 47 (2): 353–364. doi:10.1070/SM1984v047n02ABEH002647. ISSN 0025-5734.
5. Joshua, Cooper; Rorabaugh, Danny (2013). Bounds on Zimin Word Avoidance. arXiv:1409.3080. Bibcode:2014arXiv1409.3080C.
6. Baker, Kirby A.; McNulty, George F.; Taylor, Walter (1989-12-18). "Growth problems for avoidable words". Theoretical Computer Science. 69 (3): 319–345. doi:10.1016/0304-3975(89)90071-6. ISSN 0304-3975.
7. Bean, Dwight R.; Ehrenfeucht, Andrzej; McNulty, George F. (1979). "Avoidable patterns in strings of symbols". Pacific Journal of Mathematics. 85 (2): 261–294. ISSN 0030-8730.
8. Grytczuk, Jarosław (2007-05-28). "Pattern avoidance on graphs". Discrete Mathematics. The Fourth Caracow Conference on Graph Theory. 307 (11): 1341–1346. doi:10.1016/j.disc.2005.11.071. ISSN 0012-365X.
9. Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Soc. p. 97. ISBN 978-0-8218-7325-0.
10. Fogg, N. Pytheas (2002-09-23). Substitutions in Dynamics, Arithmetics and Combinatorics. Springer Science & Business Media. p. 104. ISBN 978-3-540-44141-0.
11. Allouche, Jean-Paul; Shallit, Jeffrey; Shallit, Professor Jeffrey (2003-07-21). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. p. 24. ISBN 978-0-521-82332-6.
12. Clark, Ronald J. (2006-04-01). "The existence of a pattern which is 5-avoidable but 4-unavoidable". International Journal of Algebra and Computation. 16 (2): 351–367. doi:10.1142/S0218196706002950. ISSN 0218-1967.
13. Grytczuk, Jarosław (2007-05-28). "Pattern avoidance on graphs". Discrete Mathematics. The Fourth Caracow Conference on Graph Theory. 307 (11): 1341–1346. doi:10.1016/j.disc.2005.11.071. ISSN 0012-365X.

• 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. 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. 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. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.