Improved Bounds on the Length of Maximal Abelian Square-free Words

Evan M. Bullock

Abstract


A word is abelian square-free if it does not contain two adjacent subwords which are permutations of each other. Over an alphabet $\Sigma_k$ on $k$ letters, an abelian square-free word is maximal if it cannot be extended to the left or right by letters from $\Sigma_k$ and remain abelian square-free. Michael Korn proved that the length $\ell (k)$ of a shortest maximal abelian square-free word satisfies $4k-7\leq \ell(k)\leq 6k-10$ for $k\geq 6$. In this paper, we refine Korn's methods to show that $6k-29\leq \ell(k)\leq 6k-12$ for $k\geq 8$.


Full Text: PDF