A coloring problem for infinite words
| Autor: | Luca Q. Zamboni, Elena V. Pribavkina, Aldo de Luca |
|---|---|
| Přispěvatelé: | Università degli studi di Napoli Federico II, Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Combinatoire, théorie des nombres (CTN), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), DE LUCA, Aldo, E., Pribavkina, L. Q., Zamboni |
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Omega Theoretical Computer Science Combinatorics Factorization STURMIAN WORDS [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Partition (number theory) ComputingMilieux_MISCELLANEOUS Mathematics Discrete mathematics Semigroup 68R15 05D10 ta111 Ramsey theory RAMSEY THEORY FACTOR COMPLEXITY Computational Theory and Mathematics Partition regularity Ramsey's theorem Combinatorics (math.CO) Coloring problem Computer Science::Formal Languages and Automata Theory Computer Science - Discrete Mathematics |
| Zdroj: | Journal of Combinatorial Theory, Series A Journal of Combinatorial Theory, Series A, Elsevier, 2014, 125, pp.306-332 Journal of Combinatorial Theory. Series A |
| ISSN: | 0097-3165 1096-0899 |
| 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: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect