unavoidable pattern

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

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

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

A word $w$ is said to match, or encounter, a pattern $p$ if a factor (also called subword or 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".

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

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

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

A pattern $p$ is an unavoidable pattern (also called blocking term) if $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.

A pattern $p$ is $k$-avoidable if $p$ is avoidable on an alphabet $\backslash Sigma$ of size $k$. Otherwise, $p$ is $k$-unavoidable, which means $p$ is unavoidable on every alphabet of size $k$.{{Cite book|url=https://books.google.com/books?id=3w9eR3u8GN4C&q=Combinatorics+on+words.+Christoffel+words+and+repetitions+in+words+2009|title=Combinatorics on Words: Christoffel Words and Repetitions in Words|publisher=American Mathematical Soc.|isbn=978-0-8218-7325-0|pages=127|language=en}}

If pattern $p$ is $k$-avoidable, then $p$ is $g$-avoidable for all $g\backslash geq\; k$.

Given a finite set of avoidable patterns $S=\backslash \{p\_1,p\_2,...,p\_i\; \backslash \}$, there exists an infinite word $w\backslash in\backslash Sigma^\backslash omega$ such that $w$ avoids all patterns of $S$. Let $\backslash mu(S)$ denote the size of the minimal alphabet $\backslash Sigma\text{'}$such that $\backslash exist\; w\text{'}\; \backslash in\; \{\backslash Sigma\text{'}\}^\backslash omega$ avoiding all patterns of $S$.

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

• A pattern $q$ is avoidable if $q$ is an instance of an avoidable pattern $p$.{{Cite journal|last=Schmidt|first=Ursula|date=1987-08-01|title=Long unavoidable patterns|journal=Acta Informatica|language=en|volume=24|issue=4|pages=433–445|doi=10.1007/BF00292112|s2cid=7928450|issn=1432-0525}}
• 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 symbol $a$ not in $p$, then $pap$ is unavoidable.
• Given an unavoidable pattern $p$, then the reversal $p^R$ is unavoidable.
• Given an unavoidable pattern $p$, there exists a symbol $a$ such that $a$ occurs exactly once in $p$.
• Let $n\backslash in\backslash Nu$ represent the number of distinct symbols of pattern $p$. If $|p|\backslash geq2^n$, then $p$ is avoidable.

{{main|Sesquipower}}

Given alphabet $\backslash Delta=\backslash \{x\_1,x\_2,...\backslash \}$, Zimin words (patterns) are defined recursively $Z\_\{n+1\}=Z\_nx\_\{n+1\}Z\_n$ for $n\backslash in\backslash Zeta^+$ and $Z\_1=x\_1$.

All Zimin words are unavoidable.

A word $w$ is unavoidable if and only if it is a factor of a Zimin word.{{Cite journal|last=Zimin|first=A. I.|title=Blocking Sets of Terms|date=1984|journal=Mathematics of the USSR-Sbornik|language=en|volume=47|issue=2|pages=353–364|doi=10.1070/SM1984v047n02ABEH002647|bibcode=1984SbMat..47..353Z|issn=0025-5734}}

Given a finite alphabet $\backslash Sigma$, let $f(n,|\backslash Sigma|)$ represent the smallest $m\backslash in\backslash Zeta^+$ such that $w$ matches $Z\_n$ for all $w\backslash in\; \backslash Sigma^m$. We have following properties:{{cite arXiv | eprint=1409.3080 | last1=Cooper | first1=Joshua | last2=Rorabaugh | first2=Danny | title=Bounds on Zimin Word Avoidance | date=2014 | class=math.CO }}

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

$Z\_n$ is the longest unavoidable pattern constructed by alphabet $\backslash Delta=\backslash \{x\_1,x\_2,...,x\_n\backslash \}$ since $|Z\_n|=2^n\; -1$.

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

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

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

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

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

A word $w$ is said to be locked if $w$ has no free letter; hence $w$ can not be reduced.{{Cite journal|last1=Baker|first1=Kirby A.|last2=McNulty|first2=George F.|last3=Taylor|first3=Walter|date=1989-12-18|title=Growth problems for avoidable words|journal=Theoretical Computer Science|language=en|volume=69|issue=3|pages=319–345|doi=10.1016/0304-3975(89)90071-6|issn=0304-3975|doi-access=free}}

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

A pattern $p$ is unavoidable if and only if $p$ reduces to a word of length one; hence $\backslash exist\; w$ such that $|w|=1$ and $p\backslash stackrel\{*\}\{\backslash rightarrow\}w$.{{Cite journal|last1=Bean|first1=Dwight R.|last2=Ehrenfeucht|first2=Andrzej|last3=McNulty|first3=George F.|date=1979|title=Avoidable patterns in strings of symbols.|url=https://projecteuclid.org/euclid.pjm/1102783913|journal=Pacific Journal of Mathematics|language=en|volume=85|issue=2|pages=261–294|doi=10.2140/pjm.1979.85.261|issn=0030-8730|doi-access=free}}

Given a simple graph $G=(V,E)$, a edge coloring $c:E\backslash rightarrow\; \backslash 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 be $p$-free.

Similarly, a vertex coloring $c:V\backslash rightarrow\; \backslash 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$.

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

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

Similarly, $\backslash pi\_p\text{'}(G)$ and $\backslash pi\_p\text{'}(n)$ are defined for edge colorings.

A pattern $p$ is avoidable on graphs if $\backslash pi\_p(n)$ is bounded by $c\_p$, where $c\_p$ only depends 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 $\backslash pi\_p(P\_n)\; \backslash leq\; c\_p$ for all $n\; \backslash in\backslash Zeta\; ^+$, where $P\_n$ is a graph of $n$ vertices concatenated.

There exists an absolute constant $c$, such that $\backslash pi\_p(n)\backslash leq\; cn^\{\backslash frac\{m(p)\}\{m(p)-1\}\}\backslash leq\; cn^2$ for all patterns $p$ with $m(p)\backslash geq2$.

Given a pattern $p$, let $n$ represent the number of distinct symbols of $p$. If $|p|\backslash geq2^n$, then $p$ is avoidable on graphs.

Given a pattern $p$ such that $count\_p(x)$ is even for all $x\backslash in\; p$, then $\backslash pi\_p\text{'}(K\_2^k)\backslash leq2^k-1$ for all $k\backslash geq\; 1$, where $K\_n$ is the complete graph of $n$ vertices.

Given a pattern $p$ such that $m(p)\backslash geq2$, and an arbitrary tree $T$, let $S$ be the set of all avoidable subpatterns and their reflections of $p$. Then $\backslash pi\_p(T)\backslash leq\; 3\backslash mu(S)$.

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

• The Thue–Morse sequence is cube-free and overlap-free; hence it avoids the patterns $xxx$ and $xyxyx$.
• A square-free word is one avoiding the pattern $xx$. The word over the alphabet $\backslash \{0,\backslash pm1\backslash \}$ obtained by taking the first difference of the Thue–Morse sequence is an example of an infinite square-free word.{{Cite book|url=https://books.google.com/books?id=3w9eR3u8GN4C&q=Combinatorics+on+words.+Christoffel+words+and+repetitions+in+words+2009|title=Combinatorics on Words: Christoffel Words and Repetitions in Words|publisher=American Mathematical Soc.|isbn=978-0-8218-7325-0|pages=97|language=en}}{{Cite book|last=Fogg|first=N. Pytheas|url=https://books.google.com/books?id=qBIsuwEACAAJ&q=Substitutions+in+dynamics,+arithmetics+and+combinatorics.|title=Substitutions in Dynamics, Arithmetics and Combinatorics|date=2002-09-23|publisher=Springer Science & Business Media|isbn=978-3-540-44141-0|pages=104|language=en}}
• The patterns $x$ and $xyx$ are unavoidable on any alphabet, since they are factors of the Zimin words.{{Cite book|last1=Allouche|first1=Jean-Paul|url=https://books.google.com/books?id=2ZsSUStt96sC&dq=Automatic+Sequences%3A+Theory%2C+Applications%2C+Generalizations&pg=PR13|title=Automatic Sequences: Theory, Applications, Generalizations|last2=Shallit|first2=Jeffrey|last3=Shallit|first3=Professor Jeffrey|date=2003-07-21|publisher=Cambridge University Press|isbn=978-0-521-82332-6|pages=24|language=en}}
• The power patterns $x^n$ for $n\backslash geq\; 3$ are 2-avoidable.
• All binary patterns can be divided into three categories:{{cite book|last1=Lothaire|first1=M.|url=https://archive.org/details/algebraiccombina0000loth|url-access=registration|title=Algebraic Combinatorics on Words|publisher=Cambridge University Press|year=2002|isbn=9780521812207}}
• $\backslash varepsilon,x,xyx$ are unavoidable.
• $xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy$ 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.{{Cite journal|last=Clark|first=Ronald J.|date=2006-04-01|title=The existence of a pattern which is 5-avoidable but 4-unavoidable|journal=International Journal of Algebra and Computation|volume=16|issue=2|pages=351–367|doi=10.1142/S0218196706002950|issn=0218-1967}}
• The repetitive threshold $RT(n)$ is the infimum of exponents $k$ such that $x^k$ is avoidable on an alphabet of size $n$. Also see Dejean's theorem.

• Is there an avoidable pattern $p$ such that the avoidability index of $p$ is 6?
• Given an arbitrarily pattern $p$, is there an algorithm to determine the avoidability index of $p$?

{{reflist}}

• {{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = Cambridge University Press | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}
• {{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=American Mathematical Society | year=2009 | isbn=978-0-8218-4480-9 | zbl=1161.68043 }}
• {{cite book | last=Lothaire | first=M. | author-link=M. Lothaire | title=Algebraic combinatorics on words | others=With preface by Jean Berstel and Dominique Perrin | edition=Reprint of the 2002 hardback | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=Cambridge University Press | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}
• {{cite book | last=Pytheas Fogg | first=N. | editor1-first=Valérie | editor1-last = Berthé |editor1-link = Valérie Berthé| editor2-last = Ferenczi | editor2-first= Sébastien | editor3-last= Mauduit | editor3-first= Christian | editor4-last= Siegel | editor4-first= A. | title=Substitutions in dynamics, arithmetics and combinatorics | series=Lecture Notes in Mathematics | volume=1794 | location=Berlin | publisher=Springer-Verlag | year=2002 | isbn=3-540-44141-7 | zbl=1014.11015 }}

Category:Semigroup theory

Category:Formal languages

Category:Combinatorics on words