Talk information

Date: Sunday, November 27, 2022
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Dan Hefetz (University of Ariel)
Title: Cycle lengths in randomly perturbed graphs

Abstract:

Let $G$ be an $n$-vertex graph, where $\delta(G) \geq \delta n$ for some $\delta := \delta(n)$. A result of Bohman, Frieze and Martin from 2003 asserts that if $\alpha(G) = O \left(\delta^2 n \right)$, then perturbing $G$ via the addition of $\omega \left(\frac{\log(1/\delta)}{\delta^3} \right)$ random edges, a.a.s. results in a Hamiltonian graph. This bound on the size of the random perturbation is only tight when $\delta$ is independent of $n$ and deteriorates to become uninformative when $\delta = \Omega \left(n^{-1/3} \right)$. We prove several improvements and extensions of this result.

Based on joint work with Elad Aigner-Horev and Michael Krivelevich.