{
  "id": "1103.3809",
  "version": "v2",
  "published": "2011-03-19T21:16:08.000Z",
  "updated": "2011-11-22T21:16:09.000Z",
  "title": "A new approach to nonrepetitive sequences",
  "authors": [
    "Jarosław Grytczuk",
    "Jakub Kozik",
    "Piotr Micek"
  ],
  "comment": "5 pages, no figures.arXiv admin note: substantial text overlap with arXiv:1103.3810",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that 3 symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of 3-element sets $L_1,..., L_n$ there exists a nonrepetitive sequence $s_1, ..., s_n$ with $s_i\\in L_i$. Applying the probabilistic method one can prove that this is true for sufficiently large sets $L_i$. We present an elementary proof that sets of size 4 suffice (confirming the best known bound). The argument is a simple counting with Catalan numbers involved. Our approach is inspired by a new algorithmic proof of the Lov\\'{a}sz Local Lemma due to Moser and Tardos and its interpretations by Fortnow and Tao. The presented method has further applications to nonrepetitive games and nonrepetitive colorings of graphs.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-11-22T21:16:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "local lemma",
      "extension holds",
      "adjacent identical blocks",
      "thue asserts",
      "sufficiently large sets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1103.3809G"
    }
  }
}