## Abstract

Pósa’s theorem states that any graph G whose degree sequence d_{1} ≤ · · · ≤ d_{n} satisfies d_{i} ≥ 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 ‘resilience version’ of Pósa’s theorem: if pn ≥ C log n and the i-th vertex degree (ordered increasingly) of G ⊆ 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 resilience version of Dirac’s theorem obtained by Lee and Sudakov. Chvátal’s theorem generalises Pósa’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átal’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.

Original language | English |
---|---|

Article number | #P4.54 |

Journal | Electronic Journal of Combinatorics |

Volume | 26 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2019 |

### Bibliographical note

Funding Information:Supported by the EPSRC, grant no. EP/N019504/1, and by the Royal Society and the Wolfson Foundation Supported by the European Research Council under the European Union?s Seventh Framework Programme (FP/2007?2013) / ERC Grant 306349. We are grateful to Ant?nio Gir?o for some helpful discussions which led us to simplify one of our proofs.

Funding Information:

∗Supported by the EPSRC, grant no. EP/N019504/1, and by the Royal Society and the Wolfson Foundation †Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP/2007–2013) / ERC Grant 306349

Publisher Copyright:

©The authors.

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics