{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-02","reactions":{}}