Extremal Overlap-Free and Extremal $\beta$-Free Binary Words

Abstract

An overlap-free (or $\beta$-free) word $w$ over a fixed alphabet $\Sigma$ is extremal if every word obtained from $w$ by inserting a single letter from $\Sigma$ at any position contains an overlap (or a factor of exponent at least $\beta$, respectively). We find all lengths which admit an extremal overlap-free binary word. For every "extended" real number $\beta$ such that $2^+\leqslant\beta\leqslant 8/3$, we show that there are arbitrarily long extremal $\beta$-free binary words.