Logo image
Back
On shortest crucial words avoiding abelian powers
Journal article   Open access   Peer reviewed

On shortest crucial words avoiding abelian powers

S. Avgustinovich, A. Glen, B.V. Halldórsson and S. Kitaev
Discrete Applied Mathematics, Vol.158(6), pp.605-607
2010
DOI: https://doi.org/10.1016/j.dam.2009.11.010
pdf
abelian_powers.pdfDownloadView
Author’s Version Open Access
url
Free to Read *No subscription requiredView

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.

Details

Metrics

243 File views/ downloads
82 Record Views
11 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
International collaboration
Citation topics
9 Mathematics
9.28 Pure Maths
9.28.534 Dynamical Systems
Web Of Science research areas
Mathematics, Applied
ESI research areas
Engineering
Logo image