{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:35Z","timestamp":1753893815299,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>P\u00f3sa's theorem states that any graph $G$ whose degree sequence $d_1 \\le \\cdots \\le d_n$ satisfies $d_i \\ge i+1$ for all $i &lt; 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 `resilience version' of P\u00f3sa'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&lt;n\/2$, then $G$ has a Hamilton cycle. This is essentially best possible and strengthens a resilience version of Dirac's theorem obtained by Lee and Sudakov.\r\nChv\u00e1tal's theorem generalises P\u00f3sa's theorem and characterises all degree sequences which ensure the existence of a Hamilton cycle. We show that a natural guess for a resilience version of Chv\u00e1tal'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.<\/jats:p>","DOI":"10.37236\/8279","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T00:59:20Z","timestamp":1578617960000},"source":"Crossref","is-referenced-by-count":1,"title":["Resilient Degree Sequences with respect to Hamilton Cycles and Matchings in Random Graphs"],"prefix":"10.37236","volume":"26","author":[{"given":"Padraig","family":"Condon","sequence":"first","affiliation":[]},{"given":"Alberto","family":"Espuny D\u00edaz","sequence":"additional","affiliation":[]},{"given":"Daniela","family":"K\u00fchn","sequence":"additional","affiliation":[]},{"given":"Deryk","family":"Osthus","sequence":"additional","affiliation":[]},{"given":"Jaehoon","family":"Kim","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2019,12,20]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i4p54\/7985","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i4p54\/7985","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T23:00:04Z","timestamp":1579215604000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v26i4p54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,20]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,10,11]]}},"URL":"https:\/\/doi.org\/10.37236\/8279","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2019,12,20]]},"article-number":"P4.54"}}