Lengths of extremal square-free ternary words

01/31/2020
by   Lucas Mol, et al.
0

A square-free word w over a fixed alphabet Σ is extremal if every word obtained from w by inserting a single letter from Σ (at any position) contains a square. Grytczuk et al. recently introduced the concept of extremal square-free word, and demonstrated that there are arbitrarily long extremal square-free ternary words. We find all lengths which admit an extremal square-free ternary word. In particular, we show that there is an extremal square-free ternary word of every sufficiently large length. We also solve the analogous problem for circular words.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset