Unavoidable pattern explained

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 ( count _{p} (x):x \in p) where 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 .

Instance

Given finite alphabets

\Sigma and \Delta , a word x\in\Sigma ^{*} is an instance of the pattern p\in\Delta ^{*} if there exists a non-erasing semigroup morphism f:\Delta ^{* → \Sigma} ^{*} such that f(p) = x , where \Sigma ^{*} denotes the Kleene star of \Sigma . Non-erasing means that f(a) ≠ \varepsilon for all a\in\Delta , where \varepsilon 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 \Sigma if each sufficiently long word x\in\Sigma ^{*} must match p ; formally: if \exists n\in \Nu. \forall x\in\Sigma ^{*.} (|x|\geq n \implies x matches p) . Otherwise, p is avoidable on \Sigma , which implies there exist infinitely many words over the alphabet \Sigma that avoid p .

By Kőnig's lemma, pattern

p is avoidable on \Sigma if and only if there exists an infinite word w\in \Sigma ^{\omega} that avoids p .

Maximal p-free word

Given a pattern

p and an alphabet \Sigma . A p -free word w\in\Sigma ^{*} is a maximal p -free word over \Sigma if aw and wa match p \forall a\in\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 \Sigma of size k . Otherwise, p is k -unavoidable, which means p is unavoidable on every alphabet of size k .^[1]

If pattern

p is k -avoidable, then p is g -avoidable for all g\geq k .

Given a finite set of avoidable patterns

S = \{p _{1,p} _{2,...,p} _{i} \} , there exists an infinite word w\in\Sigma ^{\omega} such that w avoids all patterns of S . Let \mu(S) denote the size of the minimal alphabet \Sigma' such that \exist w' \in {\Sigma'} ^{\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 inf in if p is unavoidable.

Properties

• A pattern

q is avoidable if q is an instance of an avoidable pattern p .^[2]

• 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\Nu represent the number of distinct symbols of pattern p . If |p|\geq 2 ^{n} , then p is avoidable.

Zimin words

See main article: Sesquipower. Given alphabet

\Delta = \{x _{1,x} _{2,...\}} , Zimin words (patterns) are defined recursively Z _{n+1} = Z _{nx} _{n+1} Z _{n} for n\in\Zeta ^{+} 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.^[3]

Given a finite alphabet

\Sigma , let f(n,|\Sigma|) represent the smallest m\in\Zeta ^{+} such that w matches Z _{n} for all w\in \Sigma ^{m} . We have following properties:^[4] f( 1 ,q) =1 f( 2 ,q) =2 q +1 f( 3 , 2 ) =29 f(n,q)\leq{ ^{n-1} q} = \underbrace{q ^{q ^{⋅ ^{⋅ ^{q}}}} }_ Z _{n} is the longest unavoidable pattern constructed by alphabet \Delta = \{x _{1,x} _{2,...,x} _{n\}} since |Z ^{n} _{n| =2} -1 .

Pattern reduction

Free letter

Given a pattern

p over some alphabet \Delta , we say x\in\Delta is free for p if there exist subsets A,B of \Delta such that the following hold:uv is a factor of p and u\in A ↔ uv is a factor of p and v\in B

x\in A\backslash B\cup B\backslash 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 \Delta ^{*} reduces to pattern q if there exists a symbol x\in \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}{ → }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.^[5]

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{*}{ → }r .

Unavoidability

A pattern

p is unavoidable if and only if p reduces to a word of length one; hence \exist w such that |w| =1 and p\stackrel{*}{ → }w .^[6]

Graph pattern avoidance^[7]

Avoidance / Matching on a specific graph

Given a simple graph

G = (V,E) , a edge coloring c:E → \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 → \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'(G)} and \pi _{p'(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)} \leq c _{p} for all n \in\Zeta ^{+} , where P _{n} is a graph of n vertices concatenated.

Probabilistic bound on

\pi _{p(n)}

There exists an absolute constant

c , such that \pi _{p(n)\leq} cn ^{(m(p))/(m(p) -1)} \leq cn ^{2} for all patterns p with m(p)\geq 2 .

Given a pattern

p , let n represent the number of distinct symbols of p . If |p|\geq 2 ^{n} , then p is avoidable on graphs.

Explicit colorings

Given a pattern

p such that count _{p(x)} is even for all x\in p , then \pi _{p'(K} ^{k)\leq 2} ^{2} ^{k-1} for all k\geq 1 , where K _{n} is the complete graph of n vertices.

Given a pattern

p such that m(p)\geq 2 , and an arbitrary tree T , let S be the set of all avoidable subpatterns and their reflections of p . Then \pi _{p(T)\leq} 3 \mu(S) .

Given a pattern

p such that m(p)\geq 2 , and a tree T with degree n\geq 2 . Let S be the set of all avoidable subpatterns and their reflections of p , then \pi _{p'(T)\leq} 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.^{[8] [9]}

• The patterns

x and xyx are unavoidable on any alphabet, since they are factors of the Zimin words.^[10]

• The power patterns

x ^{n} for n\geq 3 are 2-avoidable.

• All binary patterns can be divided into three categories:^[11]

\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.^[12]

• 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

• Book: Allouche . Jean-Paul . Shallit . Jeffrey . Jeffrey Shallit . 978-0-521-82332-6 . . Automatic Sequences: Theory, Applications, Generalizations . 2003 . 1086.11015 .
• Book: Berstel . Jean . Lauve . Aaron . Reutenauer . Christophe . Saliola . Franco V. . Combinatorics on words. Christoffel words and repetitions in words . CRM Monograph Series . 27 . Providence, RI . . 2009 . 978-0-8218-4480-9 . 1161.68043 .
• Book: Lothaire, M. . M. Lothaire . Algebraic combinatorics on words . With preface by Jean Berstel and Dominique Perrin . Reprint of the 2002 hardback . Encyclopedia of Mathematics and Its Applications . 90. . 2011 . 978-0-521-18071-9 . 1221.68183 .
• Book: Pytheas Fogg, N. . Valérie . Berthé . Valérie Berthé. Ferenczi . Sébastien . Mauduit . Christian . Siegel . A. . Substitutions in dynamics, arithmetics and combinatorics . Lecture Notes in Mathematics . 1794 . Berlin . . 2002 . 3-540-44141-7 . 1014.11015 .

Notes and References

1. Book: Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Soc.. 978-0-8218-7325-0. 127. en.
2. Schmidt. Ursula. 1987-08-01. Long unavoidable patterns. Acta Informatica. en. 24. 4. 433–445. 10.1007/BF00292112. 7928450. 1432-0525.
3. Zimin. A. I.. Blocking Sets of Terms. 1984. Mathematics of the USSR-Sbornik. en. 47. 2. 353–364. 10.1070/SM1984v047n02ABEH002647. 1984SbMat..47..353Z. 0025-5734.
4. Book: Joshua. Cooper. Bounds on Zimin Word Avoidance. Rorabaugh. Danny. 2013. 1409.3080. 2014arXiv1409.3080C.
5. Baker. Kirby A.. McNulty. George F.. Taylor. Walter. 1989-12-18. Growth problems for avoidable words. Theoretical Computer Science. en. 69. 3. 319–345. 10.1016/0304-3975(89)90071-6. 0304-3975. free.
6. Bean. Dwight R.. Ehrenfeucht. Andrzej. McNulty. George F.. 1979. Avoidable patterns in strings of symbols.. Pacific Journal of Mathematics. en. 85. 2. 261–294. 10.2140/pjm.1979.85.261. 0030-8730. free.
7. Grytczuk. Jarosław. 2007-05-28. Pattern avoidance on graphs. Discrete Mathematics. The Fourth Caracow Conference on Graph Theory. en. 307. 11. 1341–1346. 10.1016/j.disc.2005.11.071. 0012-365X. free.
8. Book: Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Soc.. 978-0-8218-7325-0. 97. en.
9. Book: Fogg, N. Pytheas. Substitutions in Dynamics, Arithmetics and Combinatorics. 2002-09-23. Springer Science & Business Media. 978-3-540-44141-0. 104. en.
10. Book: Allouche. Jean-Paul. Automatic Sequences: Theory, Applications, Generalizations. Shallit. Jeffrey. Shallit. Professor Jeffrey. 2003-07-21. Cambridge University Press. 978-0-521-82332-6. 24. en.
11. Book: Lothaire. M.. Algebraic Combinatorics on Words. registration. Cambridge University Press. 2002. 9780521812207.
12. Clark. Ronald J.. 2006-04-01. The existence of a pattern which is 5-avoidable but 4-unavoidable. International Journal of Algebra and Computation. 16. 2. 351–367. 10.1142/S0218196706002950. 0218-1967.