Tower-type bounds for unavoidable patterns in words
HTML articles powered by AMS MathViewer
- by David Conlon, Jacob Fox and Benny Sudakov PDF
- Trans. Amer. Math. Soc. 372 (2019), 6213-6229 Request permission
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
- Jean-Paul Allouche and Jeffrey Shallit, The ubiquitous Prouhet-Thue-Morse sequence, Sequences and their applications (Singapore, 1998) Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 1999, pp. 1–16. MR 1843077
- Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
- Dwight R. Bean, Andrzej Ehrenfeucht, and George F. McNulty, Avoidable patterns in strings of symbols, Pacific J. Math. 85 (1979), no. 2, 261–294. MR 574919
- Jean Berstel and Dominique Perrin, The origins of combinatorics on words, European J. Combin. 28 (2007), no. 3, 996–1022. MR 2300777, DOI 10.1016/j.ejc.2005.07.019
- Arnaud Carayol and Stefan Göller, On long words avoiding Zimin patterns, 34th Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 66, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. Art. No. 19, 13. MR 3655346
- Ronald J. Clark, The existence of a pattern which is 5-avoidable but 4-unavoidable, Internat. J. Algebra Comput. 16 (2006), no. 2, 351–367. MR 2228517, DOI 10.1142/S0218196706002950
- David Conlon, Jacob Fox, and Benny Sudakov, Recent developments in graph Ramsey theory, Surveys in combinatorics 2015, London Math. Soc. Lecture Note Ser., vol. 424, Cambridge Univ. Press, Cambridge, 2015, pp. 49–118. MR 3497267
- Joshua Cooper and Danny Rorabaugh, Bounds on Zimin word avoidance, Congr. Numer. 222 (2014), 87–95. MR 3328869
- Persi Diaconis and Ron Graham, Magical mathematics, Princeton University Press, Princeton, NJ, 2012. The mathematical ideas that animate great magic tricks; With a foreword by Martin Gardner. MR 2858033
- Harold Marston Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc. 22 (1921), no. 1, 84–100. MR 1501161, DOI 10.1090/S0002-9947-1921-1501161-8
- Wojciech Rytter and Arseny M. Shur, Searching for Zimin patterns, Theoret. Comput. Sci. 571 (2015), 50–57. MR 3303954, DOI 10.1016/j.tcs.2015.01.004
- Mark V. Sapir, Combinatorial algebra: syntax and semantics, Springer Monographs in Mathematics, Springer, Cham, 2014. With contributions by Victor S. Guba and Mikhail V. Volkov. MR 3243545, DOI 10.1007/978-3-319-08031-4
- A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I Mat.-Nat. Kl. 7 (1906), 1–22.
- A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I Mat.-Nat. Kl. 1 (1912) 1–67.
- A. I. Zimin, Blocking sets of terms, Mat. Sb. (N.S.) 119(161) (1982), no. 3, 363–375, 447 (Russian). MR 678833
Additional Information
- David Conlon
- Affiliation: Mathematical Institute, Oxford OX2 6GG, United Kingdom
- MR Author ID: 793461
- Email: david.conlon@maths.ox.ac.uk
- Jacob Fox
- Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305
- MR Author ID: 775407
- Email: jacobfox@stanford.edu
- Benny Sudakov
- Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland
- MR Author ID: 602546
- Email: benjamin.sudakov@math.ethz.ch
- 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. - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 372 (2019), 6213-6229
- MSC (2010): Primary 05D10, 68R15; Secondary 20M05
- DOI: https://doi.org/10.1090/tran/7751
- MathSciNet review: 4024519