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 .
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 '.
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 .
The avoidability index of a pattern ' is the smallest ' such that ' is '-avoidable, and ' if ' is unavoidable.
Given alphabet , Zimin words (patterns) are defined recursively for and .
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 .
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.
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 '.
Source:
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 '.
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.
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 .