Dirac's theorem for random regular graphs. (28th January 2021)

• Record Type: Journal Article
• Authors: Condon, Padraig; Espuny Díaz, Alberto; Girão, António; Kühn, Daniela; Osthus, Deryk
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 1(2021)
• Page Start: 17
• Page End: 36
• Publication Date: 2021-01-28
• Subjects: 05C80, -- 05C35, -- 05C45; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000346
• Languages: English
• ISSNs: 0963-5483

Abstract

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 $\epsilon > 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 + \epsilon )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.