Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Tower-type bounds for unavoidable patterns in words

Authors: David Conlon, Jacob Fox and Benny Sudakov
Journal: Trans. Amer. Math. Soc. 372 (2019), 6213-6229
MSC (2010): Primary 05D10, 68R15; Secondary 20M05
Published electronically: May 30, 2019
MathSciNet review: 4024519
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 nontrivial case, we determine $ f(n,q)$ up to a constant factor, showing that $ f(3,q) = \Theta (2^q q!)$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05D10, 68R15, 20M05

Retrieve articles in all journals with MSC (2010): 05D10, 68R15, 20M05

Additional Information

David Conlon
Affiliation: Mathematical Institute, Oxford OX2 6GG, United Kingdom

Jacob Fox
Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305

Benny Sudakov
Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland

Received by editor(s): December 17, 2017
Received by editor(s) in revised form: November 4, 2018
Published electronically: May 30, 2019
Additional Notes: 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.
Article copyright: © Copyright 2019 American Mathematical Society