Unavoidable pattern - Revision history

Citation bot: Altered template type. Add: class, date, title, eprint, authors 1-2. Changed bare reference to CS1/2. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2025-05-19T00:33:17Z

Altered template type. Add: class, date, title, eprint, authors 1-2. Changed bare reference to CS1/2. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 00:33, 19 May 2025
Line 56:		Line 56:
	A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|bibcode=1984SbMat..47..353Z\|issn=0025-5734}}</ref>		A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|bibcode=1984SbMat..47..353Z\|issn=0025-5734}}</ref>

	Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{~~arxiv~~\|1409.3080}}</ref>		Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{cite arXiv \| eprint=1409.3080 \| last1=Cooper \| first1=Joshua \| last2=Rorabaugh \| first2=Danny \| title=Bounds on Zimin Word Avoidance \| date=2014 \| class=math.CO }}</ref>

	*<math>f(1,q)=1</math>		*<math>f(1,q)=1</math>

Headbomb: ce

2025-05-19T00:32:42Z

← Previous revision		Revision as of 00:32, 19 May 2025
Line 56:		Line 56:
	A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|bibcode=1984SbMat..47..353Z\|issn=0025-5734}}</ref>		A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|bibcode=1984SbMat..47..353Z\|issn=0025-5734}}</ref>

	Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{~~cite book\|last1=Joshua\|first1=Cooper\|url=https://archive.org/details/~~arxiv~~-1409.3080~~\|~~title=Bounds on Zimin Word Avoidance\|last2=Rorabaugh\|first2=Danny\|year=2013\|publisher=arXiv.org \|arxiv=~~1409.3080~~\|bibcode=2014arXiv1409.3080C~~}}</ref>		Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{arxiv\|1409.3080}}</ref>

	*<math>f(1,q)=1</math>		*<math>f(1,q)=1</math>

Citation bot: Added publisher. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Formal languages | #UCB_Category 109/201

2024-10-07T09:27:30Z

Added publisher. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Formal languages | #UCB_Category 109/201

← Previous revision		Revision as of 09:27, 7 October 2024
Line 56:		Line 56:
	A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|bibcode=1984SbMat..47..353Z\|issn=0025-5734}}</ref>		A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|bibcode=1984SbMat..47..353Z\|issn=0025-5734}}</ref>

	Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{cite book\|last1=Joshua\|first1=Cooper\|url=https://archive.org/details/arxiv-1409.3080\|title=Bounds on Zimin Word Avoidance\|last2=Rorabaugh\|first2=Danny\|year=2013\|arxiv=1409.3080\|bibcode=2014arXiv1409.3080C}}</ref>		Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{cite book\|last1=Joshua\|first1=Cooper\|url=https://archive.org/details/arxiv-1409.3080\|title=Bounds on Zimin Word Avoidance\|last2=Rorabaugh\|first2=Danny\|year=2013\|publisher=arXiv.org \|arxiv=1409.3080\|bibcode=2014arXiv1409.3080C}}</ref>

	*<math>f(1,q)=1</math>		*<math>f(1,q)=1</math>

GhostInTheMachine: /* Probabilistic bound on \pi_p(n) */ remove math tags from heading

2024-08-30T21:14:32Z

Probabilistic bound on \pi_p(n): remove math tags from heading

← Previous revision		Revision as of 21:14, 30 August 2024
Line 108:		Line 108:
	* Avoidance on words can be expressed as a specific case of avoidance on graphs; hence a pattern <math>p</math> is avoidable on any finite alphabet if and only if <math>\pi_p(P_n) \leq c_p</math> for all <math>n \in\Zeta ^+ </math>, where <math>P_n</math> is a graph of <math>n</math> vertices concatenated.		* Avoidance on words can be expressed as a specific case of avoidance on graphs; hence a pattern <math>p</math> is avoidable on any finite alphabet if and only if <math>\pi_p(P_n) \leq c_p</math> for all <math>n \in\Zeta ^+ </math>, where <math>P_n</math> is a graph of <math>n</math> vertices concatenated.

	=== Probabilistic bound on ''~~<math>\pi_p~~(n)~~</math>~~'' ===		=== Probabilistic bound on ''{{pi}}{{sub\|p}}(n)'' ===
	There exists an absolute constant <math>c</math>, such that ''<math>\pi_p(n)\leq cn^{\frac{m(p)}{m(p)-1}}\leq cn^2</math>'' for all patterns ''<math>p</math>'' with ''<math>m(p)\geq2</math>''.<ref name=":4" />		There exists an absolute constant <math>c</math>, such that ''<math>\pi_p(n)\leq cn^{\frac{m(p)}{m(p)-1}}\leq cn^2</math>'' for all patterns ''<math>p</math>'' with ''<math>m(p)\geq2</math>''.<ref name=":4" />

Dexxor: don't use $in headings$

2024-01-05T10:13:25Z

don't use <math> in headings

← Previous revision		Revision as of 10:13, 5 January 2024
Line 19:		Line 19:
	By [[Kőnig's lemma]], pattern <math>p</math> is avoidable on <math>\Sigma</math> [[if, and only if\|if and only if]] there exists an [[infinite sequence\|infinite word]] <math>w\in \Sigma^\omega</math> that avoids <math>p</math>.<ref name="Lothaire2001" />		By [[Kőnig's lemma]], pattern <math>p</math> is avoidable on <math>\Sigma</math> [[if, and only if\|if and only if]] there exists an [[infinite sequence\|infinite word]] <math>w\in \Sigma^\omega</math> that avoids <math>p</math>.<ref name="Lothaire2001" />

	=== Maximal ~~<math>~~p~~</math>~~-free word ===		=== Maximal ''p''-free word ===
	Given a pattern <math>p</math> and an alphabet ''<math>\Sigma</math>''. A <math>p</math>-free word ''<math>w\in\Sigma^*</math>'' is a maximal <math>p</math>-free word over ''<math>\Sigma</math>'' if <math>aw</math> and <math>wa</math> match <math>p</math> <math>\forall a\in\Sigma</math>.		Given a pattern <math>p</math> and an alphabet ''<math>\Sigma</math>''. A <math>p</math>-free word ''<math>w\in\Sigma^*</math>'' is a maximal <math>p</math>-free word over ''<math>\Sigma</math>'' if <math>aw</math> and <math>wa</math> match <math>p</math> <math>\forall a\in\Sigma</math>.

Line 27:		Line 27:
	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.		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.

	=== ''~~<math>~~k~~</math>~~''-avoidable / ''~~<math>~~k~~</math>~~''-unavoidable ===		=== ''k''-avoidable / ''k''-unavoidable ===
	A pattern ''<math>p</math>'' is ''<math>k</math>''-avoidable if ''<math>p</math>'' is avoidable on an alphabet ''<math>\Sigma</math>'' of size ''<math>k</math>''. Otherwise, ''<math>p</math>'' is ''<math>k</math>''-unavoidable, which means ''<math>p</math>'' is unavoidable on every alphabet of size ''<math>k</math>''.<ref name=":5">{{Cite book\|url=https://books.google.com/books?id=3w9eR3u8GN4C&q=Combinatorics+on+words.+Christoffel+words+and+repetitions+in+words+2009\|title=Combinatorics on Words: Christoffel Words and Repetitions in Words\|publisher=American Mathematical Soc.\|isbn=978-0-8218-7325-0\|pages=127\|language=en}}</ref>		A pattern ''<math>p</math>'' is ''<math>k</math>''-avoidable if ''<math>p</math>'' is avoidable on an alphabet ''<math>\Sigma</math>'' of size ''<math>k</math>''. Otherwise, ''<math>p</math>'' is ''<math>k</math>''-unavoidable, which means ''<math>p</math>'' is unavoidable on every alphabet of size ''<math>k</math>''.<ref name=":5">{{Cite book\|url=https://books.google.com/books?id=3w9eR3u8GN4C&q=Combinatorics+on+words.+Christoffel+words+and+repetitions+in+words+2009\|title=Combinatorics on Words: Christoffel Words and Repetitions in Words\|publisher=American Mathematical Soc.\|isbn=978-0-8218-7325-0\|pages=127\|language=en}}</ref>

Citation bot: Removed parameters. | Use this bot. Report bugs. | Suggested by Abductive | Category:Formal languages | #UCB_Category 73/202

2023-07-26T07:26:44Z

Removed parameters. | Use this bot. Report bugs. | Suggested by Abductive | Category:Formal languages | #UCB_Category 73/202

← Previous revision		Revision as of 07:26, 26 July 2023
Line 56:		Line 56:
	A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|bibcode=1984SbMat..47..353Z\|issn=0025-5734}}</ref>		A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|bibcode=1984SbMat..47..353Z\|issn=0025-5734}}</ref>

	Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{cite book\|last1=Joshua\|first1=Cooper\|url=https://archive.org/details/arxiv-1409.3080\|title=Bounds on Zimin Word Avoidance\|last2=Rorabaugh\|first2=Danny\|year=2013~~\|publisher=arXiv.org~~\|arxiv=1409.3080\|bibcode=2014arXiv1409.3080C}}</ref>		Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{cite book\|last1=Joshua\|first1=Cooper\|url=https://archive.org/details/arxiv-1409.3080\|title=Bounds on Zimin Word Avoidance\|last2=Rorabaugh\|first2=Danny\|year=2013\|arxiv=1409.3080\|bibcode=2014arXiv1409.3080C}}</ref>

	*<math>f(1,q)=1</math>		*<math>f(1,q)=1</math>

194.254.113.75: ABACADBC is avoidable but unavoidable on graphs. On some interesting ternary formulas. Pascal Ochem and Matthieu Rosenfeld. Electron. J. Comb. 26(1) (2019), #P1.12.

2022-03-22T09:40:21Z

ABACADBC is avoidable but unavoidable on graphs. On some interesting ternary formulas. Pascal Ochem and Matthieu Rosenfeld. Electron. J. Comb. 26(1) (2019), #P1.12.

← Previous revision		Revision as of 09:40, 22 March 2022
Line 138:		Line 138:
	*Is there an avoidable pattern <math>p</math> such that the avoidability index of <math>p</math> is 6?		*Is there an avoidable pattern <math>p</math> such that the avoidability index of <math>p</math> is 6?
	*Given an arbitrarily pattern <math>p</math>, is there an algorithm to determine the avoidability index of <math>p</math>?<ref name="Lothaire2001" />		*Given an arbitrarily pattern <math>p</math>, is there an algorithm to determine the avoidability index of <math>p</math>?<ref name="Lothaire2001" />
	*Are all avoidable patterns also avoidable on graphs?<ref name=":2">{{Cite journal\|last=Grytczuk\|first=Jarosław\|date=2007-05-28\|title=Pattern avoidance on graphs\|journal=Discrete Mathematics\|series=The Fourth Caracow Conference on Graph Theory\|language=en\|volume=307\|issue=11\|pages=1341–1346\|doi=10.1016/j.disc.2005.11.071\|issn=0012-365X\|doi-access=free}}</ref>

	==References==		==References==

Citation bot: Alter: url. URLs might have been anonymized. Add: isbn, publisher, bibcode. Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Abductive | Category:Formal languages | #UCB_Category 67/214

2021-12-11T12:02:56Z

Alter: url. URLs might have been anonymized. Add: isbn, publisher, bibcode. Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Abductive | Category:Formal languages | #UCB_Category 67/214

OAbot: Open access bot: doi added to citation with #oabot.

2021-07-06T14:00:52Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 14:00, 6 July 2021
Line 81:		Line 81:

	=== Locked ===		=== Locked ===
	A word ''<math>w</math>'' is said to be locked if ''<math>w</math>'' has no free letter; hence ''<math>w</math>'' can not be reduced.<ref name=":3">{{Cite journal\|last1=Baker\|first1=Kirby A.\|last2=McNulty\|first2=George F.\|last3=Taylor\|first3=Walter\|date=1989-12-18\|title=Growth problems for avoidable words\|url=https://dx.doi.org/10.1016%2F0304-3975%2889%2990071-6\|journal=Theoretical Computer Science\|language=en\|volume=69\|issue=3\|pages=319–345\|doi=10.1016/0304-3975(89)90071-6\|issn=0304-3975}}</ref>		A word ''<math>w</math>'' is said to be locked if ''<math>w</math>'' has no free letter; hence ''<math>w</math>'' can not be reduced.<ref name=":3">{{Cite journal\|last1=Baker\|first1=Kirby A.\|last2=McNulty\|first2=George F.\|last3=Taylor\|first3=Walter\|date=1989-12-18\|title=Growth problems for avoidable words\|url=https://dx.doi.org/10.1016%2F0304-3975%2889%2990071-6\|journal=Theoretical Computer Science\|language=en\|volume=69\|issue=3\|pages=319–345\|doi=10.1016/0304-3975(89)90071-6\|issn=0304-3975\|doi-access=free}}</ref>

	=== Transitivity ===		=== Transitivity ===
Line 89:		Line 89:
	A pattern ''<math>p</math>'' is unavoidable if and only if ''<math>p</math>'' reduces to a word of length one; hence ''<math>\exist w</math>'' such that ''<math>\|w\|=1</math>'' and ''<math>p\stackrel{*}{\rightarrow}w</math>''.<ref>{{Cite journal\|last1=Bean\|first1=Dwight R.\|last2=Ehrenfeucht\|first2=Andrzej\|last3=McNulty\|first3=George F.\|date=1979\|title=Avoidable patterns in strings of symbols.\|url=https://projecteuclid.org/euclid.pjm/1102783913\|journal=Pacific Journal of Mathematics\|language=en\|volume=85\|issue=2\|pages=261–294\|doi=10.2140/pjm.1979.85.261\|issn=0030-8730\|doi-access=free}}</ref><ref name=":0" />		A pattern ''<math>p</math>'' is unavoidable if and only if ''<math>p</math>'' reduces to a word of length one; hence ''<math>\exist w</math>'' such that ''<math>\|w\|=1</math>'' and ''<math>p\stackrel{*}{\rightarrow}w</math>''.<ref>{{Cite journal\|last1=Bean\|first1=Dwight R.\|last2=Ehrenfeucht\|first2=Andrzej\|last3=McNulty\|first3=George F.\|date=1979\|title=Avoidable patterns in strings of symbols.\|url=https://projecteuclid.org/euclid.pjm/1102783913\|journal=Pacific Journal of Mathematics\|language=en\|volume=85\|issue=2\|pages=261–294\|doi=10.2140/pjm.1979.85.261\|issn=0030-8730\|doi-access=free}}</ref><ref name=":0" />

	== Graph pattern avoidance<ref name=":4">{{Cite journal\|last=Grytczuk\|first=Jarosław\|date=2007-05-28\|title=Pattern avoidance on graphs\|url=http://www.sciencedirect.com/science/article/pii/S0012365X06007291\|journal=Discrete Mathematics\|series=The Fourth Caracow Conference on Graph Theory\|language=en\|volume=307\|issue=11\|pages=1341–1346\|doi=10.1016/j.disc.2005.11.071\|issn=0012-365X}}</ref>==		== Graph pattern avoidance<ref name=":4">{{Cite journal\|last=Grytczuk\|first=Jarosław\|date=2007-05-28\|title=Pattern avoidance on graphs\|url=http://www.sciencedirect.com/science/article/pii/S0012365X06007291\|journal=Discrete Mathematics\|series=The Fourth Caracow Conference on Graph Theory\|language=en\|volume=307\|issue=11\|pages=1341–1346\|doi=10.1016/j.disc.2005.11.071\|issn=0012-365X\|doi-access=free}}</ref>==

	=== Avoidance / Matching on a specific graph ===		=== Avoidance / Matching on a specific graph ===
Line 138:		Line 138:
	*Is there an avoidable pattern <math>p</math> such that the avoidability index of <math>p</math> is 6?		*Is there an avoidable pattern <math>p</math> such that the avoidability index of <math>p</math> is 6?
	*Given an arbitrarily pattern <math>p</math>, is there an algorithm to determine the avoidability index of <math>p</math>?<ref name="Lothaire2001" />		*Given an arbitrarily pattern <math>p</math>, is there an algorithm to determine the avoidability index of <math>p</math>?<ref name="Lothaire2001" />
	*Are all avoidable patterns also avoidable on graphs?<ref name=":2">{{Cite journal\|last=Grytczuk\|first=Jarosław\|date=2007-05-28\|title=Pattern avoidance on graphs\|journal=Discrete Mathematics\|series=The Fourth Caracow Conference on Graph Theory\|language=en\|volume=307\|issue=11\|pages=1341–1346\|doi=10.1016/j.disc.2005.11.071\|issn=0012-365X}}</ref>		*Are all avoidable patterns also avoidable on graphs?<ref name=":2">{{Cite journal\|last=Grytczuk\|first=Jarosław\|date=2007-05-28\|title=Pattern avoidance on graphs\|journal=Discrete Mathematics\|series=The Fourth Caracow Conference on Graph Theory\|language=en\|volume=307\|issue=11\|pages=1341–1346\|doi=10.1016/j.disc.2005.11.071\|issn=0012-365X\|doi-access=free}}</ref>

	==References==		==References==

Adumbrativus: Take prime symbol out of superscript

2021-06-19T00:58:20Z

Take prime symbol out of superscript

← Previous revision		Revision as of 00:58, 19 June 2021
Line 32:		Line 32:
	If pattern <math>p</math> is '''<math>k</math>'''-avoidable, then <math>p</math> is '''<math>g</math>'''-avoidable for all '''''<math>g\geq k</math>'''''.		If pattern <math>p</math> is '''<math>k</math>'''-avoidable, then <math>p</math> is '''<math>g</math>'''-avoidable for all '''''<math>g\geq k</math>'''''.

	Given a finite set of avoidable patterns <math>S=\{p_1,p_2,...,p_i \}</math>, there exists an infinite word <math>w\in\Sigma^\omega</math> such that <math>w</math> avoids all patterns of <math>S</math>.<ref name="Lothaire2001" /> Let <math>\mu(S)</math> denote the size of the minimal alphabet <math>\Sigma^'</math>such that <math>\exist w^'\in {\Sigma^'}^\omega</math> avoiding all patterns of <math>S</math>.		Given a finite set of avoidable patterns <math>S=\{p_1,p_2,...,p_i \}</math>, there exists an infinite word <math>w\in\Sigma^\omega</math> such that <math>w</math> avoids all patterns of <math>S</math>.<ref name="Lothaire2001" /> Let <math>\mu(S)</math> denote the size of the minimal alphabet <math>\Sigma'</math>such that <math>\exist w' \in {\Sigma'}^\omega</math> avoiding all patterns of <math>S</math>.

	=== Avoidability index ===		=== Avoidability index ===
Line 101:		Line 101:
	Let ''<math>\pi_p(n)=\max\{\pi_p(G):G\in G_n\}</math>'' where ''<math>G_n</math>'' is the set of all simple graphs with a maximum [[Degree (graph theory)\|degree]] no more than ''<math>n</math>''.		Let ''<math>\pi_p(n)=\max\{\pi_p(G):G\in G_n\}</math>'' where ''<math>G_n</math>'' is the set of all simple graphs with a maximum [[Degree (graph theory)\|degree]] no more than ''<math>n</math>''.

	Similarly, <math>\pi_p^'(G)</math> and <math>\~~pi _{p}^~~'(n)</math> are defined for edge colorings.		Similarly, <math>\pi_p'(G)</math> and <math>\pi_p'(n)</math> are defined for edge colorings.

	=== Avoidability / Unavoidability on graphs ===		=== Avoidability / Unavoidability on graphs ===
Line 114:		Line 114:

	=== Explicit colorings ===		=== Explicit colorings ===
	Given a pattern <math>p</math> such that ''<math>count_p(x)</math>'' is even for all ''<math>x\in p</math>'', then <math>\pi_p^'(K_2^k)\leq2^k-1</math> for all ''<math>k\geq 1</math>'', where ''<math>K_n</math>'' is the [[complete graph]] of <math>n</math> vertices.<ref name=":4" />		Given a pattern <math>p</math> such that ''<math>count_p(x)</math>'' is even for all ''<math>x\in p</math>'', then <math>\pi_p'(K_2^k)\leq2^k-1</math> for all ''<math>k\geq 1</math>'', where ''<math>K_n</math>'' is the [[complete graph]] of <math>n</math> vertices.<ref name=":4" />

	Given a pattern <math>p</math> such that ''<math>m(p)\geq2</math>'', and an arbitrary [[Tree (graph theory)\|tree]] <math>T</math>, let <math>S</math> be the set of all avoidable subpatterns and their reflections of <math>p</math>. Then <math>\pi_p(T)\leq 3\mu(S)</math>.<ref name=":4" />		Given a pattern <math>p</math> such that ''<math>m(p)\geq2</math>'', and an arbitrary [[Tree (graph theory)\|tree]] <math>T</math>, let <math>S</math> be the set of all avoidable subpatterns and their reflections of <math>p</math>. Then <math>\pi_p(T)\leq 3\mu(S)</math>.<ref name=":4" />

	Given a pattern <math>p</math> such that ''<math>m(p)\geq2</math>'', and a [[Tree (graph theory)\|tree]] <math>T</math> with degree ''<math>n\geq2</math>''. Let <math>S</math> be the set of all avoidable subpatterns and their reflections of <math>p</math>, then <math>\pi_p^'(T)\leq 2(n-1)\mu(S)</math>.<ref name=":4" />		Given a pattern <math>p</math> such that ''<math>m(p)\geq2</math>'', and a [[Tree (graph theory)\|tree]] <math>T</math> with degree ''<math>n\geq2</math>''. Let <math>S</math> be the set of all avoidable subpatterns and their reflections of <math>p</math>, then <math>\pi_p'(T)\leq 2(n-1)\mu(S)</math>.<ref name=":4" />

	== Examples ==		== Examples ==

← Previous revision		Revision as of 12:02, 11 December 2021
Line 28:		Line 28:

	=== ''<math>k</math>''-avoidable / ''<math>k</math>''-unavoidable ===		=== ''<math>k</math>''-avoidable / ''<math>k</math>''-unavoidable ===
	A pattern ''<math>p</math>'' is ''<math>k</math>''-avoidable if ''<math>p</math>'' is avoidable on an alphabet ''<math>\Sigma</math>'' of size ''<math>k</math>''. Otherwise, ''<math>p</math>'' is ''<math>k</math>''-unavoidable, which means ''<math>p</math>'' is unavoidable on every alphabet of size ''<math>k</math>''.<ref name=":5">{{Cite book\|url=https://books.google.com/books?id=3w9eR3u8GN4C&~~printsec=frontcover&dq~~=Combinatorics+on+words.+Christoffel+words+and+repetitions+in+words+2009~~#q=Combinatorics%20on%20words.%20Christoffel%20words%20and%20repetitions%20in%20words%202009~~\|title=Combinatorics on Words: Christoffel Words and Repetitions in Words\|publisher=American Mathematical Soc.\|isbn=978-0-8218-7325-0\|pages=127\|language=en}}</ref>		A pattern ''<math>p</math>'' is ''<math>k</math>''-avoidable if ''<math>p</math>'' is avoidable on an alphabet ''<math>\Sigma</math>'' of size ''<math>k</math>''. Otherwise, ''<math>p</math>'' is ''<math>k</math>''-unavoidable, which means ''<math>p</math>'' is unavoidable on every alphabet of size ''<math>k</math>''.<ref name=":5">{{Cite book\|url=https://books.google.com/books?id=3w9eR3u8GN4C&q=Combinatorics+on+words.+Christoffel+words+and+repetitions+in+words+2009\|title=Combinatorics on Words: Christoffel Words and Repetitions in Words\|publisher=American Mathematical Soc.\|isbn=978-0-8218-7325-0\|pages=127\|language=en}}</ref>

	If pattern <math>p</math> is '''<math>k</math>'''-avoidable, then <math>p</math> is '''<math>g</math>'''-avoidable for all '''''<math>g\geq k</math>'''''.		If pattern <math>p</math> is '''<math>k</math>'''-avoidable, then <math>p</math> is '''<math>g</math>'''-avoidable for all '''''<math>g\geq k</math>'''''.
Line 54:		Line 54:
	All Zimin words are unavoidable.<ref name=":0" />		All Zimin words are unavoidable.<ref name=":0" />

	A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|issn=0025-5734}}</ref>		A word ''<math>w</math>'' is unavoidable if and only if it is a factor of a Zimin word.<ref name=":0">{{Cite journal\|last=Zimin\|first=A. I.\|title=Blocking Sets of Terms\|date=1984\|journal=Mathematics of the USSR-Sbornik\|language=en\|volume=47\|issue=2\|pages=353–364\|doi=10.1070/SM1984v047n02ABEH002647\|bibcode=1984SbMat..47..353Z\|issn=0025-5734}}</ref>

	Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{cite book\|last1=Joshua\|first1=Cooper\|url=https://archive.org/details/arxiv-1409.3080\|title=Bounds on Zimin Word Avoidance\|last2=Rorabaugh\|first2=Danny\|year=2013\|arxiv=1409.3080\|bibcode=2014arXiv1409.3080C}}</ref>		Given a finite alphabet <math>\Sigma</math>, let <math>f(n,\|\Sigma\|)</math> represent the smallest <math>m\in\Zeta^+</math> such that <math>w</math> matches <math>Z_n</math> for all <math>w\in \Sigma^m</math>. We have following properties:<ref>{{cite book\|last1=Joshua\|first1=Cooper\|url=https://archive.org/details/arxiv-1409.3080\|title=Bounds on Zimin Word Avoidance\|last2=Rorabaugh\|first2=Danny\|year=2013\|publisher=arXiv.org\|arxiv=1409.3080\|bibcode=2014arXiv1409.3080C}}</ref>

	*<math>f(1,q)=1</math>		*<math>f(1,q)=1</math>
Line 81:		Line 81:

	=== Locked ===		=== Locked ===
	A word ''<math>w</math>'' is said to be locked if ''<math>w</math>'' has no free letter; hence ''<math>w</math>'' can not be reduced.<ref name=":3">{{Cite journal\|last1=Baker\|first1=Kirby A.\|last2=McNulty\|first2=George F.\|last3=Taylor\|first3=Walter\|date=1989-12-18\|title=Growth problems for avoidable words~~\|url=https://dx.doi.org/10.1016%2F0304-3975%2889%2990071-6~~\|journal=Theoretical Computer Science\|language=en\|volume=69\|issue=3\|pages=319–345\|doi=10.1016/0304-3975(89)90071-6\|issn=0304-3975\|doi-access=free}}</ref>		A word ''<math>w</math>'' is said to be locked if ''<math>w</math>'' has no free letter; hence ''<math>w</math>'' can not be reduced.<ref name=":3">{{Cite journal\|last1=Baker\|first1=Kirby A.\|last2=McNulty\|first2=George F.\|last3=Taylor\|first3=Walter\|date=1989-12-18\|title=Growth problems for avoidable words\|journal=Theoretical Computer Science\|language=en\|volume=69\|issue=3\|pages=319–345\|doi=10.1016/0304-3975(89)90071-6\|issn=0304-3975\|doi-access=free}}</ref>

	=== Transitivity ===		=== Transitivity ===
Line 89:		Line 89:
	A pattern ''<math>p</math>'' is unavoidable if and only if ''<math>p</math>'' reduces to a word of length one; hence ''<math>\exist w</math>'' such that ''<math>\|w\|=1</math>'' and ''<math>p\stackrel{*}{\rightarrow}w</math>''.<ref>{{Cite journal\|last1=Bean\|first1=Dwight R.\|last2=Ehrenfeucht\|first2=Andrzej\|last3=McNulty\|first3=George F.\|date=1979\|title=Avoidable patterns in strings of symbols.\|url=https://projecteuclid.org/euclid.pjm/1102783913\|journal=Pacific Journal of Mathematics\|language=en\|volume=85\|issue=2\|pages=261–294\|doi=10.2140/pjm.1979.85.261\|issn=0030-8730\|doi-access=free}}</ref><ref name=":0" />		A pattern ''<math>p</math>'' is unavoidable if and only if ''<math>p</math>'' reduces to a word of length one; hence ''<math>\exist w</math>'' such that ''<math>\|w\|=1</math>'' and ''<math>p\stackrel{*}{\rightarrow}w</math>''.<ref>{{Cite journal\|last1=Bean\|first1=Dwight R.\|last2=Ehrenfeucht\|first2=Andrzej\|last3=McNulty\|first3=George F.\|date=1979\|title=Avoidable patterns in strings of symbols.\|url=https://projecteuclid.org/euclid.pjm/1102783913\|journal=Pacific Journal of Mathematics\|language=en\|volume=85\|issue=2\|pages=261–294\|doi=10.2140/pjm.1979.85.261\|issn=0030-8730\|doi-access=free}}</ref><ref name=":0" />

	== Graph pattern avoidance<ref name=":4">{{Cite journal\|last=Grytczuk\|first=Jarosław\|date=2007-05-28\|title=Pattern avoidance on graphs~~\|url=http://www.sciencedirect.com/science/article/pii/S0012365X06007291~~\|journal=Discrete Mathematics\|series=The Fourth Caracow Conference on Graph Theory\|language=en\|volume=307\|issue=11\|pages=1341–1346\|doi=10.1016/j.disc.2005.11.071\|issn=0012-365X\|doi-access=free}}</ref>==		== Graph pattern avoidance<ref name=":4">{{Cite journal\|last=Grytczuk\|first=Jarosław\|date=2007-05-28\|title=Pattern avoidance on graphs\|journal=Discrete Mathematics\|series=The Fourth Caracow Conference on Graph Theory\|language=en\|volume=307\|issue=11\|pages=1341–1346\|doi=10.1016/j.disc.2005.11.071\|issn=0012-365X\|doi-access=free}}</ref>==

	=== Avoidance / Matching on a specific graph ===		=== Avoidance / Matching on a specific graph ===
Line 123:		Line 123:

	* The [[Thue–Morse sequence]] is cube-free and overlap-free; hence it avoids the patterns ''<math>xxx</math>'' and ''<math>xyxyx</math>''.<ref name=":5" />		* The [[Thue–Morse sequence]] is cube-free and overlap-free; hence it avoids the patterns ''<math>xxx</math>'' and ''<math>xyxyx</math>''.<ref name=":5" />
	*A [[square-free word]] is one avoiding the pattern ''<math>xx</math>''. The word over the alphabet <math>\{0,\pm1\}</math> obtained by taking the [[first difference]] of the Thue–Morse sequence is an example of an infinite square-free word.<ref>{{Cite book\|url=https://books.google.com/books?id=3w9eR3u8GN4C&~~printsec=frontcover&dq~~=Combinatorics+on+words.+Christoffel+words+and+repetitions+in+words+2009~~#q=Combinatorics%20on%20words.%20Christoffel%20words%20and%20repetitions%20in%20words%202009~~\|title=Combinatorics on Words: Christoffel Words and Repetitions in Words\|publisher=American Mathematical Soc.\|isbn=978-0-8218-7325-0\|pages=97\|language=en}}</ref><ref>{{Cite book\|last=Fogg\|first=N. Pytheas\|url=https://books.google.com/books?id=qBIsuwEACAAJ&dq=Substitutions+in+dynamics,+arithmetics+and+combinatorics.\|title=Substitutions in Dynamics, Arithmetics and Combinatorics\|date=2002-09-23\|publisher=Springer Science & Business Media\|isbn=978-3-540-44141-0\|pages=104\|language=en}}</ref>		*A [[square-free word]] is one avoiding the pattern ''<math>xx</math>''. The word over the alphabet <math>\{0,\pm1\}</math> obtained by taking the [[first difference]] of the Thue–Morse sequence is an example of an infinite square-free word.<ref>{{Cite book\|url=https://books.google.com/books?id=3w9eR3u8GN4C&q=Combinatorics+on+words.+Christoffel+words+and+repetitions+in+words+2009\|title=Combinatorics on Words: Christoffel Words and Repetitions in Words\|publisher=American Mathematical Soc.\|isbn=978-0-8218-7325-0\|pages=97\|language=en}}</ref><ref>{{Cite book\|last=Fogg\|first=N. Pytheas\|url=https://books.google.com/books?id=qBIsuwEACAAJ&q=Substitutions+in+dynamics,+arithmetics+and+combinatorics.\|title=Substitutions in Dynamics, Arithmetics and Combinatorics\|date=2002-09-23\|publisher=Springer Science & Business Media\|isbn=978-3-540-44141-0\|pages=104\|language=en}}</ref>
	* The patterns ''<math>x</math>'' and ''<math>xyx</math>'' are unavoidable on any alphabet, since they are factors of the Zimin words.<ref>{{Cite book\|last1=Allouche\|first1=Jean-Paul\|url=https://books.google.com/books?id=2ZsSUStt96sC~~&pg=PR13~~&dq=Automatic+Sequences:+Theory,+Applications,+Generalizations#q=~~Automatic%20Sequences:%20Theory,%20Applications,%20Generalizations~~\|title=Automatic Sequences: Theory, Applications, Generalizations\|last2=Shallit\|first2=Jeffrey\|last3=Shallit\|first3=Professor Jeffrey\|date=2003-07-21\|publisher=Cambridge University Press\|isbn=978-0-521-82332-6\|pages=24\|language=en}}</ref><ref name="Lothaire2001" />		* The patterns ''<math>x</math>'' and ''<math>xyx</math>'' are unavoidable on any alphabet, since they are factors of the Zimin words.<ref>{{Cite book\|last1=Allouche\|first1=Jean-Paul\|url=https://books.google.com/books?id=2ZsSUStt96sC&dq=Automatic+Sequences%3A+Theory%2C+Applications%2C+Generalizations&pg=PR13\|title=Automatic Sequences: Theory, Applications, Generalizations\|last2=Shallit\|first2=Jeffrey\|last3=Shallit\|first3=Professor Jeffrey\|date=2003-07-21\|publisher=Cambridge University Press\|isbn=978-0-521-82332-6\|pages=24\|language=en}}</ref><ref name="Lothaire2001" />
	* The power patterns ''<math>x^n</math>'' for ''<math>n\geq 3 </math>'' are 2-avoidable.<ref name="Lothaire2001" />		* The power patterns ''<math>x^n</math>'' for ''<math>n\geq 3 </math>'' are 2-avoidable.<ref name="Lothaire2001" />
	*All binary patterns can be divided into three categories:<ref name="Lothaire2001">{{cite book\|last1=Lothaire\|first1=M.\|url=https://archive.org/details/algebraiccombina0000loth\|url-access=registration\|title=Algebraic Combinatorics on Words\|publisher=Cambridge University Press\|year=2002}}</ref>		*All binary patterns can be divided into three categories:<ref name="Lothaire2001">{{cite book\|last1=Lothaire\|first1=M.\|url=https://archive.org/details/algebraiccombina0000loth\|url-access=registration\|title=Algebraic Combinatorics on Words\|publisher=Cambridge University Press\|year=2002\|isbn=9780521812207}}</ref>
	**<math>\varepsilon,x,xyx</math> are unavoidable.		**<math>\varepsilon,x,xyx</math> are unavoidable.
	**<math>xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy</math> have avoidability index of 3.		**<math>xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy</math> have avoidability index of 3.