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.
is the number of occurrence of symbol
In other words, it is the number of occurrences in
if there exists a non-erasing semigroup morphism
denotes the Kleene star of
if a factor (also called subword or substring) of
This definition can be generalized to the case of an infinite
, based on a generalized definition of "substring".
, which implies there exist infinitely many words over the alphabet
if and only if there exists an infinite word
is an unavoidable pattern (also called blocking term) if
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.
Given a finite set of avoidable patterns
, there exists an infinite word
denote the size of the minimal alphabet
, Zimin words (patterns) are defined recursively
is unavoidable if and only if it is a factor of a Zimin word.
is the longest unavoidable pattern constructed by alphabet
can be obtained by removing all occurrence of
if there exists a simple path
Similarly, a vertex coloring
if there exists a simple path
is the minimal number of distinct colors needed for a
is the set of all simple graphs with a maximum degree no more than
There exists an absolute constant
represent the number of distinct symbols of
be the set of all avoidable subpatterns and their reflections of
be the set of all avoidable subpatterns and their reflections of