Tower-type bounds for unavoidable patterns in words

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...

وصف كامل

التفاصيل البيبلوغرافية
المؤلفون الرئيسيون: Conlon, D, Fox, J, Sudakov, B
التنسيق: Journal article
منشور في: American Mathematical Society 2019
الوصف
الملخص: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 Z1 = x1 and Zn = Zn−1xnZn−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 Zn. When n = 3, the first non-trivial case, we determine f(n, q) up to a constant factor, showing that f(3, q) = Θ(2q q!).