Discrete Mathematics & Theoretical Computer Science 
In 1961, Erdos asked whether or not there exist words of arbitrary length over a fixed finite alphabet that avoid patterns of the form XX' where X' is a permutation of X (called abelian squares). This problem has since been solved in the affirmative in a series of papers from 1968 to 1992. Much less is known in the case of abelian kth powers, i.e., words of the form X1X2 ... Xk where Xi is a permutation of X1 for 2 <= i <= k. In this paper, we consider crucial words for abelian kth powers, i. e., finite words that avoid abelian kth powers, but which cannot be extended to the right by any letter of their own alphabets without creating an abelian kth power. More specifically, we consider the problem of determining the minimal length of a crucial word avoiding abelian kth powers. This problem has already been solved for abelian squares by Evdokimov and Kitaev (2004), who showed that a minimal crucial word over an nletter alphabet A(n) = \1, 2, ..., n\ avoiding abelian squares has length 4n  7 for n >= 3. Extending this result, we prove that a minimal crucial word over A(n) avoiding abelian cubes has length 9n  13 for n >= 5, and it has length 2, 5, 11, and 20 for n = 1, 2, 3, and 4, respectively. Moreover, for n >= 4 and k >= 2, we give a construction of length k(2) (n  1)  k  1 of a crucial word over A(n) avoiding abelian kth powers. This construction gives the minimal length for k = 2 and k = 3. For k >= 4 and n >= 5, we provide a lower bound for the length of crucial words over A(n) avoiding abelian kth powers.
Source : ScholeXplorer
IsRelatedTo ARXIV math/0205217 Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.jcta.2003.12.003 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.math/0205217
