Robustness and hyperstability for the Erdős-Gallai theorem
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.02483
curl -X POST /api/v1/records/arxiv/2607.02483/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.02483/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'