21/12/2016, 14:00 — 15:00 — Sala 6.2.33, Faculdade de Ciências da Universidade de Lisboa
Manuel Silva, Universidade Nova de Lisboa/CMA
Ramsey theory for infinite words
In combinatorics of words, a concatenation of $k$ consecutive equal blocks is called a power of order $k$. We define an anti-power of order $k$ as a concatenation of $k$ consecutive pairwise distinct blocks of the same length. We show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. We will also generalize two combinatorial constructions given by Justin and Pirillo concerning arbitrarily large monochromatic $k$-powers occurring in infinite words and give a new classe of infinite words that do not allow infinite monochromatic factorizations.
