$k$-abelian complexity and fluctuation
Also appears in collection : Combinatorics on words / Combinatoire des mots
Words $u$ and $v$ are defined to be $k$-abelian equivalent if every factor of length at most $k$ appears as many times in $u$ as in $v$. The $k$-abelian complexity function of an infinite word can then be defined so that it maps a number $n$ to the number of $k$-abelian equivalence classes of length-$n$ factors of the word. We consider some variations of extremal behavior of $k$-abelian complexity.
First, we look at minimal and maximal complexity. Studying minimal complexity leads to results on ultimately periodic and Sturmian words, similar to the results by Morse and Hedlund on the usual factor complexity. Maximal complexity is related to counting the number of equivalence classes. As a more complicated topic, we study the question of how much k-abelian complexity can fluctuate between fast growing and slowly growing values. These questions could naturally be asked also in a setting where we restrict our attention to some subclass of all words, like morphic words.
![$k$-sum free sets in $[0,1]$](/media/cache/video_light/uploads/video/2015-09-10_de_Roton-video--19cf70874d3c5af7378c268cab865b06.jpg)
