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 (149kB)
    Link to Published Version: http://dx.doi.org/10.1016/j.dam.2009.11.010
    *Open access, 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