A word is square-free if it does not contain nonempty factors of the form $XX$. In 1906 Thue proved that there exist arbitrarily long square-free words over a $3$-letter alphabet. We consider a new type of square-free words with additional property. A square-free word is called extremal if it cannot be extended to a new square-free word by inserting a single letter at any position. We prove that there exist infinitely many square-free extremal words over a $3$-letter alphabet. Some parts of our construction relies on computer verifications. It is not known if there exist any extremal square-free words over a $4$-letter alphabet.
@article{10_37236_9264,
author = {Jaros{\l}aw Grytczuk and Hubert Kordulewski and Artur Niewiadomski},
title = {Extremal square-free words},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {1},
doi = {10.37236/9264},
zbl = {1435.05007},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9264/}
}
TY - JOUR
AU - Jarosław Grytczuk
AU - Hubert Kordulewski
AU - Artur Niewiadomski
TI - Extremal square-free words
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9264/
DO - 10.37236/9264
ID - 10_37236_9264
ER -
%0 Journal Article
%A Jarosław Grytczuk
%A Hubert Kordulewski
%A Artur Niewiadomski
%T Extremal square-free words
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9264/
%R 10.37236/9264
%F 10_37236_9264
Jarosław Grytczuk; Hubert Kordulewski; Artur Niewiadomski. Extremal square-free words. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/9264
