|
| |
|
|
A309623
|
|
Numbers n for which there is an extremal ternary word of length n.
|
|
1
|
| |
|
|
|
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
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
