{
  "id": "2007.02891",
  "version": "v1",
  "published": "2020-07-06T17:07:05.000Z",
  "updated": "2020-07-06T17:07:05.000Z",
  "title": "Hamiltonicity of random subgraphs of the hypercube",
  "authors": [
    "Padraig Condon",
    "Alberto Espuny Díaz",
    "António Girão",
    "Daniela Kühn",
    "Deryk Osthus"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We study Hamiltonicity in random subgraphs of the hypercube $\\mathcal{Q}^n$. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of $\\mathcal{Q}^n$ according to a uniformly chosen random ordering. Then, with high probability, as soon as the graph produced by this process has minimum degree $2k$, it contains $k$ edge-disjoint Hamilton cycles, for any fixed $k\\in\\mathbb{N}$. Secondly, we obtain a perturbation result: if $H\\subseteq\\mathcal{Q}^n$ satisfies $\\delta(H)\\geq\\alpha n$ with $\\alpha>0$ fixed and we consider a random binomial subgraph $\\mathcal{Q}^n_p$ of $\\mathcal{Q}^n$ with $p\\in(0,1]$ fixed, then with high probability $H\\cup\\mathcal{Q}^n_p$ contains $k$ edge-disjoint Hamilton cycles, for any fixed $k\\in\\mathbb{N}$. In particular, both results resolve a long standing conjecture, posed e.g. by Bollob\\'as, that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$. Our techniques also show that, with high probability, for all fixed $p\\in(0,1]$ the graph $\\mathcal{Q}^n_p$ contains an almost spanning cycle. Our methods involve branching processes, the R\\\"odl nibble, and absorption.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-06T17:07:05.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random subgraphs",
      "high probability",
      "random binomial subgraph",
      "hamiltonicity",
      "edge-disjoint hamilton cycles"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}