A Coloring Problem for Infinite Words

Abstract

In this paper we consider the following question in the spirit of Ramsey theory: Given $x\in A^{\omega },$ 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^{\omega }.$ 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\in A^{\omega }$ satisfying ${\lambda }_x(n+1)-{\lambda }_x(n)=1$ for all $n$ sufficiently large, where ${\lambda }_x(n)$ denotes the number of distinct factors of $x$ of length $n.$

arXiv admin note: incorporates 1301.5263

References in corpus (1)

• Quasicrystals, model sets, and automatic sequences