A Coloring Problem for Infinite Words
| Autor: | de Luca, Aldo, Pribavkina, Elena V., Zamboni, Luca Q. |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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.$ Comment: arXiv admin note: incorporates 1301.5263 |
| Databáze: | arXiv |
| Externí odkaz: |
|