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 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 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.
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 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 .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. 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.Properties
- A pattern is avoidable if is an instance of an avoidable pattern '.
- Let avoidable pattern ' be a factor of pattern ', then ' is also avoidable.
- 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.
- Given an unavoidable pattern ', then the reversal ' is unavoidable.
- Given an unavoidable pattern ', there exists a symbol ' such that ' occurs exactly once in .
- Let represent the number of distinct symbols of pattern. If, then is avoidable.
Zimin words
Unavoidability
All Zimin words are unavoidable.A word is unavoidable if and only if it is a factor of a Zimin word.
Given a finite alphabet, let represent the smallest such that matches for all. We have following properties:
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 '
- '
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.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 .Graph pattern avoidance
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 ''''
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.Given a pattern such that ', and an arbitrary tree, let be the set of all avoidable subpatterns and their reflections of. Then.
Given a pattern such that ', and a tree with degree . Let be the set of all avoidable subpatterns and their reflections of, then.
Examples
- The Thue–Morse sequence is cube-free and overlap-free; hence it avoids the patterns ' and '.
- 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.
- The patterns ' and ' are unavoidable on any alphabet, since they are factors of the Zimin words.
- The power patterns ' for are 2-avoidable.
- All binary patterns can be divided into three categories:
- * are unavoidable.
- * have avoidability index of 3.
- *others have avoidability index of 2.
- has avoidability index of 4, as well as other locked words.
- has avoidability index of 5.
- 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 ?
- Are all avoidable patterns also avoidable on graphs?