{
  "id": "1810.12433",
  "version": "v1",
  "published": "2018-10-29T22:10:13.000Z",
  "updated": "2018-10-29T22:10:13.000Z",
  "title": "Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs",
  "authors": [
    "Padraig Condon",
    "Alberto Espuny Díaz",
    "Jaehoon Kim",
    "Daniela Kühn",
    "Deryk Osthus"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "P\\'osa's theorem states that any graph $G$ whose degree sequence $d_1 \\le \\ldots \\le d_n$ satisfies $d_i \\ge i+1$ for all $i < n/2$ has a Hamilton cycle. This degree condition is best possible. We show that a similar result holds for suitable subgraphs $G$ of random graphs, i.e. we prove a `resilient' version of P\\'osa's theorem: if $pn \\ge C \\log n$ and the $i$-th vertex degree (ordered increasingly) of $G \\subseteq G_{n,p}$ is at least $(i+o(n))p$ for all $i<n/2$, then $G$ has a Hamilton cycle. This is essentially best possible and strengthens a resilient version of Dirac's theorem obtained by Lee and Sudakov. Chv\\'atal's theorem generalises P\\'osa's theorem and characterises all degree sequences which ensure the existence of a Hamilton cycle. We show that a natural guess for a resilient version of Chv\\'atal's theorem fails to be true. We formulate a conjecture which would repair this guess, and show that the corresponding degree conditions ensure the existence of a perfect matching in any subgraph of $G_{n,p}$ which satisfies these conditions. This provides an asymptotic characterisation of all degree sequences which resiliently guarantee the existence of a perfect matching.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-10-29T22:10:13.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamilton cycle",
      "resilient degree sequences",
      "random graphs",
      "chvatals theorem generalises posas theorem",
      "degree condition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}