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 "formula_1" is "formula_2" where "formula_3" is the number of occurrence of symbol "formula_4" in pattern "formula_1". In other words, it is the number of occurrences in "formula_1" of the least frequently occurring symbol in "formula_1". 
Instance.
Given finite alphabets formula_8 and formula_9, a word formula_10 is an instance of the pattern formula_11 if there exists a non-erasing semigroup morphism formula_12 such that formula_13, where formula_14 denotes the Kleene star of formula_8. Non-erasing means that formula_16 for all formula_17, where formula_18 denotes the empty string.
Avoidance / Matching.
A word formula_19 is said to "match", or "encounter", a pattern formula_1 if a factor (also called "subword" or "substring") of formula_19 is an instance of formula_1. Otherwise, formula_19 is said to avoid formula_1, or to be formula_1-free. This definition can be generalized to the case of an infinite formula_19, based on a generalized definition of "substring".
Avoidability / Unavoidability on a specific alphabet.
A pattern formula_1 is "unavoidable" on a finite alphabet formula_8 if each sufficiently long word formula_10 must match formula_1; formally: if formula_31. Otherwise, formula_1 is "avoidable" on formula_8, which implies there exist infinitely many words over the alphabet formula_8 that avoid formula_1. 
By Kőnig's lemma, pattern formula_1 is avoidable on formula_8 if and only if there exists an infinite word formula_38 that avoids formula_1.
Maximal formula_1-free word.
Given a pattern formula_1 and an alphabet "formula_8". A formula_1-free word "formula_44" is a maximal formula_1-free word over "formula_8" if formula_47 and formula_48 match formula_1 formula_50.
Avoidable / Unavoidable pattern.
A pattern "formula_1" is an unavoidable pattern (also called "blocking term") if "formula_1" 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.
"formula_53"-avoidable / "formula_53"-unavoidable.
A pattern "formula_1" is "formula_53"-avoidable if "formula_1" is avoidable on an alphabet "formula_8" of size "formula_53". Otherwise, "formula_1" is "formula_53"-unavoidable, which means "formula_1" is unavoidable on every alphabet of size "formula_53".
If pattern formula_1 is formula_53-avoidable, then formula_1 is formula_67-avoidable for all formula_68.
Given a finite set of avoidable patterns formula_69, there exists an infinite word formula_70 such that formula_19 avoids all patterns of formula_72. Let formula_73 denote the size of the minimal alphabet formula_74such that formula_75 avoiding all patterns of formula_72.
Avoidability index.
The avoidability index of a pattern "formula_1" is the smallest "formula_53" such that "formula_1" is "formula_53"-avoidable, and "formula_81" if "formula_1" is unavoidable.
Zimin words.
Given alphabet formula_106, Zimin words (patterns) are defined recursively formula_107 for formula_108 and formula_109.
Unavoidability.
All Zimin words are unavoidable.
A word "formula_19" is unavoidable if and only if it is a factor of a Zimin word.
Given a finite alphabet formula_8, let formula_112 represent the smallest formula_113 such that formula_19 matches formula_115 for all formula_116. We have following properties:
formula_115 is the longest unavoidable pattern constructed by alphabet formula_122 since formula_123.
Pattern reduction.
Free letter.
Given a pattern "formula_1" over some alphabet formula_9, we say formula_126 is free for "formula_1" if there exist subsets formula_128 of formula_9 such that the following hold:
For example, let "formula_137", then "formula_138" is free for "formula_1" since there exist "formula_140" satisfying the conditions above.
Reduce.
A pattern "formula_141" reduces to pattern "formula_83" if there exists a symbol "formula_143" such that "formula_4" is free for "formula_1", and "formula_83" can be obtained by removing all occurrence of "formula_4" from "formula_1". Denote this relation by formula_149.
For example, let "formula_137", then "formula_1" can reduce to "formula_152" since "formula_138" is free for "formula_1".
Locked.
A word "formula_19" is said to be locked if "formula_19" has no free letter; hence "formula_19" can not be reduced.
Transitivity.
Given patterns "formula_158", if "formula_1" reduces to "formula_83" and "formula_83" reduces to "formula_162", then "formula_1" reduces to "formula_162". Denote this relation by formula_165.
Unavoidability.
A pattern "formula_1" is unavoidable if and only if "formula_1" reduces to a word of length one; hence "formula_168" such that "formula_169" and "formula_170".
Graph pattern avoidance.
Avoidance / Matching on a specific graph.
Given a simple graph "formula_171", a edge coloring "formula_172" matches pattern "formula_1" if there exists a simple path "formula_174" in "formula_175" such that the sequence "formula_176" matches "formula_1". Otherwise, "formula_178" is said to avoid "formula_1" or be "formula_1"-free.
Similarly, a vertex coloring "formula_181" matches pattern "formula_1" if there exists a simple path "formula_183" in "formula_175" such that the sequence "formula_185" matches "formula_1".
Pattern chromatic number.
The pattern chromatic number formula_187 is the minimal number of distinct colors needed for a "formula_1"-free vertex coloring "formula_178" over the graph "formula_175".
Let "formula_191" where "formula_192" is the set of all simple graphs with a maximum degree no more than "formula_193". 
Similarly, formula_194 and formula_195 are defined for edge colorings. 
Avoidability / Unavoidability on graphs.
A pattern "formula_1" is avoidable on graphs if "formula_197" is bounded by "formula_198", where "formula_198" only depends on "formula_1". 
Probabilistic bound on "formula_197".
There exists an absolute constant formula_178, such that "formula_208" for all patterns "formula_1" with "formula_210".
Given a pattern formula_1, let formula_193 represent the number of distinct symbols of formula_1. If formula_104, then formula_1 is avoidable on graphs.
Explicit colorings.
Given a pattern formula_1 such that "formula_217" is even for all "formula_218", then formula_219 for all "formula_220", where "formula_221" is the complete graph of formula_193 vertices.
Given a pattern formula_1 such that "formula_210", and an arbitrary tree formula_225, let formula_72 be the set of all avoidable subpatterns and their reflections of formula_1. Then formula_228.
Given a pattern formula_1 such that "formula_210", and a tree formula_225 with degree "formula_232". Let formula_72 be the set of all avoidable subpatterns and their reflections of formula_1, then formula_235.