{
  "id": "1709.03901",
  "version": "v1",
  "published": "2017-09-12T15:12:22.000Z",
  "updated": "2017-09-12T15:12:22.000Z",
  "title": "Local resilience of an almost spanning $k$-cycle in random graphs",
  "authors": [
    "Nemanja Škorić",
    "Angelika Steger",
    "Miloš Trujić"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The famous P\\'{o}sa-Seymour conjecture states that for any $k \\geq 2$, a graph $G = (V, E)$ with minimum degree $kn/(k + 1)$ contains the $k$-th power of a Hamilton cycle. The conjecture was confirmed a couple of decades later by Koml\\'{o}s, S\\'{a}rk\\\"{o}zy, and Szemer\\'{e}di. We extend this result to a sparse setting. We show that for all $k \\geq 2$ and $\\varepsilon, \\alpha > 0$, if $p \\geq C(\\log{N}/N)^{1/k}$ then any subgraph of a random graph $G_{N, p}$ with minimum degree at least $(k/(k + 1) + \\alpha)Np$, w.h.p.\\ contains the $k$-th power of a cycle on at least $(1 - \\varepsilon)N$ vertices, improving upon the recent results of Noever and Steger for $k = 2$, as well as Allen, B\\\"{o}ttcher, Ehrenm\\\"{u}ller, and Taraz for $k \\geq 3$. Our result is almost best possible in three ways: $(1)$ for $p \\ll N^{-1/k}$ the random graph $G_{N, p}$ almost surely does not contain the $k$-th power of any long cycle; $(2)$ there exist subgraphs of $G_{N, p}$ with minimum degree $(k/(k + 1) + \\alpha)Np$ and $\\Omega(p^{-2})$ vertices not belonging to any triangles; $(3)$ there exist subgraphs of $G_{N, p}$ with minimum degree $(k/(k + 1) - \\alpha)Np$ which do not contain the $k$-th power of a cycle on $(1 - \\varepsilon)N$ vertices.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-09-12T15:12:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graph",
      "minimum degree",
      "th power",
      "local resilience",
      "conjecture states"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}