On shortest crucial words avoiding abelian powers

Sergey Avgustinovich, Amy Glen, Bjarni Halldorsson, Sergey Kitaev

Research output: Contribution to journalArticle

12 Citations (Scopus)

Abstract

Let k≥2k≥2 be an integer. An abelian kkth power is a word of the form X1X2⋯XkX1X2⋯Xk where XiXi is a permutation of X1X1 for 2≤i≤k2≤i≤k. A word WW is said to be crucial with respect to abelian kkth powers if WW avoids abelian kkth powers, but WxWx ends with an abelian kkth power for any letter xx occurring in WW.

Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on nn letters avoiding abelian squares is 4n−74n−7 for n≥3n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−139n−13 for n≥5n≥5. They have also conjectured that for any k≥4k≥4 and sufficiently large nn, the shortest length of a crucial word on nn letters avoiding abelian kkth powers, denoted by ℓk(n)ℓk(n), is k2n−(k2+k+1)k2n−(k2+k+1). This is currently the best known upper bound for ℓk(n)ℓk(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1)3kn−(4k+1) for n≥5n≥5 and k≥4k≥4. In this note, we improve this lower bound by proving that for n≥2k−1n≥2k−1, ℓk(n)≥k2n−(2k3−3k2+k+1)ℓk(n)≥k2n−(2k3−3k2+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing nn.
LanguageEnglish
Pages605-607
Number of pages3
JournalDiscrete Applied Mathematics
Volume158
Issue number6
DOIs
Publication statusPublished - 28 Mar 2010

Fingerprint

Lower bound
Constant term
Regular hexahedron
Permutation
Upper bound
Integer
Form

Keywords

  • pattern avoidance
  • abelian powers
  • crucial word

Cite this

Avgustinovich, Sergey ; Glen, Amy ; Halldorsson, Bjarni ; Kitaev, Sergey. / On shortest crucial words avoiding abelian powers. In: Discrete Applied Mathematics. 2010 ; Vol. 158, No. 6. pp. 605-607.
@article{96a7e3e7b68a43cead7717600fa19216,
title = "On shortest crucial words avoiding abelian powers",
abstract = "Let k≥2k≥2 be an integer. An abelian kkth power is a word of the form X1X2⋯XkX1X2⋯Xk where XiXi is a permutation of X1X1 for 2≤i≤k2≤i≤k. A word WW is said to be crucial with respect to abelian kkth powers if WW avoids abelian kkth powers, but WxWx ends with an abelian kkth power for any letter xx occurring in WW.Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on nn letters avoiding abelian squares is 4n−74n−7 for n≥3n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−139n−13 for n≥5n≥5. They have also conjectured that for any k≥4k≥4 and sufficiently large nn, the shortest length of a crucial word on nn letters avoiding abelian kkth powers, denoted by ℓk(n)ℓk(n), is k2n−(k2+k+1)k2n−(k2+k+1). This is currently the best known upper bound for ℓk(n)ℓk(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1)3kn−(4k+1) for n≥5n≥5 and k≥4k≥4. In this note, we improve this lower bound by proving that for n≥2k−1n≥2k−1, ℓk(n)≥k2n−(2k3−3k2+k+1)ℓk(n)≥k2n−(2k3−3k2+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing nn.",
keywords = "pattern avoidance, abelian powers, crucial word",
author = "Sergey Avgustinovich and Amy Glen and Bjarni Halldorsson and Sergey Kitaev",
year = "2010",
month = "3",
day = "28",
doi = "10.1016/j.dam.2009.11.010",
language = "English",
volume = "158",
pages = "605--607",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
number = "6",

}

On shortest crucial words avoiding abelian powers. / Avgustinovich, Sergey; Glen, Amy; Halldorsson, Bjarni; Kitaev, Sergey.

In: Discrete Applied Mathematics, Vol. 158, No. 6, 28.03.2010, p. 605-607.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On shortest crucial words avoiding abelian powers

AU - Avgustinovich, Sergey

AU - Glen, Amy

AU - Halldorsson, Bjarni

AU - Kitaev, Sergey

PY - 2010/3/28

Y1 - 2010/3/28

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

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

KW - pattern avoidance

KW - abelian powers

KW - crucial word

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/AGHK.pdf

U2 - 10.1016/j.dam.2009.11.010

DO - 10.1016/j.dam.2009.11.010

M3 - Article

VL - 158

SP - 605

EP - 607

JO - Discrete Applied Mathematics

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 6

ER -