{
  "id": "1404.7232",
  "version": "v2",
  "published": "2014-04-29T04:24:57.000Z",
  "updated": "2016-01-11T16:26:47.000Z",
  "title": "Rainbow arithmetic progressions",
  "authors": [
    "Steve Butler",
    "Craig Erickson",
    "Leslie Hogben",
    "Kirsten Hogenson",
    "Lucas Kramer",
    "Richard L. Kramer",
    "Jephian Chin-Hung Lin",
    "Ryan R. Martin",
    "Derrick Stolee",
    "Nathan Warnberg",
    "Michael Young"
  ],
  "comment": "20 pages, 2 figures, 3 tables",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers $n$ and $k$, the expression $aw([n],k)$ denotes the smallest number of colors with which the integers $\\{1,\\ldots,n\\}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. We establish that $aw([n],3)=\\Theta(\\log n)$ and $aw([n],k)=n^{1-o(1)}$ for $k\\geq 4$. For positive integers $n$ and $k$, the expression $aw(Z_n,k)$ denotes the smallest number of colors with which elements of the cyclic group of order $n$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. In this setting, arithmetic progressions can \"wrap around,\" and $aw(Z_n,3)$ behaves quite differently from $aw([n],3)$, depending on the divisibility of $n$. As shown in [Jungi\\'c et al., \\textit{Combin. Probab. Comput.}, 2003], $aw(Z_{2^m},3) = 3$ for any positive integer $m$. We establish that $aw(Z_n,3)$ can be computed from knowledge of $aw(Z_p,3)$ for all of the prime factors $p$ of $n$. However, for $k\\geq 4$, the behavior is similar to the previous case, that is, $aw(Z_n,k)=n^{1-o(1)}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-29T04:24:57.000Z",
      "abstract": "In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers $n$ and $k$, the expression $\\mathrm{aw}([n],k)$ denotes the smallest number of colors with which the integers $\\{1,\\ldots,n\\}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. We establish that $\\mathrm{aw}([n],3)=\\Theta(\\log n)$ and $\\mathrm{aw}([n],k)=n^{1-o(1)}$ for $k\\geq 4$. For positive integers $n$ and $k$, the expression $\\mathrm{aw}(\\mathbb{Z}_n,k)$ denotes the smallest number of colors with which elements of the cyclic group of order $n$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. In this setting, arithmetic progressions can \"wrap around,\" and $\\mathrm{aw}(\\mathbb{Z}_n,3)$ behaves quite differently from $\\mathrm{aw}([n],3)$, depending on the divisibility of $n$. In fact, $\\mathrm{aw}(\\mathbb{Z}_{2^m},3) = 3$ for any positive integer $m$. However, for $k\\geq 4$, the behavior is similar to the previous case, that is, $\\mathrm{aw}(\\mathbb{Z}_n,k)=n^{1-o(1)}$.",
      "comment": "21 pages, 2 figures, 4 tables",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2016-01-11T16:26:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D10",
      "11B25",
      "11B30",
      "11B50",
      "11B75"
    ],
    "keywords": [
      "rainbow arithmetic progression",
      "positive integer",
      "smallest number",
      "anti-van der waerden",
      "behaves quite"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.7232B"
    }
  }
}