Observations and Problems on k-abelian avoidability

We introduce new avoidability problems for words by considering equivalence relations, k-abelian equivalences, which lie properly in between equality and commutative equality, i.e. abelian equality. For two k-abelian equivalent words the numbers of occurrences of different factors of length k coincide and the prefixies (resp. suffixies) of length k-1 are equal as well. The size of the smallest alphabet avoiding 2-repetitions of words, i.e. squares, is three and for abelian squares it is four. It follows that for 2-abelian squares this size has to be three or four. Similarly, the size of the smallest alphabet where 2-abelian cubes, i.e. 3-repetitions, can be avoided is two or three, because cubes (resp. abelian cubes) are avoidable in binary (resp. ternary) alphabet. We show that for 2-abelian squares the required size is four, as in the case of abelian squares. The longest 2-abelian square-free ternary word is of length 537. The question for 2-abelian cubes is open. Though, we have computational evidence that the size would be two, since there exists 2-abelian cube-free binary word of length 100 000, meaning that the 2-abelian case would behave like that of words.
Comment: 6 pages, 3 figures, Dagstuhl Seminar Combinatorial and Algorithmic Aspects of Sequence Processing (11081)