{
  "id": "1710.00505",
  "version": "v1",
  "published": "2017-10-02T06:45:21.000Z",
  "updated": "2017-10-02T06:45:21.000Z",
  "title": "Hamiltonicity in random graphs is born resilient",
  "authors": [
    "Richard Montgomery"
  ],
  "comment": "18 pages, submitted",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\{G_M\\}_{M\\geq 0}$ be the random graph process, where $G_0$ is the empty graph on $n$ vertices and subsequent graphs in the sequence are obtained by adding a new edge uniformly at random. For each $\\varepsilon>0$, we show that, almost surely, any graph $G_M$ with minimum degree at least 2 is not only Hamiltonian (as shown by Bollob\\'as), but remains Hamiltonian despite the removal of any set of edges, as long as at most $(1/2-\\varepsilon)$ of the edges incident to each vertex are removed. We say that such a graph is $(1/2-\\varepsilon)$-resiliently Hamiltonian. Furthermore, for each $\\epsilon>0$, we show that, almost surely, each graph $G_M$ is not $(1/2+\\varepsilon)$-resiliently Hamiltonian. These results strengthen those by Lee and Sudakov on the likely resilience of Hamiltonicity in the binomial random graph. For each $k$, we denote by $G^{(k)}$ the (possibly empty) maximal subgraph with minimum degree at least $k$ of a graph $G$. That is, the $k$-core of $G$. Krivelevich, Lubetzky and Sudakov have shown that, for each $k\\geq 15$, in almost every random graph process $\\{G_M\\}_{M\\geq 0}$, every non-empty $k$-core is Hamiltonian. We show that, for each $\\varepsilon>0$ and $k\\geq k_0(\\varepsilon)$, in almost every random graph process $\\{G_M\\}_{M\\geq 0}$, every non-empty $k$-core is $(1/2-\\varepsilon)$-resiliently Hamiltonian, but not $(1/2+\\varepsilon)$-resiliently Hamiltonian.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-10-02T06:45:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graph process",
      "born resilient",
      "resiliently hamiltonian",
      "hamiltonicity",
      "minimum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}