Seminário de Álgebra  RSS

24/10/2019, 14:00 — 15:00 — Sala P4.35, Pavilhão de Matemática
, 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.

Projecto FCT UID/MAT/04459/2019.


Organizador actual: Gustavo Granja

CAMGSD FCT