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.
MSC (2010): Primary 05D10, 68R15; Secondary 20M05
DOI: https://doi.org/10.1090/tran/7751
Published electronically: May 30, 2019
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
Email: david.conlon@maths.ox.ac.uk

Jacob Fox
Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305
Email: jacobfox@stanford.edu

Benny Sudakov
Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland
Email: benjamin.sudakov@math.ethz.ch

DOI: https://doi.org/10.1090/tran/7751
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