Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

On shortest crucial words avoiding abelian powers

Avgustinovich, Sergey and Glen, Amy and Halldorsson, Bjarni and Kitaev, Sergey (2010) On shortest crucial words avoiding abelian powers. Discrete Applied Mathematics, 158 (6). pp. 605-607. ISSN 0166-218X

Full text not available in this repository. Request a copy from the Strathclyde author

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.