Pith. sign in

REVIEW 2 minor 31 references

Pancyclicity of graphs perturbed by a random $F$-factor

T0 review · 0 major / 2 minor · reviewed 2026-06-30 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The pancyclicity threshold for graphs perturbed by a random K_r-factor equals the Hamiltonicity threshold ρ_r solving x^r + r x -1=0.

desk verdict The paper settles the Espuny Díaz-Girão conjecture by proving the Hamiltonicity and pancyclicity thresholds coincide at the explicit root ρ_r for random K_r-factor perturbations, via a general F-factor framework. read the letter →

arxiv 2606.02160 v2 pith:AKTQ3V5C submitted 2026-06-01 math.CO

Dingjia Mao , Feihong Yuan , Wenling Zhou This is my paper · ORCID
classification math.CO
keywords pancyclicityHamiltonicityrandomfactorsminimumdegreegraphperturbationsK_r-factorthresholdfunctions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper determines the sharp minimum-degree threshold guaranteeing that a graph plus a random K_r-factor is pancyclic. It shows this threshold equals the one for Hamiltonicity and resolves a conjecture by proving the stronger pancyclic property. The result follows from a general framework developed for perturbations by random F-factors for any fixed connected graph F. A reader would care because it provides exact conditions under which random edge additions force the existence of cycles of all lengths in a graph.

What carries the argument

The pancyclicity threshold α_pan^*(K_r) defined as the infimum of α such that any graph with minimum degree at least α n plus a random K_r-factor is pancyclic, shown to equal ρ_r.

What would settle it

A counterexample graph G with minimum degree slightly larger than ρ_r n such that G union a random K_r-factor fails to be pancyclic with positive probability would disprove the claim.

Watch

Extended reading notes

Core claim

We show that α^*(K_r)=α_pan^*(K_r)=ρ_r, where ρ_r is the unique positive solution of x^r + r x -1=0. The proof is obtained from a general framework for perturbations by a uniformly random F-factor, where F is an arbitrary fixed connected graph.

Load-bearing premise

The general framework for an arbitrary fixed connected graph F successfully extends to prove the pancyclic property for the specific case F=K_r without additional restrictions on the host graph.

Editorial extensions

If this is right

  • The same threshold applies to Hamiltonicity, resolving the conjecture of Espuny Díaz and Girão.
  • The threshold is sharp for both pancyclicity and Hamiltonicity.
  • The general framework for arbitrary F extends successfully to the pancyclic case for F = K_r.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The framework likely yields pancyclicity thresholds for other connected graphs F beyond K_r.
  • Connections between Hamiltonicity and pancyclicity thresholds hold in this perturbed setting.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper determines the sharp minimum-degree threshold for Hamiltonicity in graphs perturbed by a uniformly random K_r-factor, showing that this threshold coincides with the pancyclicity threshold at ρ_r (the unique positive root of x^r + r x -1 =0). It resolves a conjecture of Espuny Díaz and Girão and proves the stronger pancyclic property using a general framework developed for perturbations by a uniformly random F-factor, where F is an arbitrary fixed connected graph.

Significance. If the result holds, the work is significant for establishing that Hamiltonicity and pancyclicity thresholds coincide exactly at an explicitly defined parameter-free threshold ρ_r in the random K_r-factor perturbation model. The general framework for arbitrary connected F provides a reusable approach that could extend to other properties, and the explicit algebraic characterization of ρ_r strengthens the result by avoiding data-dependent fitting.

minor comments (2)
  1. The abstract introduces α^*(K_r) and α_pan^*(K_r) without immediate reference to their definitions; a brief parenthetical or forward reference would improve standalone readability.
  2. Notation for the random F-factor perturbation model is used consistently but could benefit from an early explicit reminder of the uniform distribution assumption in the introduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The report contains no major comments requiring a point-by-point reply.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper defines ρ_r explicitly as the unique positive root of the equation x^r + r x -1 =0 and proves that both the Hamiltonicity threshold α^*(K_r) and the pancyclicity threshold α_pan^*(K_r) equal this value. The argument relies on a general framework for random F-factor perturbations that extends directly to F=K_r. No step reduces a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or definitional tautology; the threshold equation is an independent mathematical characterization rather than a renaming or renormalization of the result itself. The derivation is therefore self-contained.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Based on abstract only; the result rests on standard domain assumptions of extremal graph theory and the definition of a uniform random F-factor. No free parameters or invented entities are introduced.

assumptions (1)
  • domain assumption Standard assumptions of extremal graph theory concerning minimum-degree conditions and the existence of cycles in perturbed graphs.
    Invoked implicitly to support the threshold statements for Hamiltonicity and pancyclicity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pancyclicity of graphs perturbed by a random $F$-factor." pith.science (2026). https://pith.science/paper/AKTQ3V5C

@misc{pith2026260602160,
  author       = {Pith},
  title        = {Pith review of: Pancyclicity of graphs perturbed by a random $F$-factor},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AKTQ3V5C}},
  note         = {Machine review of arXiv:2606.02160}
}
abstract

We determine the sharp minimum-degree threshold for Hamiltonicity in graphs perturbed by a uniformly random $K_r$-factor, resolving a conjecture of Espuny D\'iaz and Gir\~ao [Random Structures Algorithms, 2023]. In fact, we prove the stronger pancyclic statement. Let $\alpha^*(K_r)$ and $\alpha_{\text{pan}}^*(K_r)$ denote the Hamiltonicity and pancyclicity thresholds, respectively. We show that $\alpha^*(K_r)=\alpha_{\text{pan}}^*(K_r)=\rho_r$, where $\rho_r$ is the unique positive solution of $x^r+rx-1=0$. The proof is obtained from a general framework for perturbations by a uniformly random $F$-factor, where $F$ is an arbitrary fixed connected graph.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Antoniuk, A

    S. Antoniuk, A. Dudek, C. Reiher, A. Ruci´ nski, and M. Schacht. High powers of Hamilto- nian cycles in randomly augmented graphs.J. Graph Theory, 98(2):255–284, 2021

    work page 2021

  2. [2]

    Antoniuk, A

    S. Antoniuk, A. Dudek, and A. Ruci´ nski. Powers of Hamiltonian cycles in randomly augmented Dirac graphs—the complete collection.J. Graph Theory, 104(4):811–835, 2023

    work page 2023

  3. [3]

    Antoniuk, N

    S. Antoniuk, N. Kamˇ cev, C. Reiher, and T. P. Tukara. The complete picture for clique factors in randomly perturbed graphs.arXiv preprint arXiv:2603.22081, 2026

    work page arXiv 2026

  4. [4]

    Balogh, A

    J. Balogh, A. Treglown, and A. Z. Wagner. Tilings in randomly perturbed dense graphs. Combin. Probab. Comput., 28(2):159–176, 2019

    work page 2019

  5. [5]

    Bohman, A

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

    work page 2003

  6. [6]

    B¨ ottcher, J

    J. B¨ ottcher, J. Han, Y. Kohayakawa, R. Montgomery, O. Parczyk, and Y. Person. Univer- sality for bounded degree spanning trees in randomly perturbed graphs.Random Structures Algorithms, 55(4):854–864, 2019

    work page 2019

  7. [7]

    B¨ ottcher, R

    J. B¨ ottcher, R. Montgomery, O. Parczyk, and Y. Person. Embedding spanning bounded degree graphs in randomly perturbed graphs.Mathematika, 66(2):422–447, 2020

    work page 2020

  8. [8]

    B¨ ottcher, O

    J. B¨ ottcher, O. Parczyk, A. Sgueglia, and J. Skokan. The square of a Hamilton cycle in randomly perturbed graphs.Random Structures Algorithms, 65(2):342–386, 2024

    work page 2024

Show all 31 references
  1. [9]

    Chang, J

    Y. Chang, J. Han, Y. Kohayakawa, P. Morris, and G. O. Mota. Factors in randomly perturbed hypergraphs.Random Structures Algorithms, 60(2):153–165, 2022

    2022

  2. [10]

    Cooper, A

    C. Cooper, A. Frieze, and B. Reed. Random regular graphs of non-constant degree: con- nectivity and Hamiltonicity.Combin. Probab. Comput., 11(3):249–261, 2002

    2002

  3. [11]

    Das and A

    S. Das and A. Treglown. Ramsey properties of randomly perturbed graphs: cliques and cycles.Combin. Probab. Comput., 29(6):830–867, 2020

    2020

  4. [12]

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

    1952

  5. [13]

    Dragani´ c and P

    N. Dragani´ c and P. Keevash. P´ osa rotation through a random permutation.arXiv preprint arXiv:2502.00489, 2025

    2025

  6. [14]

    Dudek, C

    A. Dudek, C. Reiher, A. Ruci´ nski, and M. Schacht. Powers of Hamiltonian cycles in randomly augmented graphs.Random Structures Algorithms, 56(1):122–141, 2020

    2020

  7. [15]

    Espuny D´ ıaz and A

    A. Espuny D´ ıaz and A. Gir˜ ao. Hamiltonicity of graphs perturbed by a random regular graph.Random Structures Algorithms, 62(4):857–886, 2023. 11

    2023

  8. [16]

    J. R. Faudree, R. J. Faudree, R. J. Gould, M. S. Jacobson, and C. Magnant. Chv´ atal-Erd¨ os type theorems.Discuss. Math. Graph Theory, 30(2):245–256, 2010

    2010

  9. [17]

    J. Han, P. Morris, and A. Treglown. Tilings in randomly perturbed graphs: bridging the gap between Hajnal–Szemer´ edi and Johansson–Kahn–Vu.Random Structures Algorithms, 58(3):480–516, 2021

    2021

  10. [18]

    Han and Y

    J. Han and Y. Zhao. Hamiltonicity in randomly perturbed hypergraphs.J. Combin. Theory Ser. B, 144:14–31, 2020

    2020

  11. [19]

    Joos and J

    F. Joos and J. Kim. Spanning trees in randomly perturbed graphs.Random Structures Algorithms, 56(1):169–219, 2020

    2020

  12. [20]

    R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, editors,Complexity of Computer Computations, pages 85–103. Springer, Boston, MA, 1972

    1972

  13. [21]

    Koml´ os and E

    J. Koml´ os and E. Szemer´ edi. Limit distribution for the existence of Hamiltonian cycles in a random graph.Discrete Math., 43(1):55–63, 1983

    1983

  14. [22]

    A. D. Korˇ sunov. Solution of a problem of P. Erd˝ os and A. R´ enyi on Hamiltonian cycles in undirected graphs.Dokl. Akad. Nauk SSSR, 228(3):529–532, 1976

    1976

  15. [23]

    Krivelevich, M

    M. Krivelevich, M. Kwan, and B. Sudakov. Bounded-degree spanning trees in randomly perturbed graphs.SIAM J. Discrete Math., 31(1):155–171, 2017

    2017

  16. [24]

    Krivelevich, B

    M. Krivelevich, B. Sudakov, V. H. Vu, and N. C. Wormald. Random regular graphs of high degree.Random Structures Algorithms, 18(4):346–363, 2001

    2001

  17. [25]

    McDiarmid

    C. McDiarmid. Concentration. InProbabilistic Methods for Algorithmic Discrete Mathe- matics, volume 16 ofAlgorithms Combin., pages 195–248. Springer, Berlin, 1998

    1998

  18. [26]

    McDowell and R

    A. McDowell and R. Mycroft. Hamiltonℓ-cycles in randomly perturbed hypergraphs. Electron. J. Combin., 25:Paper No. 4.36, 30, 2018

    2018

  19. [27]

    K. Ota. Cycles through prescribed vertices with large degree sum.Discrete Math., 145(1- 3):201–210, 1995

    1995

  20. [28]

    L. P´ osa. Hamiltonian circuits in random graphs.Discrete Math., 14(4):359–364, 1976

    1976

  21. [29]

    R. W. Robinson and N. C. Wormald. Almost all cubic graphs are Hamiltonian.Random Structures Algorithms, 3(2):117–125, 1992

    1992

  22. [30]

    R. W. Robinson and N. C. Wormald. Almost all regular graphs are Hamiltonian.Random Structures Algorithms, 5(2):363–374, 1994

    1994

  23. [31]

    N. C. Wormald. Models of random regular graphs. InSurveys in Combinatorics, 1999, volume 267 ofLondon Math. Soc. Lecture Note Ser., pages 239–298. Cambridge Univ. Press, Cambridge, 1999. 12

    1999

Pith tools

Reviewed June 30, 2026 · model on record in the stance chip above.