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

k-avoidable / 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 π_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]

References

1. Lothaire, M. (2002). Algebraic Combinatorics on Words . Cambridge University Press. ISBN   9780521812207.
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. S2CID   7928450.
4. Zimin, A. I. (1984). "Blocking Sets of Terms". Mathematics of the USSR-Sbornik. 47 (2): 353–364. Bibcode:1984SbMat..47..353Z. 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. doi: 10.2140/pjm.1979.85.261 . 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.

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