Bounds on Zimin Word Avoidance

Abstract

How long can a word be that avoids the unavoidable? Word $W$ encounters word $V$ provided there is a homomorphism $\varphi$ defined by mapping letters to nonempty words such that $\varphi (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