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]