# On shortest crucial words avoiding abelian powers

Avgustinovich, S., Glen, A., Halldórsson, B.V. and Kitaev, S. (2010) *On shortest crucial words avoiding abelian powers.* Discrete Applied Mathematics, 158 (6). pp. 605-607.

*No subscription required

## Abstract

Let k ≥ 2 be an integer. An abeliank th power is a word of the form X1 X2 ⋯ Xk where Xi is a permutation of X1 for 2 ≤ i ≤ k. A word W is said to be crucial with respect to abelian kth powers if W avoids abelian kth powers, but W x ends with an abelian kth power for any letter x occurring in W. Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on n letters avoiding abelian squares is 4 n - 7 for n ≥ 3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9 n - 13 for n ≥ 5. They have also conjectured that for any k ≥ 4 and sufficiently large n, the shortest length of a crucial word on n letters avoiding abelian kth powers, denoted by ℓk (n), is k2 n - (k2 + k + 1). This is currently the best known upper bound for ℓk (n), and the best known lower bound, provided in Glen et al., is 3 k n - (4 k + 1) for n ≥ 5 and k ≥ 4. In this note, we improve this lower bound by proving that for n ≥ 2 k - 1, ℓk (n) ≥ k2 n - (2 k3 - 3 k2 + k + 1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing n.

Publication Type: | Journal Article |
---|---|

Murdoch Affiliation: | School of Chemical and Mathematical Science |

Publisher: | Elsevier BV |

Copyright: | 2009 Elsevier B.V. |

URI: | http://researchrepository.murdoch.edu.au/id/eprint/3362 |

Item Control Page |

### Downloads

Downloads per month over past year