Talk information

Date: Sunday, May 21, 2023
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Yahav Alon (TAU)
Title: Completion to Hamiltonicity and pancyclicity in $G(n,p)$

Abstract:

It is well known since the eighties that a random graph $G(n,p)$ becomes typically Hamiltonian for the edge probability $p(n)$ around $(\log n+\log\log n)/n$. It is thus natural to ask how far is $G$ drawn from $G(n,p)$, with $p(n)$ below the Hamiltonicity threshold, from being Hamiltonian, where we use edge distance from a nearest Hamiltonian graph as the measure. Improving upon an earlier result of Y. Alon and Krivelevich, we provide an accurate answer to this question for a wide range of $p(n)$. We further show that in this range, typically, $G(n,p)$ has a nearest Hamiltonian graph which is also pancyclic.

A joint work with Michael Anastos (IST Austria).