{
  "id": "1606.08532",
  "version": "v1",
  "published": "2016-06-28T01:47:50.000Z",
  "updated": "2016-06-28T01:47:50.000Z",
  "title": "The extremal function for cycles of length $\\ell$ mod $k$",
  "authors": [
    "Benny Sudakov",
    "Jacques Verstraete"
  ],
  "comment": "10 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Burr and Erd\\H{o}s conjectured that for each $k,\\ell \\in \\mathbb Z^+$ such that $k \\mathbb Z + \\ell$ contains even integers, there exists $c_k(\\ell)$ such that any graph of average degree at least $c_k(\\ell)$ contains a cycle of length $\\ell$ mod $k$. This conjecture was proved by Bollob\\'{a}s, and many successive improvements of upper bounds on $c_k(\\ell)$ appear in the literature. In this short note, for $1 \\leq \\ell \\leq k$, we show that $c_k(\\ell)$ is proportional to the largest average degree of a $C_{\\ell}$-free graph on $k$ vertices, which determines $c_k(\\ell)$ up to an absolute constant. In particular, using known results on Tur\\'{a}n numbers for even cycles, we obtain $c_k(\\ell) = O(\\ell k^{2/\\ell})$ for all even $\\ell$, which is tight for $\\ell \\in \\{4,6,10\\}$. Since the complete bipartite graph $K_{\\ell - 1,n - \\ell + 1}$ has no cycle of length $2\\ell$ mod $k$, it also shows $c_k(\\ell) = \\Theta(\\ell)$ for $\\ell = \\Omega(\\log k)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-06-28T01:47:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "extremal function",
      "complete bipartite graph",
      "largest average degree",
      "absolute constant",
      "free graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}