The weak circular repetition threshold over large alphabets
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 6.

The repetition threshold for words on n letters, denoted RT(n), is the infimum of the set of all r such that there are arbitrarily long r-free words over n letters. A repetition threshold for circular words on n letters can be defined in three natural ways, which gives rise to the weak, intermediate, and strong circular repetition thresholds for n letters, denoted CRTW(n), CRTI(n), and CRTS(n), respectively. Currie and the present authors conjectured that CRTI(n) = CRTW(n) = RT(n) for all n ≥ 4. We prove that CRTW(n) = RT(n) for all n ≥ 45, which confirms a weak version of this conjecture for all but finitely many values of n.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2020006
Classification : 68R15, 05C15
Mots-clés : Repetition threshold, circular repetition threshold, repetition threshold for graphs, Dejean’s conjecture, Dejean’s theorem, nonrepetitive colouring 
@article{ITA_2020__54_1_A6_0,
     author = {Mol, Lucas and Rampersad, Narad},
     title = {The weak circular repetition threshold over large alphabets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {54},
     year = {2020},
     doi = {10.1051/ita/2020006},
     mrnumber = {4169251},
     zbl = {1508.68272},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2020006/}
}
TY  - JOUR
AU  - Mol, Lucas
AU  - Rampersad, Narad
TI  - The weak circular repetition threshold over large alphabets
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2020
VL  - 54
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2020006/
DO  - 10.1051/ita/2020006
LA  - en
ID  - ITA_2020__54_1_A6_0
ER  - 
%0 Journal Article
%A Mol, Lucas
%A Rampersad, Narad
%T The weak circular repetition threshold over large alphabets
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2020
%V 54
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2020006/
%R 10.1051/ita/2020006
%G en
%F ITA_2020__54_1_A6_0
Mol, Lucas; Rampersad, Narad. The weak circular repetition threshold over large alphabets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 6. doi : 10.1051/ita/2020006. http://archive.numdam.org/articles/10.1051/ita/2020006/

[1] A. Aberkane and J. D. Currie, There exist binary circular 5∕2+ power free words of every length. Electron. J. Combin. 11 (2004) #R10. | DOI | MR | Zbl

[2] A. Aberkane and J. D. Currie, Attainable lengths for circular binary words avoiding k powers. Bull. Belg. Math. Soc. Simon Stevin 12 (2005) 525–534. | DOI | MR | Zbl

[3] N. Alon, J. Grytczuk, M. Hałuszczak and O. Riordan, Nonrepetitive colorings of graphs. Random Struct. Algorithms 21 (2002) 336–346. | DOI | MR | Zbl

[4] J. Berstel, Axel Thue’s Papers on Repetitions in Words: A Translation. Publications du LaCIM, Université du Québec à Montréal, vol. 20 (1995).

[5] A. Carpi, On Dejean’s conjecture over large alphabets. Theoret. Comput. Sci. 385 (2007) 137–151. | DOI | MR | Zbl

[6] J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. European J. Combin. 18 (1997) 497–510. | DOI | MR | Zbl

[7] J. D. Currie and N. Rampersad, A proof of Dejean’s conjecture. Math. Comp. 80 (2011) 1063–1070. | DOI | MR | Zbl

[8] J. D. Currie, N. Rampersad, Dejean’s conjecture holds for n ≥ 27. RAIRO: ITA 43 (2009) 775–778. | Numdam | MR | Zbl

[9] J. D. Currie, N. Rampersad, Dejean’s conjecture holds for n ≥ 30. Theoret. Comput. Sci. 410 (2009) 2885–2888. | DOI | MR | Zbl

[10] J. D. Currie, L. Mol and N. Rampersad, Circular repetition thresholds on some small alphabets: last cases of Gorbunova’s conjecture. Electron. J. Combin. 26 (2018) #P2.31. | DOI | MR | Zbl

[11] J. D. Currie, L. Mol and N. Rampersad, The number of threshold words on n letters grows exponentially for every n ≥ 27. J. Integer Sequences 23 (2020) 20.3.1. | MR | Zbl

[12] J. D. Currie, There are ternary circular square-free words of length n for n ≥ 18. Electron. J. Combin. 9 (2002) #N10. | DOI | MR | Zbl

[13] F. Dejean, Sur un théorème de Thue. J. Combin. Theory Ser. A 13 (1972) 90–99. | DOI | MR | Zbl

[14] V. Dujmović, L. Esperet, G. Joret, B. Walczak and D. R. Wood, Planar graphs have bounded nonrepetitive chromatic number, Adv. Comb. 5 (2020) 11. | MR | Zbl

[15] I. A. Gorbunova, Repetition threshold for circular words. Electron. J. Combin. 19 (2012) #P11. | DOI | MR | Zbl

[16] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press (2002). | DOI | MR | Zbl

[17] B. Lužar, P. Ochem and A. Pinlou, On repetition thresholds of caterpillars and trees of bounded degree. Electron. J. Combin. 25 (2018) #P1.61. | DOI | MR | Zbl

[18] M. Mohammad-Noori and J. D. Currie, Dejean’s conjecture and Sturmian words. European J. Combin. 28 (2007) 876–890. | DOI | MR | Zbl

[19] J. Moulin-Ollagnier, Proof of Dejean’s conjecture for alphabets with 5, 6, 7, 8, 9, 10, and 11 letters. Theoret. Comput. Sci. 95 (1992) 187–205. | DOI | MR | Zbl

[20] H. Mousavi, Automatic theorem proving in Walnut. Preprint (2016). | arXiv

[21] P. Ochem and E. Vaslet, Repetition thresholds for subdivided graphs and trees. RAIRO: ITA 46 (2012) 123–130. | Numdam | MR | Zbl

[22] J. J. Pansiot, A propos d’une conjecture de F. Dejean sur les répétitions dans les mots. Discrete Appl. Math. 7 (1984) 297–311. | DOI | MR | Zbl

[23] M. Rao, Last cases of Dejean’s conjecture. Theoret. Comput. Sci. 412 (2011) 3010–3018. | DOI | MR | Zbl

[24] A. M. Shur, On the existence of minimal β-powers. Internat. J. Found. Comput. Sci. 22 (2011) 1683–1696. | DOI | MR | Zbl

Cité par Sources :