Dirac's theorem for random regular graphs. (28th January 2021) - Condon, Padraig; Espuny Díaz, Alberto; Girão, António; Kühn, Daniela; Osthus, Deryk
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 $ε > 0$, a.a.s. the following holds. Let $G'$ be any subgraph of the random n -vertex d -regular graph $G_{n, d}$ with minimum degree at least $$(1/2 + ε )d$$ . Then $G'$ 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.