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 is where is the number of occurrence of symbol in pattern . In other words, it is the number of occurrences in of the least frequently occurring symbol in .
Instance
Given finite alphabets and , a word is an instance of the pattern if there exists a non-erasing semigroup morphism such that , where denotes the Kleene star of . Non-erasing means that for all , where denotes the empty string.
Avoidance / Matching
A word is said to match, or encounter, a pattern if a factor (also called subword or substring) of is an instance of . Otherwise, is said to avoid , or to be -free. This definition can be generalized to the case of an infinite , based on a generalized definition of "substring".
Avoidability / Unavoidability on a specific alphabet
A pattern is unavoidable on a finite alphabet if each sufficiently long word must match ; formally: if . Otherwise, is avoidable on , which implies there exist infinitely many words over the alphabet that avoid .
By Kőnig's lemma, pattern is avoidable on if and only if there exists an infinite word that avoids .[1]
Maximal p-free word
Given a pattern and an alphabet . A -free word is a maximal -free word over if and match .
Avoidable / Unavoidable pattern
A pattern is an unavoidable pattern (also called blocking term) if 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 is -avoidable if is avoidable on an alphabet of size . Otherwise, is -unavoidable, which means is unavoidable on every alphabet of size .[2]
If pattern is -avoidable, then is -avoidable for all .
Given a finite set of avoidable patterns , there exists an infinite word such that avoids all patterns of .[1] Let denote the size of the minimal alphabet such that avoiding all patterns of .
Avoidability index
The avoidability index of a pattern is the smallest such that is -avoidable, and if is unavoidable.[1]
Properties
- A pattern is avoidable if is an instance of an avoidable pattern .[3]
- Let avoidable pattern be a factor of pattern , then is also avoidable.[3]
- A pattern is unavoidable if and only if is a factor of some unavoidable pattern .
- Given an unavoidable pattern and a symbol not in , then is unavoidable.[3]
- Given an unavoidable pattern , then the reversal is unavoidable.
- Given an unavoidable pattern , there exists a symbol such that occurs exactly once in .[3]
- Let represent the number of distinct symbols of pattern . If , then is avoidable.[3]
Zimin words
Given alphabet , Zimin words (patterns) are defined recursively for and .
Unavoidability
All Zimin words are unavoidable.[4]
A word is unavoidable if and only if it is a factor of a Zimin word.[4]
Given a finite alphabet , let represent the smallest such that matches for all . We have following properties:[5]
is the longest unavoidable pattern constructed by alphabet since .
Pattern reduction
Free letter
Given a pattern over some alphabet , we say is free for if there exist subsets of such that the following hold:
- is a factor of and ↔ is a factor of and
For example, let , then is free for since there exist satisfying the conditions above.
Reduce
A pattern reduces to pattern if there exists a symbol such that is free for , and can be obtained by removing all occurrence of from . Denote this relation by .
For example, let , then can reduce to since is free for .
Locked
A word is said to be locked if has no free letter; hence can not be reduced.[6]
Transitivity
Given patterns , if reduces to and reduces to , then reduces to . Denote this relation by .
Unavoidability
A pattern is unavoidable if and only if reduces to a word of length one; hence such that and .[7][4]
Graph pattern avoidance[8]
Avoidance / Matching on a specific graph
Given a simple graph , a edge coloring matches pattern if there exists a simple path in such that the sequence matches . Otherwise, is said to avoid or be -free.
Similarly, a vertex coloring matches pattern if there exists a simple path in such that the sequence matches .
Pattern chromatic number
The pattern chromatic number is the minimal number of distinct colors needed for a -free vertex coloring over the graph .
Let where is the set of all simple graphs with a maximum degree no more than .
Similarly, and are defined for edge colorings.
Avoidability / Unavoidability on graphs
A pattern is avoidable on graphs if is bounded by , where only depends on .
- Avoidance on words can be expressed as a specific case of avoidance on graphs; hence a pattern is avoidable on any finite alphabet if and only if for all , where is a graph of vertices concatenated.
Probabilistic bound on πp(n)
There exists an absolute constant , such that for all patterns with .[8]
Given a pattern , let represent the number of distinct symbols of . If , then is avoidable on graphs.
Explicit colorings
Given a pattern such that is even for all , then for all , where is the complete graph of vertices.[8]
Given a pattern such that , and an arbitrary tree , let be the set of all avoidable subpatterns and their reflections of . Then .[8]
Given a pattern such that , and a tree with degree . Let be the set of all avoidable subpatterns and their reflections of , then .[8]
Examples
- The Thue–Morse sequence is cube-free and overlap-free; hence it avoids the patterns and .[2]
- A square-free word is one avoiding the pattern . The word over the alphabet obtained by taking the first difference of the Thue–Morse sequence is an example of an infinite square-free word.[9][10]
- The patterns and are unavoidable on any alphabet, since they are factors of the Zimin words.[11][1]
- The power patterns for are 2-avoidable.[1]
- All binary patterns can be divided into three categories:[1]
- are unavoidable.
- have avoidability index of 3.
- others have avoidability index of 2.
- has avoidability index of 4, as well as other locked words.[6]
- has avoidability index of 5.[12]
- The repetitive threshold is the infimum of exponents such that is avoidable on an alphabet of size . Also see Dejean's theorem.
Open problems
- Is there an avoidable pattern such that the avoidability index of is 6?
- Given an arbitrarily pattern , is there an algorithm to determine the avoidability index of ?[1]
References
- ^ a b c d e f g Lothaire, M. (2002). Algebraic Combinatorics on Words. Cambridge University Press. ISBN 9780521812207.
- ^ a b Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Soc. p. 127. ISBN 978-0-8218-7325-0.
- ^ a b c d e Schmidt, Ursula (1987-08-01). "Long unavoidable patterns". Acta Informatica. 24 (4): 433–445. doi:10.1007/BF00292112. ISSN 1432-0525. S2CID 7928450.
- ^ a b c Zimin, A. I. (1984). "Blocking Sets of Terms". Mathematics of the USSR-Sbornik. 47 (2): 353–364. Bibcode:1984SbMat..47..353Z. doi:10.1070/SM1984v047n02ABEH002647. ISSN 0025-5734.
- ^ Joshua, Cooper; Rorabaugh, Danny (2013). Bounds on Zimin Word Avoidance. arXiv:1409.3080. Bibcode:2014arXiv1409.3080C.
- ^ a b Baker, Kirby A.; McNulty, George F.; Taylor, Walter (1989-12-18). "Growth problems for avoidable words". Theoretical Computer Science. 69 (3): 319–345. doi:10.1016/0304-3975(89)90071-6. ISSN 0304-3975.
- ^ Bean, Dwight R.; Ehrenfeucht, Andrzej; McNulty, George F. (1979). "Avoidable patterns in strings of symbols". Pacific Journal of Mathematics. 85 (2): 261–294. doi:10.2140/pjm.1979.85.261. ISSN 0030-8730.
- ^ a b c d e Grytczuk, Jarosław (2007-05-28). "Pattern avoidance on graphs". Discrete Mathematics. The Fourth Caracow Conference on Graph Theory. 307 (11): 1341–1346. doi:10.1016/j.disc.2005.11.071. ISSN 0012-365X.
- ^ Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Soc. p. 97. ISBN 978-0-8218-7325-0.
- ^ Fogg, N. Pytheas (2002-09-23). Substitutions in Dynamics, Arithmetics and Combinatorics. Springer Science & Business Media. p. 104. ISBN 978-3-540-44141-0.
- ^ Allouche, Jean-Paul; Shallit, Jeffrey; Shallit, Professor Jeffrey (2003-07-21). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. p. 24. ISBN 978-0-521-82332-6.
- ^ 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. doi:10.1142/S0218196706002950. ISSN 0218-1967.
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
- Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
- Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.