A coloring problem for infinite words

Abstract

In this paper we consider the following question in the spirit of Ramsey theory: Given x ∈ Aω, where A is a finite non-empty set, does there exist a finite coloring of the non-empty factors of x with the property that no factorization of x is monochromatic? We prove that this question has a positive answer using two colors for almost all words relative to the standard Bernoulli measure on Aω. We also show that it has a positive answer for various classes of uniformly recurrent words, including all aperiodic balanced words, and all words x ∈ Aω satisfying λx(n + 1) - λx(n) = 1 for all n sufficiently large, where λx(n) denotes the number of distinct factors of x of length n. © 2014 Elsevier Inc.