{
  "id": "1307.2828",
  "version": "v4",
  "published": "2013-07-10T15:32:31.000Z",
  "updated": "2014-03-25T16:40:57.000Z",
  "title": "A Coloring Problem for Infinite Words",
  "authors": [
    "Aldo de Luca",
    "Elena V. Pribavkina",
    "Luca Q. Zamboni"
  ],
  "comment": "arXiv admin note: incorporates 1301.5263",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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.$",
  "revisions": [
    {
      "version": "v4",
      "updated": "2014-03-25T16:40:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R15",
      "05D10"
    ],
    "keywords": [
      "infinite words",
      "coloring problem",
      "positive answer",
      "standard bernoulli measure",
      "finite non-empty set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1307.2828D"
    }
  }
}