When: Sunday, May 21,
10am
Where: Schreiber 309
Speaker: Yahav Alon, Tel Aviv University
Title:
Completion to Hamiltonicity and Pancyclicity in $G(n,p)$
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).