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. Section::::"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. Unavoidable pattern