Bounds on Zimin Word Avoidance
arXiv:1409.3080
Abstract
How long can a word be that avoids the unavoidable? Word $W$ encounters word $V$ provided there is a homomorphism $Ï$ defined by mapping letters to nonempty words such that $Ï(V)$ is a subword of $W$. Otherwise, $W$ is said to avoid $V$. If, on any arbitrary finite alphabet, there are finitely many words that avoid $V$, then we say $V$ is unavoidable. Zimin (1982) proved that every unavoidable word is encountered by some word $Z_n$, defined by: $Z_1 = x_1$ and $Z_{n+1} = Z_n x_{n+1} Z_n$. Here we explore bounds on how long words can be and still avoid the unavoidable Zimin words.
9 pages; presented 4 March 2014 at the 45th Southeastern International Conference on Combinatorics, Graph Theory, and Computing at Florida Atlantic University; accepted to appear in Congressus Numerantum