Bounds on Zimin Word Avoidance

الأصل · EN

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ₙ, defined by: Z₁ = x₁ and Zₙ₊₁ = Zₙ xₙ₊₁ Zₙ. Here we explore bounds on how long words can be and still avoid the unavoidable Zimin words.