On some variations of coloring problems of infinite words

DOI10.1016/J.JCTA.2015.08.006MaRDI QIDQ889516zbMATH OpenOpenAlexFDO

Authors Luca Q. Zamboni, Aldo De Luca

Publication date 6 November 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.06807

zbMATH Keywords

coloring problems for infinite words combinatorics on words Ramsey theory Sturmian words

Mathematics Subject Classification ID

Ramsey theory (05D10) Combinatorics on words (68R15)

Abstract: Given a finite coloring (or finite partition) of the free semigroup

A^{+}

over a set

A

, we consider various types of monochromatic factorizations of right sided infinite words

x i n A^{o} m e g a

. Some stronger versions of the usual notion of monochromatic factorization are introduced. A factorization is called sequentially monochromatic when concatenations of consecutive blocks are monochromatic. A sequentially monochromatic factorization is called ultra monochromatic if any concatenation of arbitrary permuted blocks of the factorization has the same color of the single blocks. We establish links, and in some cases equivalences, between the existence of these factorizations and fundamental results in Ramsey theory including the infinite Ramsey theorem, Hindman's finite sums theorem, partition regularity of IP sets and the Milliken-Taylor theorem. We prove that for each finite set

A

and each finite coloring

v a r p h i : A^{+} i g h t a r r o w C,

for almost all words

x i n A^{o} m e g a,

there exists

y

in the subshift generated by

x

admitting a

v a r p h i

-ultra monochromatic factorization, where "almost all" refers to the Bernoulli measure on

A^{o} m e g a .

Recommendations

Cites work

Cited in

(13)

This page was built for publication: On some variations of coloring problems of infinite words

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