Catalog Home Page

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.

[img]
PDF - Authors' Version
Download (153kB)
Free to read: http://dx.doi.org/10.1016/j.dam.2009.11.010
*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 Item Control Page

Downloads

Downloads per month over past year