Id: arxiv/2607.02483 Url: https://arxiv.org/abs/2607.02483 Tags: math.CO Score: 0 Title: Robustness and hyperstability for the Erdős-Gallai theorem Domain: math.CO Source: arxiv Authors: Micha Christoph, Alp Müyesser, Yuval Wigderson Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-02 Page: https://delphi.science/r/arxiv/2607.02483 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\geq K$, $p\geq 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…