Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs

Padraig Condon¹ ; Alberto Espuny Díaz¹ ; Daniela Kühn¹ ; Deryk Osthus¹ ; Jaehoon Kim²

¹University of Birmingham
²University of Warwick

The electronic journal of combinatorics, Tome 26 (2019) no. 4

Résumé

Pósa'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 < 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 \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 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.

Détail

DOI : 10.37236/8279

Classification : 05C45, 05C70, 05C80, 05C07
Mots-clés : Chvátal's theorem, Pósa's theorem