2018/10/29 by Padraig Condon, Alberto Espuny Díaz, Condon, Padraig +7
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1810.12433
openalex publication_date 2018/10/29 · openalex created_date 2022/10/23 · openalex updated_date 2026/07/28
P 'osa's theorem states that any graph G whose degree sequence d1 \≤\n\… \≤ dn satisfies di \≥ i+1 for all i < n/2 has a Hamilton cycle.\nThis degree condition is best possible. We show that a similar result holds for\nsuitable subgraphs G of random graphs, i.e. we prove a `resilience version'\nof P 'osa's theorem: if pn \≥ C \log n and the i-th vertex degree (ordered\nincreasingly) of G \⊆ Gn,p is at least (i+o(n))p for all i<n/2,\nthen G has a Hamilton cycle. This is essentially best possible and\nstrengthens a resilience version of Dirac's theorem obtained by Lee and\nSudakov.\n Chv 'atal's theorem generalises P 'osa's theorem and characterises all degree\nsequences which ensure the existence of a Hamilton cycle. We show that a\nnatural guess for a resilience version of Chv 'atal's theorem fails to be true.\nWe formulate a conjecture which would repair this guess, and show that the\ncorresponding degree conditions ensure the existence of a perfect matching in\nany subgraph of Gn,p which satisfies these conditions. This provides an\nasymptotic characterisation of all degree sequences which resiliently guarantee\nthe existence of a perfect matching.\n