Tower-type bounds for unavoidable patterns in words

Abstract

A word $w$ is said to contain the pattern $P$ if there is a way to substitute a nonempty word for each letter in $P$ so that the resulting word is a subword of $w$. Bean, Ehrenfeucht and McNulty and, independently, Zimin characterised the patterns $P$ which are unavoidable, in the sense that any sufficiently long word over a fixed alphabet contains $P$. Zimin's characterisation says that a pattern is unavoidable if and only if it is contained in a Zimin word, where the Zimin words are defined by $Z_1=x_1$ and $Z_n=Z_{n-1}{x}_n{Z}_{n-1}$. We study the quantitative aspects of this theorem, obtaining essentially tight tower-type bounds for the function $f(n,q)$, the least integer such that any word of length $f(n,q)$ over an alphabet of size $q$ contains $Z_n$. When $n=3$, the first non-trivial case, we determine $f(n,q)$ up to a constant factor, showing that $f(3,q)=\hat{I}˜(2^{q}q!)$.

17 pages