{
  "id": "1207.0312",
  "version": "v3",
  "published": "2012-07-02T09:15:38.000Z",
  "updated": "2013-05-25T19:56:14.000Z",
  "title": "Long paths and cycles in random subgraphs of graphs with large minimum degree",
  "authors": [
    "Michael Krivelevich",
    "Choongbum Lee",
    "Benny Sudakov"
  ],
  "comment": "26 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "For a given finite graph $G$ of minimum degree at least $k$, let $G_{p}$ be a random subgraph of $G$ obtained by taking each edge independently with probability $p$. We prove that (i) if $p \\ge \\omega/k$ for a function $\\omega=\\omega(k)$ that tends to infinity as $k$ does, then $G_p$ asymptotically almost surely contains a cycle (and thus a path) of length at least $(1-o(1))k$, and (ii) if $p \\ge (1+o(1))\\ln k/k$, then $G_p$ asymptotically almost surely contains a path of length at least $k$. Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking $G$ to be the complete graph on $k+1$ vertices.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-05-25T19:56:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "large minimum degree",
      "random subgraph",
      "long paths",
      "surely contains",
      "binomial random graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1207.0312K"
    }
  }
}