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 "p"-free word.
Given a pattern formula_1 and an alphabet "formula_8". A formula_1-free word "formula_43" is a maximal formula_1-free word over "formula_8" if formula_46 and formula_47 match formula_1 formula_49.
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.
"k"-avoidable / "k"-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_64-avoidable for all formula_65.
Given a finite set of avoidable patterns formula_66, there exists an infinite word formula_67 such that formula_19 avoids all patterns of formula_69. Let formula_70 denote the size of the minimal alphabet formula_71such that formula_72 avoiding all patterns of formula_69.
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_78" if "formula_1" is unavoidable.
Zimin words.
Given alphabet formula_103, Zimin words (patterns) are defined recursively formula_104 for formula_105 and formula_106.
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_109 represent the smallest formula_110 such that formula_19 matches formula_112 for all formula_113. We have following properties:
formula_112 is the longest unavoidable pattern constructed by alphabet formula_119 since formula_120.
Pattern reduction.
Free letter.
Given a pattern "formula_1" over some alphabet formula_9, we say formula_123 is free for "formula_1" if there exist subsets formula_125 of formula_9 such that the following hold:
For example, let "formula_134", then "formula_135" is free for "formula_1" since there exist "formula_137" satisfying the conditions above.
Reduce.
A pattern "formula_138" reduces to pattern "formula_80" if there exists a symbol "formula_140" such that "formula_4" is free for "formula_1", and "formula_80" can be obtained by removing all occurrence of "formula_4" from "formula_1". Denote this relation by formula_146.
For example, let "formula_134", then "formula_1" can reduce to "formula_149" since "formula_135" 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_155", if "formula_1" reduces to "formula_80" and "formula_80" reduces to "formula_159", then "formula_1" reduces to "formula_159". Denote this relation by formula_162.
Unavoidability.
A pattern "formula_1" is unavoidable if and only if "formula_1" reduces to a word of length one; hence "formula_165" such that "formula_166" and "formula_167".
Graph pattern avoidance.
Avoidance / Matching on a specific graph.
Given a simple graph "formula_168", a edge coloring "formula_169" matches pattern "formula_1" if there exists a simple path "formula_171" in "formula_172" such that the sequence "formula_173" matches "formula_1". Otherwise, "formula_175" is said to avoid "formula_1" or be "formula_1"-free.
Similarly, a vertex coloring "formula_178" matches pattern "formula_1" if there exists a simple path "formula_180" in "formula_172" such that the sequence "formula_182" matches "formula_1".
Pattern chromatic number.
The pattern chromatic number formula_184 is the minimal number of distinct colors needed for a "formula_1"-free vertex coloring "formula_175" over the graph "formula_172".
Let "formula_188" where "formula_189" is the set of all simple graphs with a maximum degree no more than "formula_190". 
Similarly, formula_191 and formula_192 are defined for edge colorings. 
Avoidability / Unavoidability on graphs.
A pattern "formula_1" is avoidable on graphs if "formula_194" is bounded by "formula_195", where "formula_195" only depends on "formula_1". 
Probabilistic bound on "πp(n)".
There exists an absolute constant formula_175, such that "formula_204" for all patterns "formula_1" with "formula_206".
Given a pattern formula_1, let formula_190 represent the number of distinct symbols of formula_1. If formula_101, then formula_1 is avoidable on graphs.
Explicit colorings.
Given a pattern formula_1 such that "formula_213" is even for all "formula_214", then formula_215 for all "formula_216", where "formula_217" is the complete graph of formula_190 vertices.
Given a pattern formula_1 such that "formula_206", and an arbitrary tree formula_221, let formula_69 be the set of all avoidable subpatterns and their reflections of formula_1. Then formula_224.
Given a pattern formula_1 such that "formula_206", and a tree formula_221 with degree "formula_228". Let formula_69 be the set of all avoidable subpatterns and their reflections of formula_1, then formula_231.
References.
 ;templatestyles src="Reflist/styles.css" / ;