From monotone arithmetic progressions to bounded additive complexity in infinite words

12 February 2013
Veselin Jungic
I will describe how a search for the answer to an old question about the existence of monotone arithmetic progressions in permutations of positive integers led to the study of infinite words with bounded additive complexity. The additive complexity of a word on a finite subset of integers is defined as the function that, for a positive integer $n$, counts the maximum number of factors of length $n$, no two of which have the same sum.
  • Combinatorial Theory Seminar