Extremal overlap-free and extremal \(\beta\)-free binary words (Q2215463)

A finite word having a given property, for example, avoiding a given power, is called extremal if it loses this property after adding to it any symbol of the alphabet anywhere in the middle. The notion of extremal square-free words has been recently introduced by \textit{J. Grytczuk} et al. [Electron. J. Comb. 27, No. 1, Research Paper P1.48, 9 p. (2020; Zbl 1435.05007)]; later, \textit{L. Mol} and \textit{N. Rampersad} [Contrib. Discrete Math. 16, No. 1, 8--19 (2021; Zbl 1467.68149)] proved that there exist extremal square-free ternary words of every sufficiently large length. In this paper, however, the authors show that the situation for binary overlap-free words is different: such words exist for all even lengths greater than or equal to \(20\), but also for very rare odd lengths related to powers of \(2\). Another result of the paper is the existence of arbitrarily long extremal \(\beta\)-power-free binary words for all \(\beta\) between \(2^+\) (which corresponds to overlap-freeness) and \(8/3\). The authors also conjecture that \(8/3\) can be the largest number with this property. Some of the results of the paper are obtained by automated computation and in particular with the help of the Walnut software.