In mathematics and theoretical computer science, a pattern is an unavoidable pattern if it is unavoidable on any finite alphabet.
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 .
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.
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".
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]
Given a pattern and an alphabet . A -free word is a maximal -free word over if and match .
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.
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 .
The avoidability index of a pattern is the smallest such that is -avoidable, and if is unavoidable. [1]
Given alphabet , Zimin words (patterns) are defined recursively for and .
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 .
Given a pattern over some alphabet , we say is free for if there exist subsets of such that the following hold:
For example, let , then is free for since there exist satisfying the conditions above.
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 .
A word is said to be locked if has no free letter; hence can not be reduced. [6]
Given patterns , if reduces to and reduces to , then reduces to . Denote this relation by .
A pattern is unavoidable if and only if reduces to a word of length one; hence such that and . [7] [4]
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 .
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.
A pattern is avoidable on graphs if is bounded by , where only depends 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.
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]
In mathematics and theoretical computer science, a pattern is an unavoidable pattern if it is unavoidable on any finite alphabet.
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 .
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.
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".
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]
Given a pattern and an alphabet . A -free word is a maximal -free word over if and match .
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.
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 .
The avoidability index of a pattern is the smallest such that is -avoidable, and if is unavoidable. [1]
Given alphabet , Zimin words (patterns) are defined recursively for and .
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 .
Given a pattern over some alphabet , we say is free for if there exist subsets of such that the following hold:
For example, let , then is free for since there exist satisfying the conditions above.
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 .
A word is said to be locked if has no free letter; hence can not be reduced. [6]
Given patterns , if reduces to and reduces to , then reduces to . Denote this relation by .
A pattern is unavoidable if and only if reduces to a word of length one; hence such that and . [7] [4]
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 .
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.
A pattern is avoidable on graphs if is bounded by , where only depends 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.
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]