Seminário de Álgebra 

24/10/2019, 14:00 — 15:00 — Sala P4.35, Pavilhão de Matemática
António Girão, University of Birmingham

Dirac's theorem for random regular graphs

In 1952, Dirac proved that any graph on $n$ vertices with minimum degree $n/2$ contains a Hamiltonian cycle, i.e. a cycle which passes through every vertex of the graph exactly once. 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 \gt 0$, a.a.s. the following holds: let $G_0$ 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_0$ 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. This is joint work with Padraig Condon, Alberto Espuny Díaz, Daniela Kuhn and Deryk Osthus.