Improved bounds on the length of maximal abelian square-free words
The electronic journal of combinatorics, Tome 11 (2004) no. 1
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$.
@article{10_37236_1770,
author = {Evan M. Bullock},
title = {Improved bounds on the length of maximal abelian square-free words},
journal = {The electronic journal of combinatorics},
year = {2004},
volume = {11},
number = {1},
doi = {10.37236/1770},
zbl = {1104.68088},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1770/}
}
Evan M. Bullock. Improved bounds on the length of maximal abelian square-free words. The electronic journal of combinatorics, Tome 11 (2004) no. 1. doi: 10.37236/1770
Cité par Sources :