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

-avoidable / -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:

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

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

  1. Lothaire, M. (2002). Algebraic Combinatorics on Words. Cambridge University Press. ISBN 9780521812207.
  2. Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Soc. p. 127. ISBN 978-0-8218-7325-0.
  3. Schmidt, Ursula (1987-08-01). "Long unavoidable patterns". Acta Informatica. 24 (4): 433–445. doi:10.1007/BF00292112. ISSN 1432-0525. S2CID 7928450.
  4. 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.
  5. Joshua, Cooper; Rorabaugh, Danny (2013). Bounds on Zimin Word Avoidance. arXiv:1409.3080. Bibcode:2014arXiv1409.3080C.
  6. 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.
  7. 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.
  8. 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.
  9. Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Soc. p. 97. ISBN 978-0-8218-7325-0.
  10. Fogg, N. Pytheas (2002-09-23). Substitutions in Dynamics, Arithmetics and Combinatorics. Springer Science & Business Media. p. 104. ISBN 978-3-540-44141-0.
  11. 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.
  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. doi:10.1142/S0218196706002950. ISSN 0218-1967.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.