Unavoidable 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}$.

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.

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

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]

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

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.

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

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]

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

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.

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

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

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

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]

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

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.

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.

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.

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]