{
  "id": "1901.09605",
  "version": "v1",
  "published": "2019-01-28T11:22:21.000Z",
  "updated": "2019-01-28T11:22:21.000Z",
  "title": "Hamiltonicity in random directed graphs is born resilient",
  "authors": [
    "Richard Montgomery"
  ],
  "comment": "36 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\{D_M\\}_{M\\geq 0}$ be the $n$-vertex random directed graph process, where $D_0$ is the empty directed graph on $n$ vertices, and subsequent directed graphs in the sequence are obtained by the addition of a new directed edge uniformly at random. For each $\\varepsilon>0$, we show that, almost surely, any directed graph $D_M$ with minimum in- and out-degree at least 1 is not only Hamiltonian (as shown by Frieze), but remains Hamiltonian when edges are removed, as long as at most $(1/2-\\varepsilon)$ of both the in- and out-edges incident to each vertex are removed. We say such a directed graph is $(1/2-\\varepsilon)$-resiliently Hamiltonian. Furthermore, for each $\\varepsilon>0$, we show that, almost surely, each directed graph $D_M$ in the sequence is not $(1/2+\\varepsilon)$-resiliently Hamiltonian. This improves a result of Ferber, Nenadov, Noever, Peter and \\v{S}kori\\'{c}, who showed, for each $\\varepsilon>0$, that the binomial random directed graph $D(n,p)$ is almost surely $(1/2-\\varepsilon)$-resiliently Hamiltonian if $p=\\omega(\\log^8n/n)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-01-28T11:22:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "born resilient",
      "resiliently hamiltonian",
      "vertex random directed graph process",
      "hamiltonicity",
      "binomial random directed graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}