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.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2020006
Keywords: 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},
year = {2020},
publisher = {EDP Sciences},
volume = {54},
doi = {10.1051/ita/2020006},
mrnumber = {4169251},
zbl = {1508.68272},
language = {en},
url = {https://www.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 - https://www.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 https://www.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
[1] and , There exist binary circular 5∕2+ power free words of every length. Electron. J. Combin. 11 (2004) #R10. | MR | Zbl | DOI
[2] and , Attainable lengths for circular binary words avoiding k powers. Bull. Belg. Math. Soc. Simon Stevin 12 (2005) 525–534. | MR | Zbl | DOI
[3] , , and , Nonrepetitive colorings of graphs. Random Struct. Algorithms 21 (2002) 336–346. | MR | Zbl | DOI
[4] , Axel Thue’s Papers on Repetitions in Words: A Translation. Publications du LaCIM, Université du Québec à Montréal, vol. 20 (1995).
[5] , On Dejean’s conjecture over large alphabets. Theoret. Comput. Sci. 385 (2007) 137–151. | MR | Zbl | DOI
[6] and , Toeplitz words, generalized periodicity and periodically iterated morphisms. European J. Combin. 18 (1997) 497–510. | MR | Zbl | DOI
[7] and , A proof of Dejean’s conjecture. Math. Comp. 80 (2011) 1063–1070. | MR | Zbl | DOI
[8] , , Dejean’s conjecture holds for n ≥ 27. RAIRO: ITA 43 (2009) 775–778. | MR | Zbl | Numdam
[9] , , Dejean’s conjecture holds for n ≥ 30. Theoret. Comput. Sci. 410 (2009) 2885–2888. | MR | Zbl | DOI
[10] , and , Circular repetition thresholds on some small alphabets: last cases of Gorbunova’s conjecture. Electron. J. Combin. 26 (2018) #P2.31. | MR | Zbl | DOI
[11] , and , 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] , There are ternary circular square-free words of length n for n ≥ 18. Electron. J. Combin. 9 (2002) #N10. | MR | Zbl | DOI
[13] , Sur un théorème de Thue. J. Combin. Theory Ser. A 13 (1972) 90–99. | MR | Zbl | DOI
[14] , , , and , Planar graphs have bounded nonrepetitive chromatic number, Adv. Comb. 5 (2020) 11. | MR | Zbl
[15] , Repetition threshold for circular words. Electron. J. Combin. 19 (2012) #P11. | MR | Zbl | DOI
[16] , Algebraic Combinatorics on Words, Cambridge University Press (2002). | Zbl | MR | DOI
[17] , and , On repetition thresholds of caterpillars and trees of bounded degree. Electron. J. Combin. 25 (2018) #P1.61. | MR | Zbl | DOI
[18] and , Dejean’s conjecture and Sturmian words. European J. Combin. 28 (2007) 876–890. | MR | Zbl | DOI
[19] , Proof of Dejean’s conjecture for alphabets with 5, 6, 7, 8, 9, 10, and 11 letters. Theoret. Comput. Sci. 95 (1992) 187–205. | MR | Zbl | DOI
[20] , Automatic theorem proving in Walnut. Preprint (2016). | arXiv
[21] and , Repetition thresholds for subdivided graphs and trees. RAIRO: ITA 46 (2012) 123–130. | MR | Zbl | Numdam
[22] , A propos d’une conjecture de F. Dejean sur les répétitions dans les mots. Discrete Appl. Math. 7 (1984) 297–311. | MR | Zbl | DOI
[23] , Last cases of Dejean’s conjecture. Theoret. Comput. Sci. 412 (2011) 3010–3018. | MR | Zbl | DOI
[24] , On the existence of minimal β-powers. Internat. J. Found. Comput. Sci. 22 (2011) 1683–1696. | MR | Zbl | DOI
Cité par Sources :
