pith. sign in

arxiv: 2607.02483 · v1 · pith:T26VD7C4new · submitted 2026-07-02 · 🧮 math.CO

Robustness and hyperstability for the ErdH{o}s-Gallai theorem

Micha Christoph , Alp M\"uyesser , Yuval Wigderson This is my paper

Pith reviewed 2026-07-03 10:10 UTC · model grok-4.3

classification 🧮 math.CO
keywords Erdős-Gallai theoremcycle lengthgraph percolationhyperstabilityrobustnessaverage degreevertex cover
0
0 comments X

The pith

For every c>0 there is K such that graphs of average degree d, after keeping each edge independently with probability at least K/d, still contain a cycle of length (1-c)d with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper strengthens the classical Erdős-Gallai theorem, which guarantees a cycle of length at least the average degree d in any graph. It shows this long-cycle guarantee survives when each edge is retained independently with probability roughly 1/d, yielding a cycle of length nearly d asymptotically almost surely. A companion hyperstability statement says that any graph lacking a cycle of length d can be made, by deleting only a small fraction of its edges, into a graph whose components each admit a vertex cover of size slightly larger than d. Both results rest on a general structural theorem for graphs that traces back to hyperstability results for bounded-degree trees.

Core claim

For every c>0 there exists K such that for all d≥K, p≥K/d and every graph G with average degree d, the random graph G_p obtained by independently percolating each edge of G with probability p contains a cycle of length (1-c)d asymptotically almost surely as |V(G)|→∞. With related methods, any graph G without a cycle of length at least d is at most c dn edge deletions away from a graph all of whose connected components have a vertex-cover of size (1+c)d.

What carries the argument

A very general structure theorem about graphs that originates from results on the hyperstability of bounded-degree trees.

If this is right

  • The Erdős-Gallai lower bound on cycle length is stable under random edge deletion at the natural sparsity threshold p ~ 1/d.
  • Absence of long cycles forces a graph to be close, in edge-edit distance, to a collection of components each having a small vertex cover.
  • The same structural theorem yields both the percolation robustness and the hyperstability statements.
  • The result applies uniformly to every host graph of given average degree, without further regularity assumptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Long cycles in sparse graphs appear to be resilient even when most edges are randomly removed.
  • The hyperstability form may extend to other extremal problems that guarantee large substructures rather than just their existence.
  • The threshold p ~ 1/d suggests a natural scale at which cycle-forming paths remain connected after percolation.

Load-bearing premise

The argument depends on a broad structural description of graphs that comes from earlier hyperstability theorems for trees of bounded degree.

What would settle it

Construct a sequence of graphs with average degree d that, after independent edge percolation at probability K/d, contain no cycle longer than (1-c)d with probability bounded away from zero.

Figures

Figures reproduced from arXiv: 2607.02483 by Alp M\"uyesser, Micha Christoph, Yuval Wigderson.

Figure 1
Figure 1. Figure 1: The diagram displays the partial order of parameters in the proof of Theorem 2.1, where [PITH_FULL_IMAGE:figures/full_fig_p024_1.png] view at source ↗
read the original abstract

The Erd\H{o}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\H{o}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 percolating each edge of $G$ with probability $p$ contains a cycle of length $(1-c)d$ asymptotically almost surely as $|V(G)|\to \infty$. With related methods, we prove the following hyperstability version of the Erd\H{o}s-Gallai theorem: any graph $G$ without a cycle of length at least $d$ is at most $c dn$ edge deletions away from a graph all of whose connected components have a vertex-cover of size $(1+c)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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript proves a robust version of the Erdős-Gallai theorem: for every c>0 there exists K such that for d≥K, p≥K/d, and any graph G with average degree d, the edge-percolated random graph G_p contains a cycle of length (1-c)d asymptotically almost surely as |V(G)|→∞. It also establishes a hyperstability version: any graph without a cycle of length at least d is at most c dn edge deletions from a graph whose components each have a vertex cover of size (1+c)d. Both results rest on a general structure theorem derived from Pokrovskiy's hyperstability theorems for bounded-degree trees.

Significance. If the central claims hold, the work supplies quantitative robustness and hyperstability extensions to a classical extremal result, with explicit dependence on the average degree d and percolation probability p. The explicit constants K and the edge-deletion bound c dn are strengths; the reduction to a structure theorem originating outside the manuscript is noted but requires verification of its applicability.

major comments (1)
  1. [Abstract / core argument] Abstract and core argument: the robust and hyperstability claims both invoke a 'very general structure theorem' originating from Pokrovskiy's results on hyperstability of bounded-degree trees. No explicit statement of this generalized theorem appears, nor is there verification that the hypotheses remain satisfied when the forbidden subgraph is a cycle of length (1-c)d (with d arbitrarily large) rather than a bounded-degree tree; this generalization is load-bearing for the reduction step that enables the percolation argument with p≥K/d.
minor comments (1)
  1. Notation for the percolation parameter p and the constant K could be introduced with a forward reference to the precise dependence on c and d.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the need for greater explicitness regarding the structure theorem. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract / core argument] Abstract and core argument: the robust and hyperstability claims both invoke a 'very general structure theorem' originating from Pokrovskiy's results on hyperstability of bounded-degree trees. No explicit statement of this generalized theorem appears, nor is there verification that the hypotheses remain satisfied when the forbidden subgraph is a cycle of length (1-c)d (with d arbitrarily large) rather than a bounded-degree tree; this generalization is load-bearing for the reduction step that enables the percolation argument with p≥K/d.

    Authors: We agree that the current manuscript would be strengthened by an explicit statement of the generalized structure theorem and by a direct verification of its hypotheses in the present setting. In the revised version we will add a self-contained statement of the structure theorem (obtained by adapting Pokrovskiy’s hyperstability results for bounded-degree trees) together with a short but complete check that the required conditions hold when the forbidden subgraph is a cycle of length at least (1-c)d for sufficiently large d. This will make the reduction step used for both the percolation and hyperstability results fully transparent. revision: yes

Circularity Check

0 steps flagged

No circularity; core structure theorem externally grounded in Pokrovskiy

full rationale

The paper's abstract and description state that the central structure theorem 'originates from results of Pokrovskiy concerning the hyperstability of bounded-degree trees.' This is an external prior result, not a self-citation, self-definition, fitted prediction, or ansatz smuggled via the authors' own prior work. The robust percolation claim and hyperstability version are presented as applications of this external theorem, with no equations or steps in the provided text reducing the target statements (cycle of length (1-c)d in G_p, or o(dn) edge deletions) to the inputs by construction. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper is a proof extension in extremal graph theory that invokes one external combinatorial structure theorem.

axioms (1)
  • domain assumption Pokrovskiy's structure theorem on hyperstability of bounded-degree trees
    Abstract states this theorem is at the core of the argument for both results.

pith-pipeline@v0.9.1-grok · 5744 in / 1296 out tokens · 48406 ms · 2026-07-03T10:10:52.465414+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages · 1 internal anchor

  1. [1]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi, The longest path in a random graph,Combinatorica1 (1981), 1–12

    work page 1981

  2. [2]

    N. Alon, M. Krivelevich, and B. Sudakov, Embedding nearly-spanning bounded degree trees,Com- binatorica27(2007), 629–644

    work page 2007

  3. [3]

    Balogh, B

    J. Balogh, B. Csaba, M. Pei, and W. Samotij, Large bounded degree trees in expanding graphs, Electron. J. Combin.17(2010), 6–15

    work page 2010

  4. [4]

    Bohman, A

    T. Bohman, A. Frieze, and R. Martin, How many random edges make a dense graph Hamiltonian?, Random Structures Algorithms22(2003), 33–42

    work page 2003

  5. [5]

    Bollob´ as, Long paths in sparse random graphs,Combinatorica2(1982), 223–228

    B. Bollob´ as, Long paths in sparse random graphs,Combinatorica2(1982), 223–228

    work page 1982

  6. [6]

    Bollob´ as, T

    B. Bollob´ as, T. I. Fenner, and A. M. Frieze, Long cycles in sparse random graphs, inGraph theory and combinatorics (Cambridge, 1983), Academic Press, London, 1984, 59–64

    work page 1983

  7. [7]

    Bollob´ as and R

    B. Bollob´ as and R. Morris,Basic graph theory, Cambridge University Press, Cambridge, 2026

    work page 2026

  8. [8]

    Chakraborti, O

    D. Chakraborti, O. Janzer, A. Methuku, and R. Montgomery, Regular subgraphs at every density, Trans. Amer. Math. Soc.(2026), to appear. Preprint available at arXiv:2411.11785

    work page arXiv 2026

  9. [9]

    Conlon and W

    D. Conlon and W. T. Gowers, Combinatorial theorems in sparse random sets,Ann. of Math. (2) 184(2016), 367–454

    work page 2016

  10. [10]

    Davoodi, D

    A. Davoodi, D. Piguet, H. ˇRada, and N. Sanhueza-Matamala, The asymptotic version of the Erd˝ os– S´ os conjecture and beyond, 2026. Preprint available at arXiv:2603.17755

    work page arXiv 2026

  11. [11]

    G. A. Dirac, Some theorems on abstract graphs,Proc. London Math. Soc. (3)2(1952), 69–81

    work page 1952

  12. [12]

    Erd˝ os and T

    P. Erd˝ os and T. Gallai, On maximal paths and circuits of graphs,Acta Math. Acad. Sci. Hungar. 10(1959), 337–356. 20

    work page 1959

  13. [13]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi, On the evolution of random graphs,Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl.5(1960), 17–61

    work page 1960

  14. [14]

    Fernandez de la Vega, Long paths in random graphs,Studia Sci

    W. Fernandez de la Vega, Long paths in random graphs,Studia Sci. Math. Hungar.14(1979), 335–340

    work page 1979

  15. [15]

    A. M. Frieze, On large matchings and cycles in sparse random graphs,Discrete Math.59(1986), 243–256

    work page 1986

  16. [16]

    F¨ uredi, A

    Z. F¨ uredi, A. Kostochka, R. Luo, and J. Verstra¨ ete, Stability in the Erd˝ os-Gallai theorem on cycles and paths, II,Discrete Math.341(2018), 1253–1263

    work page 2018

  17. [17]

    F¨ uredi, A

    Z. F¨ uredi, A. Kostochka, and J. Verstra¨ ete, Stability in the Erd˝ os-Gallai theorems on cycles and paths,J. Combin. Theory Ser. B121(2016), 197–228

    work page 2016

  18. [18]

    F¨ uredi and M

    Z. F¨ uredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erd˝ os centennial,Bolyai Soc. Math. Stud., vol. 25, J´ anos Bolyai Math. Soc., Budapest, 2013, 169– 264

    work page 2013

  19. [19]

    Glebov, H

    R. Glebov, H. Naves, and B. Sudakov, The threshold probability for long cycles,Combin. Probab. Comput.26(2017), 208–247

    work page 2017

  20. [20]

    Keevash, Hypergraph Tur´ an problems, inSurveys in combinatorics 2011,London Math

    P. Keevash, Hypergraph Tur´ an problems, inSurveys in combinatorics 2011,London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, 83–139

    work page 2011

  21. [21]

    Kelly, A

    T. Kelly, A. M¨ uyesser, and A. Pokrovskiy, Optimal spread for spanning subgraphs of Dirac hyper- graphs,J. Combin. Theory Ser. B169(2024), 507–541

    work page 2024

  22. [22]

    G. N. Kopylov, Maximal paths and cycles in a graph,Dokl. Akad. Nauk SSSR234(1977), 19–21

    work page 1977

  23. [23]

    Krivelevich, C

    M. Krivelevich, C. Lee, and B. Sudakov, Robust Hamiltonicity of Dirac graphs,Trans. Amer. Math. Soc.366(2014), 3095–3130

    work page 2014

  24. [24]

    Krivelevich, C

    M. Krivelevich, C. Lee, and B. Sudakov, Long paths and cycles in random subgraphs of graphs with large minimum degree,Random Structures Algorithms46(2015), 320–345

    work page 2015

  25. [25]

    Lee and B

    C. Lee and B. Sudakov, Dirac’s theorem for random graphs,Random Structures Algorithms41 (2012), 293–305

    work page 2012

  26. [26]

    Ma and B

    J. Ma and B. Ning, Stability results on the circumference of a graph,Combinatorica40(2020), 105–147

    work page 2020

  27. [27]

    Montgomery, Sharp threshold for embedding combs and other spanning trees in random graphs,

    R. Montgomery, Sharp threshold for embedding combs and other spanning trees in random graphs,

    work page

  28. [28]

    Preprint available at arXiv:1405.6560

    work page internal anchor Pith review Pith/arXiv arXiv

  29. [29]

    Pokrovskiy, Hyperstability in the Erd˝ os-S´ os conjecture, 2024

    A. Pokrovskiy, Hyperstability in the Erd˝ os-S´ os conjecture, 2024. Preprint available at arXiv:2409.15191

    work page arXiv 2024

  30. [30]

    Riordan, Long cycles in random subgraphs of graphs with large minimum degree,Random Structures Algorithms45(2014), 764–767

    O. Riordan, Long cycles in random subgraphs of graphs with large minimum degree,Random Structures Algorithms45(2014), 764–767

    work page 2014

  31. [31]

    R¨ odl and B

    V. R¨ odl and B. Wysocka, Note on regular subgraphs,J. Graph Theory24(1997), 139–154

    work page 1997

  32. [32]

    Schacht, Extremal results for random discrete structures,Ann

    M. Schacht, Extremal results for random discrete structures,Ann. of Math. (2)184(2016), 333–365

    work page 2016

  33. [33]

    Sudakov, Robustness of graph properties, inSurveys in combinatorics 2017,London Math

    B. Sudakov, Robustness of graph properties, inSurveys in combinatorics 2017,London Math. Soc. Lecture Note Ser., vol. 440, Cambridge Univ. Press, Cambridge, 2017, 372–408

    work page 2017

  34. [34]

    Tao,Higher order Fourier analysis,Graduate Studies in Mathematics, vol

    T. Tao,Higher order Fourier analysis,Graduate Studies in Mathematics, vol. 142, American Math- ematical Society, Providence, RI, 2012

    work page 2012

  35. [35]

    D. R. Woodall, Maximal circuits of graphs. I,Acta Math. Acad. Sci. Hungar.28(1976), 77–80. 21 A Proof of Theorem 2.1 The goal of this appendix is to give a proof of Theorem 2.1. Let us begin by recalling the statement. Theorem 2.1.For everyC, J, ε, δ >0, there existλ, q, M >0, such that for everyζ >0, there exists β >0such that for everyγ >0there existsρ ...

    work page 1976

  36. [39]

    sufficiently small

    For everyH∈ Hthere are at most1/λotherH ′ ∈ Hwhich intersectHin more thanγd vertices. A.1 Clump-theoretic machinery Since the proof of Theorem 2.1 closely follows the argument of Pokrovskiy [28], let us begin by quoting, more or less verbatim, many of the auxiliary definitions and results of [28]. Definition A.1([28, Definition 4.1]).Letp, κ >0 and letmbe...

    work page

  37. [40]

    EachH∈ Hisβd-connected and has diameter at most1/β

    work page

  38. [41]

    Any twoH, H ′ ∈ Hintersect in at mostζdvertices

    work page

  39. [42]

    EveryH∈ Hhas at leastλdvertices which intersect some otherH ′ ∈ H

    work page

  40. [43]

    Proof.As the clumps are edge-disjoint, we certainly have that all the graphs in the collectionHare edge-disjoint, and by definitionG 4 is the union of these graphs

    For everyH∈ Hthere are at most1/λotherH ′ ∈ Hwhich intersectHin more thanγdvertices. Proof.As the clumps are edge-disjoint, we certainly have that all the graphs in the collectionHare edge-disjoint, and by definitionG 4 is the union of these graphs. For the first item, we observe that by Lemma A.12, for everyK∈ K,D(K) isκ (10Chp −13)!p13m/2-connected and ...

    work page