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 $p$ is $m(p)=\min (\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}{\mathrm{t}}_{\mathrm{p}}(x):x\in p)$ where $\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}{\mathrm{t}}_{\mathrm{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$.

Instance

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

Avoidance / Matching

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

Avoidability / Unavoidability on a specific alphabet

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

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

Maximal p-free word

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

Avoidable / Unavoidable pattern

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.

k-avoidable / k-unavoidable

A pattern $p$ is $k$-avoidable if $p$ is avoidable on an alphabet $\mathrm{\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\ge k$.

Given a finite set of avoidable patterns $S=\{p_1,p_2,...,p_i\}$, there exists an infinite word $w\in {\mathrm{\Sigma }}^{\omega }$ such that $w$ avoids all patterns of $S$. Let $\mu (S)$ denote the size of the minimal alphabet ${\mathrm{\Sigma }}^{\prime }$such that $\mathrm{\exists }{w}^{\prime }\in {{\mathrm{\Sigma }}^{\prime }}^{\omega }$ avoiding all patterns of $S$.

Avoidability index

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

Properties

• A pattern $q$ is avoidable if $q$ is an instance of an avoidable pattern $p$.
• 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\in \mathrm{N}$ represent the number of distinct symbols of pattern $p$. If $|p|\ge 2^n$, then $p$ is avoidable.

Zimin words

Template:Main Given alphabet $\mathrm{\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 $Z_1=x_1$.

Unavoidability

All Zimin words are unavoidable.

A word $w$ is unavoidable if and only if it is a factor of a Zimin word.

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

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

$Z_n$ is the longest unavoidable pattern constructed by alphabet $\mathrm{\Delta }=\{x_1,x_2,...,x_n\}$ since $|Z_n|=2^n-1$.

Pattern reduction

Free letter

Given a pattern $p$ over some alphabet $\mathrm{\Delta }$, we say $x\in \mathrm{\Delta }$ is free for $p$ if there exist subsets $A,B$ of $\mathrm{\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\mathrm{\setminus }B\cup B\mathrm{\setminus }A$

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

Reduce

A pattern $p\in {\mathrm{\Delta }}^{*}$ reduces to pattern $q$ if there exists a symbol $x\in \mathrm{\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\stackrel{x}{\to }q$.

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

Locked

A word $w$ is said to be locked if $w$ has no free letter; hence $w$ can not be reduced.

Transitivity

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\stackrel{*}{\to }r$.

Unavoidability

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

Graph pattern avoidance

Avoidance / Matching on a specific graph

Given a simple graph $G=(V,E)$, a edge coloring $c:E\to \mathrm{\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\to \mathrm{\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}^{\prime }(G)$ and ${{\pi }_p}^{\prime }(n)$ are defined for edge colorings.

Avoidability / Unavoidability on graphs

A pattern $p$ is avoidable on graphs if ${\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 ${\pi }_p(P_n)\le c_p$ for all $n\in {\mathrm{Z}}^{+}$, where $P_n$ is a graph of $n$ vertices concatenated.

Probabilistic bound on Template:PiTemplate:Sub(n)

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

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

Explicit colorings

Given a pattern $p$ such that $coun{t}_p(x)$ is even for all $x\in p$, then ${{\pi }_p}^{\prime }(K_2^k)\le 2^k-1$ for all $k\ge 1$, where $K_n$ is the complete graph of $n$ vertices.

Given a pattern $p$ such that $m(p)\ge 2$, and an arbitrary tree $T$, let $S$ be the set of all avoidable subpatterns and their reflections of $p$. Then ${\pi }_p(T)\le 3\mu (S)$.

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

Examples

• 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 $\{0,\pm 1\}$ obtained by taking the first difference of the Thue–Morse sequence is an example of an infinite square-free word.
• The patterns $x$ and $xyx$ are unavoidable on any alphabet, since they are factors of the Zimin words.
• The power patterns $x^n$ for $n\ge 3$ are 2-avoidable.
• All binary patterns can be divided into three categories:
  • $\epsilon ,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.
• 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.

Open problems

• 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$?

References

• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book