Robustness and hyperstability for the Erdős-Gallai theorem

Abstract

The Erdős--Gallai theorem states that every graph of average degree $d$ contains a cycle of length at least $d$. We prove the following robust extension of the Erdős--Gallai theorem: For every $c>0$ there exists $K$ such that for all $d\ge K$, $p\ge K/d$ and every graph $G$ with average degree $d$, the random graph $G_p$ obtained by independently sampling each edge of $G$ with probability $p$ contains a cycle of length at least $(1-c)d$ asymptotically almost surely as $|V(G)|\to \infty$. With related methods, we prove the following hyperstability version of the Erdős--Gallai theorem: any graph $G$ without a cycle of length at least $d$ is at most $cd|V(G)|$ edge deletions away from a graph all of whose connected components have a vertex-cover of size at most $d$. At the core of our argument lies a very general structure theorem about graphs that originates from results of Pokrovskiy concerning the hyperstability of bounded-degree trees.

22 pages + 7 page appendix