Finding Planted Cycles in a Random Graph

Colin Sandon; Dana Yang; Jiaming Xu; Julia Gaudio

REVIEW 1 major objections 4 minor 26 references

Finding Planted Cycles in a Random Graph

T0 review · 1 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read In the planted cycles model, almost exact recovery succeeds exactly below a sharp threshold—and a polynomial-time algorithm attains it; above the threshold, recovery is impossible.

desk verdict Sharp threshold result is likely correct, but the polynomial-time claim has a missing upper bound on |H| and needs a patch. read the letter →

arxiv 2511.04058 v2 pith:GZWQZES4 submitted 2025-11-06 math.ST math.PRstat.TH

Julia Gaudio , Colin Sandon , Jiaming Xu , Dana Yang This is my paper · ORCID

classification math.STmath.PRstat.TH MSC 05C8060C0560J80

keywords randomgraphsplantedcyclesphasetransitionsalmostexactrecoverygeneratingfunctionsbranchingprocesses2-factorErdős–Rényi

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

The paper studies a random graph model in which a hidden collection of vertex-disjoint cycles (a 2-factor) is planted on a randomly chosen δn vertices of an Erdős–Rényi graph with edge probability λ/n. It identifies a single constant threshold, λ* = 1/(√(2δ)+√(1−δ))², that separates two regimes. Below λ*, every 2-factor close to the planted one can be recovered up to a vanishing fraction of edges, and the paper gives a polynomial-time greedy algorithm that does so. Above λ*, no algorithm—however powerful—can do better than constant error. The result is a sharp threshold with no gap between statistical possibility and computational tractability, in contrast to the planted clique problem.

What carries the argument

The difference graph between the planted 2-factor and any competing 2-factor decomposes into alternating (a,b)-circuits via a black-box theorem on alternating Eulerian circuits. The generating function g(x,y) = Σ_{k≥1} (2x/(1−x) · δλy/(1−(1−δ)λy))^k counts the expected number of such trails; convergence of this series on the curve xy=1 with 0<x<1<y decides the threshold. For the impossibility direction, a branching process built from (m*,m*)-paths with mean offspring greater than 1 constructs exponentially many balanced cycles, which are then stitched into many competing 2-factors.

What would settle it

Simulate the model at δ=2/3 with λ slightly below and above 1/3, and compute the minimum achievable symmetric difference over all 2-factors (or run the paper's algorithm). The claim predicts an abrupt transition from error o(1) to error Ω(1) exactly at λ=1/3, with polynomial-time success below the threshold. A direct count of balanced (a,a)-circuits in the observed graph should show bounded expectation below the threshold and divergence above it.

Watch

Extended reading notes

Core claim

The central discovery is a sharp phase transition for almost exact recovery of a planted 2-factor in an Erdős–Rényi background graph. The threshold is derived from a generating function that counts alternating trails between planted and unplanted edges in the difference graph H*ΔH; convergence of this generating function is equivalent to λ < λ* and guarantees few balanced circuits, while divergence forces exponentially many balanced long cycles that make recovery impossible. The same threshold is achieved by a polynomial-time algorithm, so there is no statistical–computational gap.

Load-bearing premise

The entire proof rests on a black-box theorem asserting that every connected component of the difference graph H*ΔH admits an Eulerian circuit whose edge colors alternate at every shared vertex; if that decomposition fails for the degree-2 and degree-4 colored vertices that arise, the sharp-threshold derivation loses its foundation.

Editorial extensions

If this is right

The sharp threshold holds conditionally on the planted 2-factor being a single Hamiltonian cycle, so the result covers the single-cycle version of the problem.
There is no statistical–computational gap: the information-theoretic threshold and the polynomial-time threshold coincide exactly.
Exact recovery of the planted cycles is impossible for any constant λ, so almost exact recovery is the correct target.
The threshold is non-monotonic in δ, maximized as δ→0 and minimized at δ=2/3, and is always below the threshold one would get if the planted vertex set were known.
The greedy trail-XOR algorithm runs in time O(n^{3+log(2+λ)}) with high probability.
The generating-function method provides a unified way to count both balanced and imbalanced circuits, going beyond the simpler alternating-circuit analysis that suffices when δ=1.

Reading between the lines

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

If the threshold formula is correct, the critical behavior just below λ* deserves attention: the generating function suggests that the expected number of balanced circuits diverges critically near the threshold, hinting at an infinite-order phase transition analogous to the planted matching problem.
The machinery likely extends to planted k-factors for k≥3, where the transition may be driven by the appearance of competing k-factors rather than 2-factors; the k=1 planted partial matching case is known to have no sharp transition.
The comparison with the known-vertex-set threshold suggests that the main statistical difficulty comes from discovering the support of the planted cycles; isolating this effect by conditioning on the vertex set would sharpen the intuition about why the unknown-support problem is harder.
A natural testable extension is the partial-recovery regime above λ*: the paper leaves open whether a 'something' phase exists for δ<1, since for δ=1 partial recovery is trivially achievable.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

You should know this paper before recommending it: the information-theoretic threshold for planted 2-factor recovery looks right and is a genuine advance, but the proof of the polynomial-time half has a hole that the authors may be able to patch. Theorem 1.1 claims both a sharp threshold and an efficient algorithm with no statistical-computational gap. The threshold for δ<1 (unknown vertex support) is new, and the generating-function characterization in §2 is elegant. The achievability proof (Theorem 2.4) is self-contained and convincing: the two-parameter generating function in (2.4) and the elementary algebra in Lemma 2.3 cleanly identify the threshold. The impossibility proof (§3) is heavy but follows a known branching-process-plus-sprinkling template, and I see no red flags there beyond the usual complexity. So the information-theoretic result is in good shape.

The soft spot is Theorem 4.1. Lemma 4.3, the statistical engine for the algorithm, assumes E[|H|] = δn − o(n) — an upper bound as well as a lower bound. Lemma 4.4 only proves |H| ≥ δn − O(n/√log n) and bounds the number of degree-1 vertices; nowhere does the paper prove |H| ≤ δn + o(n). Since the algorithm only XORs trails that increase |H|, it can overshoot, and absorbing unplanted paths or small cycles would make |H| larger than δn by a constant fraction. If that happens, Lemma 4.3 doesn't apply and E[|HΔH*|] ≥ Ω(n). The text simply jumps from Lemma 4.4 to Theorem 4.1. This is a missing support in the algorithmic half. It is not fatal to the threshold itself, but it means the "no computational-statistical gap" headline is not yet proven as written. A patch might come from subcriticality (background graph has O(1) cycles, so overshoot may be o(n)), but that argument is not in the paper. The Kotzig concern flagged earlier is satisfiable — the label classes in Lemma 2.1 are at most half the degree, so [16] applies.

Who should read this: anyone working on planted structures in sparse random graphs will want the threshold and the generating function technique. It deserves a serious referee, but I'd send it back for major revision rather than accept as is. If the authors close the |H| upper bound, this becomes a strong paper.

Referee Report

1 major / 4 minor

Summary. The paper studies the planted cycles model G(n, λ, δ), where a uniformly random set of δn vertices carries a uniformly random 2-factor H*, and all remaining pairs are present independently with probability λ/n. The main result, Theorem 1.1, asserts a sharp almost-exact-recovery threshold at λ_c = (√(2δ)+√(1−δ))^{−2}: below λ_c, almost exact recovery is possible and is achieved by a polynomial-time algorithm; above λ_c, no estimator can do better than constant error. The proof has three parts: a generating-function count of alternating (a,b)-trails to prove achievability (§2); a branching-process and sprinkling construction of many balanced cycles to prove impossibility (§3); and a greedy algorithm based on short trails to prove the algorithmic claim (§4).

Significance. If the results are correct, this is a substantial contribution: a sharp information-theoretic threshold for recovery of a planted 2-factor with unknown support, and—strikingly—no statistical–computational gap, in contrast to the planted clique problem. The generating-function technique for counting alternating trails is elegant and self-contained, and the impossibility argument via path trees and sprinkling is technically sophisticated. The algorithmic section is also ambitious: it gives a concrete polynomial-time procedure with a detailed structural analysis. The main theorem, however, is not yet fully established because of a gap in the proof of the algorithmic half.

major comments (1)

[Theorem 4.1 / Lemmas 4.3–4.4] Lemma 4.4 only proves a lower bound on the output size, |H| ≥ δn − O(n/√log n), together with a bound on the number of degree-1 vertices. Lemma 4.3, which is the statistical engine for the efficient estimator, requires the stronger assumption E[|H|] = δn − o(n). No matching upper bound on |H| is supplied. The algorithm's updates search over all short trails in G, not only over trails contained in HΔH*, so after H reaches the desired size it can in principle absorb unplanted paths: a cost-free update can add an unplanted path joining two degree-1 vertices of H, increasing |H| without increasing the number of degree-1 vertices, and a cost-effective update can add a new unplanted path of length at least √log n. The degree-1 budget in Lemma 4.4 does not rule out Ω(n) overshoot, because each cost-effective update can add up to log n edges and there are up to n/√log n such updates. Thus the pr

minor comments (4)

[Theorem B.1] The parameter order is inconsistent: the statement reads G∼G(n, δ, λ), while the model in Definition 1.1 is G(n, λ, δ).
[Lemma 3.9] In the proof of Lemma 3.9, the text refers to “Proposition 3.8” when the statement cited is Lemma 3.8.
[Algorithm 1] The pruning condition says “reachable by a path of length at most 2m*”, while the path layers are non-shortcutted (m*,m*)-paths of length exactly 2m*. Please clarify whether the pruning radius is intentionally larger than the path length, and reconcile with the domination argument in Lemma 3.8.
[Definition 1.1] “choose a set of δn2 vertices” appears to be a typo for “δn vertices”; the surrounding text and the exponent in the abstract use δn.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sharp threshold is derived from the planted model's generating function, and the self-citations are not load-bearing.

full rationale

The central claim (Theorem 1.1) is not circular. The threshold is obtained by solving the convergence/divergence condition of the generating function g(x,y) in (2.4); the coefficients c_{a,b} are model-derived expected trail counts from Lemma 2.2, not fit parameters. Achievability (Theorem 2.4) bounds the expected excess directly from this generating function, and impossibility (Lemma 3.4) proves c_{m*,m*}>1 from the same divergence, then builds supercritical trees with mean μ=(c_{m*,m*}+1)/2; no quantity is trained on the target. The paper cites its own prior work [13] for the δ=1 special case and technical analogies (e.g., 'similar in spirit to the proof of [13, Theorem 2.3]' and Eq. (3.4)), and [9, Lemma 7] is used as a black-box, parameter-free sprinkling lemma whose assumptions do not include the target recovery threshold; these are independent evidence, not circular inputs. The algorithmic proof has a separate gap that is not circularity: Lemma 4.4 proves only a lower bound |H| ≥ δn−O(n/√logn) and a degree-1 bound, while Lemma 4.3 needs E[|H|] = δn−o(n); no matching upper bound is supplied. This is a correctness concern, not a reduction of a prediction to its input.

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

The central claim rests on the generative model (independent background edges, uniform planted 2-factor), two published black-box theorems (Kotzig; [9, Lemma 7]), and the standard machinery of generating functions and branching processes. No free parameters are fitted to data. No invented entities are introduced; proof constructs such as path trees and reserved edges are internal tools, not entities with independent evidential status.

assumptions (3)

standard math Kotzig's theorem [16, Thm. 1]: any connected even graph with a partition of incident edges satisfying |Q_{v,i}| ≤ deg(v)/2 admits an Eulerian circuit whose consecutive edges have different labels at every vertex.
Used in Lemma 2.1 to decompose H*ΔH into alternating (a,b)-circuits, and again in Lemma 4.2 for the trail decomposition; this is the structural foundation of both achievability and impossibility proofs.
standard math Lemma 7 of [9] (Ding–Wu–Xu–Yang): a bi-colored bipartite graph on [k]×[k]' with a perfect red matching and independent blue edges of probability D/k (D ≥ 256 log(32e)) contains exp(k/20) alternating cycles of length ≥3k/4 with probability 1−exp(−Dk/214).
Used as a black box in Lemma 3.10 to convert many two-sided trees into many balanced cycles, which is the engine of the impossibility theorem.
domain assumption Generative model: background G0 ~ G(n,λ/n) independent edges; uniform δn-subset V; H* a uniform labeled 2-factor on V; λ,δ constants as n→∞.
The entire analysis is asymptotic in n for fixed λ,δ; the threshold depends on these parameters. Any deviation from this generative model would invalidate the result, but this is the stated problem, not an unstated premise.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Finding Planted Cycles in a Random Graph." pith.science (2026). https://pith.science/paper/GZWQZES4

@misc{pith2026251104058,
  author       = {Pith},
  title        = {Pith review of: Finding Planted Cycles in a Random Graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GZWQZES4}},
  note         = {Machine review of arXiv:2511.04058}
}

abstract

In this paper, we study the problem of finding a collection of planted cycles in an \ER random graph $G \sim \mathcal{G}(n, \lambda/n)$, in analogy to the famous Planted Clique Problem. When the cycles are planted on a uniformly random subset of $\delta n$ vertices, we show that almost-exact recovery (that is, recovering all but a vanishing fraction of planted-cycle edges as $n \to \infty$) is information-theoretically possible if $\lambda < \frac{1}{(\sqrt{2 \delta} + \sqrt{1-\delta})^2}$ and impossible if $\lambda > \frac{1}{(\sqrt{2 \delta} + \sqrt{1-\delta})^2}$. Moreover, despite the worst-case computational hardness of finding long cycles, we design a polynomial-time algorithm that attains almost exact recovery when $\lambda < \frac{1}{(\sqrt{2 \delta} + \sqrt{1-\delta})^2}$. This stands in stark contrast to the Planted Clique Problem, where a significant computational-statistical gap is widely conjectured.

Figures

Figures reproduced from arXiv: 2511.04058 by the authors.

**Figure 1.** An example where H∗ is a 4-cycle with red solid edges, H is a 4-cycle with blue dashed edges, and H∗∆H has a (3, 3)-Eulerian circuit. In light of Lemma 2.1, H∗∆H can be represented as a vertex-disjoint union of a certain class of circuits. To specify that class of circuits, we introduce the definition of (a, b)-circuit, or more generally, (a, b)-trail. See [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 2.** A schematic representation of a path tree with a depth of [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗

**Figure 3.** The solid purple line represents a path of length strictly less than [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Five edge construction (reproduced from [13]). [PITH_FULL_IMAGE:figures/full_fig_p021_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 1 linked inside Pith

[16]

Moves without forbidden transitions in a graph.Matematick` y Časopis, 18(1):76–80, 1968

Anton Kotzig. Moves without forbidden transitions in a graph.Matematick` y Časopis, 18(1):76–80, 1968

1968
[1]

Finding a large hidden clique in a random graph.Random Structures & Algorithms, 13(3-4):457–466, 1998

Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph.Random Structures & Algorithms, 13(3-4):457–466, 1998

1998
[2]

Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs

Noga Alon, Raphy Yuster, and Uri Zwick. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. InProceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, pages 326–335, 1994

1994
[3]

A note on long cycles in sparse random graphs.Electronic Journal of Combinatorics, 30(2), 2023

Michael Anastos. A note on long cycles in sparse random graphs.Electronic Journal of Combinatorics, 30(2), 2023

2023
[4]

A scaling limit for the length of the longest cycle in a sparse random graph

Michael Anastos and Alan Frieze. A scaling limit for the length of the longest cycle in a sparse random graph. Journal of Combinatorial Theory, Series B, 148:184–208, 2021

2021
[5]

A nearly tight sum-of-squares lower bound for the planted clique problem.SIAM Journal on Computing, 48(2):687–735, 2019

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem.SIAM Journal on Computing, 48(2):687–735, 2019

2019
[6]

Springer, 1998

Béla Bollobás.Random Graphs. Springer, 1998

1998
[7]

Long cycles in sparse random graphs.Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, pages 59–64, 1984

Béla Bollobás, TI Fenner, and AM Frieze. Long cycles in sparse random graphs.Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, pages 59–64, 1984

1983

Show all 26 references

[8]

Statistical and computational phase transitions in group testing

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein, and Ilias Zadik. Statistical and computational phase transitions in group testing. InConference on Learning Theory, pages 4764–4781. PMLR, 2022

2022
[9]

The planted matching problem: Sharp threshold and infinite-order phase transition.Probability Theory and Related Fields, pages 1–71, 2023

Jian Ding, Yihong Wu, Jiaming Xu, and Dana Yang. The planted matching problem: Sharp threshold and infinite-order phase transition.Probability Theory and Related Fields, pages 1–71, 2023

2023
[10]

Richard Durrett.Random Graph Dynamics, volume 200. 2007

2007
[11]

On the evolution of random graphs.Publ

Paul Erdős and Alfréd Rényi. On the evolution of random graphs.Publ. Math. Inst. Hungar. Acad. Sci, 5:17–61, 1960

1960
[12]

On large matchings and cycles in sparse random graphs.Discrete Mathematics, 59(3):243–256, 1986

Alan M Frieze. On large matchings and cycles in sparse random graphs.Discrete Mathematics, 59(3):243–256, 1986

1986
[13]

All-Something-Nothing

Julia Gaudio, Colin Sandon, Jiaming Xu, and Dana Yang. “All-Something-Nothing” phase transitions in planted k-factor recovery.arXiv preprint arXiv:2503.08984, 2025

2025 arXiv
[14]

Large cliques elude the metropolis process.Random Structures & Algorithms, 3(4):347–359, 1992

Mark Jerrum. Large cliques elude the metropolis process.Random Structures & Algorithms, 3(4):347–359, 1992

1992
[15]

The probabilistic analysis of some combinatorial search algorithms

Richard M Karp. The probabilistic analysis of some combinatorial search algorithms. InAlgorithms and complexity: New Directions and Recent Results, 1976

1976
[17]

Long paths and cycles in random subgraphs of graphs with large minimum degree.Random Structures & Algorithms, 46(2):320–345, 2015

Michael Krivelevich, Choongbum Lee, and Benny Sudakov. Long paths and cycles in random subgraphs of graphs with large minimum degree.Random Structures & Algorithms, 46(2):320–345, 2015

2015
[18]

Expected complexity of graph partitioning problems.Discrete Applied Mathematics, 57(2-3):193– 212, 1995

Luděk Kučera. Expected complexity of graph partitioning problems.Discrete Applied Mathematics, 57(2-3):193– 212, 1995

1995
[19]

Detection-recovery gap for planted dense cycles

Cheng Mao, Alexander S Wein, and Shenduo Zhang. Detection-recovery gap for planted dense cycles. InThe Thirty Sixth Annual Conference on Learning Theory, pages 2440–2481. PMLR, 2023. 32

2023
[20]

Information-theoretic thresholds for planted dense cycles

Cheng Mao, Alexander S Wein, and Shenduo Zhang. Information-theoretic thresholds for planted dense cycles. IEEE Transactions on Information Theory, 2024

2024
[21]

The planted matching problem: Phase transitions and exact results.The Annals of Applied Probability, 31(6):2663–2720, 2021

Mehrdad Moharrami, Cristopher Moore, and Jiaming Xu. The planted matching problem: Phase transitions and exact results.The Annals of Applied Probability, 31(6):2663–2720, 2021

2021
[22]

Sharp thresholds in inference of planted subgraphs

Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, and Ilias Zadik. Sharp thresholds in inference of planted subgraphs. InThe Thirty Sixth Annual Conference on Learning Theory, pages 5573–5577. PMLR, 2023

2023
[23]

The All-or-Nothing phenomenon in sparse tensor PCA.Advances in Neural Information Processing Systems, 33:17674–17684, 2020

Jonathan Niles-Weed and Ilias Zadik. The All-or-Nothing phenomenon in sparse tensor PCA.Advances in Neural Information Processing Systems, 33:17674–17684, 2020

2020
[24]

The all-or-nothing phenomenon in sparse linear regression.Mathe- matical Statistics and Learning, 3(3):259–313, 2021

Galen Reeves, Jiaming Xu, and Ilias Zadik. The all-or-nothing phenomenon in sparse linear regression.Mathe- matical Statistics and Learning, 3(3):259–313, 2021

2021
[25]

On the All-or-Nothing behavior of Bernoulli group testing.IEEE Journal on Selected Areas in Information Theory, 1(3):669–680, 2020

Lan V Truong, Matthew Aldridge, and Jonathan Scarlett. On the All-or-Nothing behavior of Bernoulli group testing.IEEE Journal on Selected Areas in Information Theory, 1(3):669–680, 2020

2020
[26]

Yihong Wu, Jiaming Xu, and Sophie H. Yu. Settling the sharp reconstruction thresholds of random graph matching.IEEE Transactions on Information Theory, 68(8):5391–5417, 2022. 33

2022

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [16]

Moves without forbidden transitions in a graph.Matematick` y Časopis, 18(1):76–80, 1968

Anton Kotzig. Moves without forbidden transitions in a graph.Matematick` y Časopis, 18(1):76–80, 1968

1968

[2] [1]

Finding a large hidden clique in a random graph.Random Structures & Algorithms, 13(3-4):457–466, 1998

Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph.Random Structures & Algorithms, 13(3-4):457–466, 1998

1998

[3] [2]

Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs

Noga Alon, Raphy Yuster, and Uri Zwick. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. InProceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, pages 326–335, 1994

1994

[4] [3]

A note on long cycles in sparse random graphs.Electronic Journal of Combinatorics, 30(2), 2023

Michael Anastos. A note on long cycles in sparse random graphs.Electronic Journal of Combinatorics, 30(2), 2023

2023

[5] [4]

A scaling limit for the length of the longest cycle in a sparse random graph

Michael Anastos and Alan Frieze. A scaling limit for the length of the longest cycle in a sparse random graph. Journal of Combinatorial Theory, Series B, 148:184–208, 2021

2021

[6] [5]

A nearly tight sum-of-squares lower bound for the planted clique problem.SIAM Journal on Computing, 48(2):687–735, 2019

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem.SIAM Journal on Computing, 48(2):687–735, 2019

2019

[7] [6]

Springer, 1998

Béla Bollobás.Random Graphs. Springer, 1998

1998

[8] [7]

Long cycles in sparse random graphs.Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, pages 59–64, 1984

Béla Bollobás, TI Fenner, and AM Frieze. Long cycles in sparse random graphs.Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, pages 59–64, 1984

1983