# Unavoidable pattern

(Redirected from Avoidable pattern)

2010 Mathematics Subject Classification: Primary: 68R15 [MSN][ZBL]

A pattern of symbols that must occur in any sufficiently long word over a given alphabet. An avoidable pattern is one which for which there are infinitely many words no part of which match the pattern.

Let $A$ be an alphabet of letters and $E$ a disjoint alphabet of pattern symbols or "variables". Elements of the free semigroup of non-empty words $E^+$ are patterns. For a pattern $p$, the pattern language is that subset of the free monoid $A^*$ containing all words $h(p)$ where $h$ is a non-erasing semigroup morphism from $E^+$ to $A^*$. A word $w \in A^*$ matches or meets $p$ if it contains some word in the pattern language as a factor, otherwise $w$ avoids $p$.

A pattern $p$ is avoidable on $A$ if there are infinitely many words in $A^*$ that avoid $p$; it is unavoidable on A if all sufficiently long words in $A^*$ match $p$. We say that $p$ is $k$-unavoidable if it is unavoidable on every alphabet of size $k$ and correspondingly $k$-avoidable if it is avoidable on an alphabet of size $k$.

There is a word $W(k)$ over an alphabet of size $4k$ which avoids every avoidable pattern with fewer than $2k$ variables.

## Contents

#### Examples

• The Thue–Morse sequence avoids the patterns $xxx$ and $xyxyx$.
• The patterns $x$ and $xyx$ are unavoidable on any alphabet.
• The power pattern $xx$ is 3-avoidable; words avoiding this pattern are square-free.
• The power patterns $x^n$ for $n \ge 3$ are 2-avoidable: the Thue–Morse sequence is an example for $n=3$.
• Sesquipowers are unavoidable.

#### Avoidability index

The avoidability index of a pattern $p$ is the smallest $k$ such that $p$ is $k$-avoidable, or $\infty$ if $p$ is unavoidable. For binary patterns (two variables $x$ and $y$) we have:

• $1,x,xy,xyx$ are unavoidable;
• $xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy$ have avoidability index 3;
• all other patterns have avoidability index 2.

#### Square-free words

A square-free word is one avoiding the pattern $xx$. An example is the word over the alphabet $\{0,\pm1\}$ obtained by taking the first difference of the Thue–Morse sequence.