OFFSET
1,1
COMMENTS
A ternary word is one over a three-letter alphabet, such as {0,1,2}. Such a word is called "squarefree" if it contains no sub-block of the form XX, where X is a nonempty contiguous block. A word x is extremal if it is squarefree, but every possible insertion of a single letter, that is, every word of the form x' a x'' with x = x' x'', a in {0,1,2}, is not squarefree.
The Grytczuk paper proves there are arbitrarily long extremal words.
REFERENCES
Jaroslaw Grytczuk, Hubert Kordulewski, Artur Niewiadomski, Extremal Square-Free Words, Electronic J. Combinatorics, 27 (1), 2020, #1.48.
LINKS
J. Grytczuk, H. Kordulewski, and A. Niewadomski, Extremal square-free words, arxiv preprint arXiv:1910.06226v1 [math.CO], October 14 2019.
EXAMPLE
The smallest extremal word is of length 25, which is 0120102120121012010212012 and is unique up to renaming of the letters. The next smallest are of length 41, and there are two (up to renaming), namely 01021012021020121021201021012021020121021 and 02102012102120102101202102012102120102101. The next is of length 48, and is unique (up to renaming): 010212012102010212012101202120121020102120121020. The next is of length 50 and is unique (up to renaming): 01021201021012021020121012021201021012021020121020.
The next smallest are of length 63, and there are two (up to renaming): 010210120210201021202102012102120102101202102010212021020121021, 012010212012101202120121020120210120102120121012021201210201202. - Michael S. Branicky, May 06 2022
For lengths 25, 41, 48, 50, and 63, there is a unique extremal word up to both renaming and reversal. - Pontus von Brömssen, May 07 2022
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Oct 20 2019
EXTENSIONS
a(5) from Michael S. Branicky, May 06 2022
STATUS
approved