### Abstract

Language | English |
---|---|

Pages | 83-96 |

Number of pages | 14 |

Journal | Discrete Mathematics and Theoretical Computer Science |

Volume | 12 |

Issue number | 5 |

Publication status | Published - 2010 |

### Fingerprint

### Keywords

- abelian squares
- abelian k-th power
- crucial word

### Cite this

*Discrete Mathematics and Theoretical Computer Science*,

*12*(5), 83-96.

}

*Discrete Mathematics and Theoretical Computer Science*, vol. 12, no. 5, pp. 83-96.

**Crucial abelian k-power-free words.** / Glen, Amy; Halldorsson, Bjarni; Kitaev, Sergey.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Crucial abelian k-power-free words

AU - Glen, Amy

AU - Halldorsson, Bjarni

AU - Kitaev, Sergey

PY - 2010

Y1 - 2010

N2 - In 1961, Erdős 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 k-th 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 k-th powers, i.e., finite words that avoid abelian k-th powers, but which cannot be extended to the right by any letter of their own alphabets without creating an abelian k-th power. More specifically, we consider the problem of determining the minimal length of a crucial word avoiding abelian k-th powers. This problem has already been solved for abelian squares by Evdokimov and Kitaev (2004), who showed that a minimal crucial word over an n-letter alphabet An = {1,2,…, n} avoiding abelian squares has length 4n-7 for n≥3. Extending this result, we prove that a minimal crucial word over An 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 k2(n-1)-k-1 of a crucial word over An avoiding abelian k-th 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 An avoiding abelian k-th powers.

AB - In 1961, Erdős 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 k-th 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 k-th powers, i.e., finite words that avoid abelian k-th powers, but which cannot be extended to the right by any letter of their own alphabets without creating an abelian k-th power. More specifically, we consider the problem of determining the minimal length of a crucial word avoiding abelian k-th powers. This problem has already been solved for abelian squares by Evdokimov and Kitaev (2004), who showed that a minimal crucial word over an n-letter alphabet An = {1,2,…, n} avoiding abelian squares has length 4n-7 for n≥3. Extending this result, we prove that a minimal crucial word over An 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 k2(n-1)-k-1 of a crucial word over An avoiding abelian k-th 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 An avoiding abelian k-th powers.

KW - abelian squares

KW - abelian k-th power

KW - crucial word

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1330

M3 - Article

VL - 12

SP - 83

EP - 96

JO - Discrete Mathematics and Theoretical Computer Science

T2 - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

SN - 1365-8050

IS - 5

ER -