Dirac's theorem for random regular graphs

DOI10.1017/S0963548320000346MaRDI QIDQ4993119zbMATH OpenOpenAlexFDO

Authors Padraig Condon, Alberto Espuny Díaz, António Girão, Daniela Kühn, Deryk Osthus

Publication date 15 June 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.05052

zbMATH Keywords

Dirac's theoremHamilton cyclelocal resiliencerandom regular graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We prove a `resilience' version of Dirac's theorem in the setting of random regular graphs. More precisely, we show that, whenever $d$ is sufficiently large compared to $varepsilon>0$, a.a.s. the following holds: let $G^{\prime }$ be any subgraph of the random $n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+varepsilon)d$. Then $G^{\prime }$ is Hamiltonian. This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov. Our result is best possible: firstly, the condition that $d$ is large cannot be omitted, and secondly, the minimum degree bound cannot be improved.

Recommendations

• Dirac's theorem for random graphs
• Random directed graphs are robustly Hamiltonian
• Robust Hamiltonicity of Dirac graphs
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• Hamiltonian cycles in random regular graphs

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Corrádi and Hajnal's theorem for sparse random graphs
• Dirac's theorem for random graphs
• Hamiltonicity in random graphs is born resilient
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 4049676 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Local resilience of almost spanning trees in random graphs
• Local resilience of an almost spanning k‐cycle in random graphs
• Local resilience of graphs
• Long paths and Hamiltonicity in random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On two Hamilton cycle problems in random graphs
• Pattern colored Hamilton cycles in random graphs
• Random directed graphs are robustly Hamiltonian
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Random regular graphs of high degree
• Resilience of perfect matchings and Hamiltonicity in random graph processes
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• Resilient pancyclicity of random and pseudorandom graphs
• Robust Hamiltonicity of random directed graphs
• Sandwiching random graphs: universality between random graph models
• Size biased couplings and the spectral gap for random regular graphs
• The bandwidth theorem in sparse graphs
• The probabilistic method
• The spectral gap of dense random regular graphs
• Uniform generation of random regular graphs of moderate degree
• Weighted sums of certain dependent random variables

Cited in

(11)

• Robust Hamiltonicity of random directed graphs
• Triangle resilience of the square of a Hamilton cycle in random graphs
• Discrepancy properties for random regular digraphs
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Dirac's theorem for random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Hamiltonicity in random directed graphs is born resilient
• Robust Hamiltonicity of random directed graphs: extended abstract
• The global resilience of Hamiltonicity in \(G(n, p)\)
• Hamiltonicity of graphs perturbed by a random regular graph
• Resilience with respect to Hamiltonicity in random graphs

This page was built for publication: Dirac's theorem for random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993119)