Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 30, 2019 | Submitted
Journal Article Open

Tower-type bounds for unavoidable patterns in words


A word ω 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 ω. 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 − 1x_(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 nontrivial case, we determine f(n, q) up to a constant factor, showing that f(3, q) = Θ(2_(q)q!).

Additional Information

© Copyright 2019 American Mathematical Society. Received by the editors December 17, 2017, and, in revised form, November 4, 2018. Article electronically published on May 30, 2019. The research of the first author was supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. The research of the second author was supported by a Packard Fellowship, by NSF Career Award DMS-1352121, and by an Alfred P. Sloan Fellowship. The research of the third author was supported in part by SNSF grant 200021-175573.

Attached Files

Submitted - 1704.03479.pdf


Files (211.8 kB)
Name Size Download all
211.8 kB Preview Download

Additional details

August 19, 2023
October 18, 2023