A coloring problem for infinite words

Abstract: In this paper we consider the following question in the spirit of Ramsey theory: Given

x i n A^{o} m e g 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^{o} m e g 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 i n A^{o} m e g a

satisfying

l a m b d a_{x} (n + 1) - l a m b d a_{x} (n) = 1

for all

n

sufficiently large, where

l a m b d a_{x} (n)

denotes the number of distinct factors of

x

of length

n .

Recommendations

Cites work

Cited in

(12)

This page was built for publication: A coloring problem for infinite words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2451905)