Avoiding squares over words with lists of size three amongst four symbols
HTML articles powered by AMS MathViewer
- by Matthieu Rosenfeld;
- Math. Comp. 91 (2022), 2489-2500
- DOI: https://doi.org/10.1090/mcom/3732
- Published electronically: June 8, 2022
- HTML | PDF | Request permission
Abstract:
In 2007, Grytczuk conjectured that for any sequence $(\ell _i)_{i\ge 1}$ of alphabets of size $3$ there exists a square-free infinite word $w$ such that for all $i$, the $i$-th letter of $w$ belongs to $\ell _i$. The result of Thue from 1906 implies that there is an infinite square-free word if all the $\ell _i$ are identical. On the other hand, Grytczuk, Przybyło and Zhu showed in 2011 that it also holds if the $\ell _i$ are of size $4$ instead of $3$.
In this article, we first show that if the lists are of size $4$, the number of square-free words is at least $2.45^n$ (the previous similar bound was $2^n$). We then show our main result: we can construct such a square-free word if the lists are subsets of size $3$ of the same alphabet of size $4$. Our proof also implies that there are at least $1.25^n$ square-free words of length $n$ for any such list assignment. This proof relies on the existence of a set of coefficients verified with a computer. We suspect that the full conjecture could be resolved by this method with a much more powerful computer (but we might need to wait a few decades for such a computer to be available).
References
- Noga Alon, Jarosław Grytczuk, Mariusz Hałuszczak, and Oliver Riordan, Nonrepetitive colorings of graphs, Random Structures Algorithms 21 (2002), no. 3-4, 336–346. Random structures and algorithms (Poznan, 2001). MR 1945373, DOI 10.1002/rsa.10057
- Vida Dujmović, Gwenaël Joret, Jakub Kozik, and David R. Wood, Nonrepetitive colouring via entropy compression, Combinatorica 36 (2016), no. 6, 661–686. MR 3597586, DOI 10.1007/s00493-015-3070-6
- Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, and David R. Wood, Planar graphs have bounded nonrepetitive chromatic number, Adv. Comb. (2020), Paper No. 5, 11. MR 4125346
- D. Gonçalves, M. Montassier, and A. Pinlou, Entropy compression method applied to graph colorings, arXiv e-prints, arXiv:1406.4380, 2014.
- Adam Gągol, Gwenaël Joret, Jakub Kozik, and Piotr Micek, Pathwidth and nonrepetitive list coloring, Electron. J. Combin. 23 (2016), no. 4, Paper 4.40, 19. MR 3604798, DOI 10.37236/5855
- Jarosław Grytczuk, Nonrepetitive colorings of graphs—a survey, Int. J. Math. Math. Sci. , posted on (2007), Art. ID 74639, 10. MR 2272338, DOI 10.1155/2007/74639
- Sebastian Czerwiński and Jarek Grytczuk, Nonrepetitive colorings of graphs, 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Electron. Notes Discrete Math., vol. 28, Elsevier Sci. B. V., Amsterdam, 2007, pp. 453–459. MR 2324051, DOI 10.1016/j.endm.2007.01.063
- Jarosław Grytczuk, Jakub Przybyło, and Xuding Zhu, Nonrepetitive list colourings of paths, Random Structures Algorithms 38 (2011), no. 1-2, 162–173. MR 2768888, DOI 10.1002/rsa.20347
- Jarosław Grytczuk, Jakub Kozik, and Piotr Micek, New approach to nonrepetitive sequences, Random Structures Algorithms 42 (2013), no. 2, 214–225. MR 3019398, DOI 10.1002/rsa.20411
- Jochen Harant and Stanislav Jendroľ, Nonrepetitive vertex colorings of graphs, Discrete Math. 312 (2012), no. 2, 374–380. MR 2852595, DOI 10.1016/j.disc.2011.09.027
- R. M. Kolpakov, On a bound for the number of repetition-free words, Diskretn. Anal. Issled. Oper. Ser. 1 13 (2006), no. 2, 21–37 (Russian, with Russian summary); English transl., J. Appl. Ind. Math. 1 (2007), no. 4, 453–462. MR 2289336, DOI 10.1134/S1990478907040084
- M. Lothaire, Combinatorics on words, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1997. With a foreword by Roger Lyndon and a preface by Dominique Perrin; Corrected reprint of the 1983 original, with a new preface by Perrin. MR 1475463, DOI 10.1017/CBO9780511566097
- Matthieu Rosenfeld, Another approach to non-repetitive colorings of graphs of bounded degree, Electron. J. Combin. 27 (2020), no. 3, Paper No. 3.43, 16. MR 4245156, DOI 10.37236/9667
- Arseny M. Shur, Two-sided bounds for the growth rates of power-free languages, Developments in language theory, Lecture Notes in Comput. Sci., vol. 5583, Springer, Berlin, 2009, pp. 466–477. MR 2544724, DOI 10.1007/978-3-642-02737-6_{3}8
- Arseny M. Shur, Growth rates of complexity of power-free languages, Theoret. Comput. Sci. 411 (2010), no. 34-36, 3209–3223. MR 2676864, DOI 10.1016/j.tcs.2010.05.017
- E. Škrabuľáková, The Thue choice number versus the Thue chromatic number of graphs, arXiv e-prints, arXiv:1508.02559, August 2015.
- A. Thue, Über unendliche Zeichenreihen, ’Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 7 (1906), 1–22.
- Olav Njåstad, Axel Thue: “Über die Auflösbarkeit einiger unbestimmten Gleichungen”, Skr. K. Nor. Vidensk. Selsk. 4 (2011), 103–110 (Norwegian, with English and Norwegian summaries). MR 2994977
- I. M. Wanless and D. R. Wood, A general framework for hypergraph colouring, arXiv e-prints, arXiv:2008.00775, 2020.
- David R. Wood, Nonrepetitive graph colouring, Electron. J. Combin. DS24 (2021), no. Dynamic Surveys, 78. MR 4336226, DOI 10.37236/9777
- Huanhua Zhao and Xuding Zhu, $(2+\epsilon )$-nonrepetitive list colouring of paths, Graphs Combin. 32 (2016), no. 4, 1635–1640. MR 3514989, DOI 10.1007/s00373-015-1652-0
Bibliographic Information
- Matthieu Rosenfeld
- Affiliation: LIRMM, CNRS, Université de Montpellier
- MR Author ID: 1169147
- ORCID: 0000-0001-5467-5407
- Email: matthieu.rosenfeld@gmail.com
- Received by editor(s): May 26, 2021
- Received by editor(s) in revised form: November 17, 2021, and January 11, 2022
- Published electronically: June 8, 2022
- Additional Notes: Supported by the ANR project CoCoGro (ANR-16-CE40-0005)
- © Copyright 2022 American Mathematical Society
- Journal: Math. Comp. 91 (2022), 2489-2500
- MSC (2020): Primary 68R15, 05-08
- DOI: https://doi.org/10.1090/mcom/3732
- MathSciNet review: 4451470