P\'osa rotation through a random permutation

Nemanja Dragani\'c; Peter Keevash

REVIEW 1 major objections 3 minor 1 cited by

P\'osa rotation through a random permutation

T0 review · 1 major / 3 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read Adding a random 2-factor makes any sufficiently large graph Hamiltonian once the minimum degree is at least $(1+\varepsilon)\sqrt{n \log n/2}$, and this value is asymptotically best possible.

desk verdict Resolves the asymptotic threshold for Hamiltonicity with a random 2-factor, but the Phase 2 uniform-order claim has a real gap that needs fixing. read the letter →

arxiv 2502.00489 v1 pith:BNN66V65 submitted 2025-02-01 math.CO

Nemanja Draganić , Peter Keevash This is my paper · ORCID

classification math.CO MSC 05C4505C80

keywords Hamiltoncyclesrandom2-factorrandomlyperturbedgraphsminimumdegreethresholdPósarotationpermutationsconcentrationinequalitiesnearlyregular

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 asks how large the minimum degree of a graph $G$ must be before adding a random 2-factor $F$ on the same $n$ vertices almost surely creates a Hamiltonian cycle, a cycle that visits every vertex exactly once. It proves the asymptotic threshold is $(1+o(1))\sqrt{n \log n / 2}$: every graph with minimum degree at least $(1+\varepsilon)\sqrt{n \log n/2}$ becomes Hamiltonian with high probability after adding $F$, while some graph just below that degree fails with high probability. This settles the gap between the earlier lower and upper bounds, $\tfrac{1}{5} \log n$ and $n^{3/4+o(1)}$. If $G$ is nearly regular, the paper shows that a minimum degree of only $\omega(\log^3 n)$ already suffices. The proofs develop a randomised version of classical Pósa rotation adapted to progressive exposure of the random permutation that the 2-factor represents.

What carries the argument

The engine is a randomised form of Pósa rotation, the classical technique that extends a path by rotating its endpoint along unused edges, run in multiple exposure rounds on the random permutation underlying $F$. A random 2-factor is written as $\pi(F^*)$, with $F^*$ a fixed 2-factor with the exposed cycle lengths and $\pi$ uniform. Long cycles are absorbed into the growing path by exposing a short random segment that with high probability contains a neighbour of the current endpoint in $G$. Short cycles are absorbed through 'i-good' ordered pairs $xy$ on the current path, where $x$ is a neighbour in $G$ of the previous endpoint and $y$ is a neighbour in $G$ of the cycle's attachment vertex. The delicate part is the matching $M$ of such pairs: the proof shows that transposing the endpoints of any good pair does not change the set of good pairs, so conditionally all $2^{|M|}$ orders of the pairs along the path are equally likely; this turns the greedy search for correctly ordered pairs into a binomial process with success probability $1/2$. In the nearly regular case the same exposure scheme is powered by 'special vertex sequences', chains of edges of $G$ that respect the order of random intervals, produced by expansion and concentration lemmas.

What would settle it

Run the two-phase process on a large instance, say $n = 10^5$ with $d = 1.1\sqrt{n \log n / 2}$, and count how often Phase 2 exhausts all available good pairs before every short cycle is absorbed; the proof predicts a failure probability of $o(1)$ from a binomial bound, so any non-vanishing failure rate would contradict the upper bound.

Watch

Extended reading notes

Core claim

The central claim is that the minimum degree needed for random 2-factor completion is asymptotically $\sqrt{n \log n / 2}$. For every $\varepsilon>0$ and all sufficiently large $n$, if $G$ has $n$ vertices and minimum degree at least $(1+\varepsilon)\sqrt{n \log n/2}$, then the union $G \cup F$, with $F$ a uniformly random 2-regular graph on the same vertex set, is with high probability Hamiltonian. Conversely, for every $\varepsilon>0$ there is an $n$-vertex graph with minimum degree $(1-\varepsilon)\sqrt{n \log n/2}$ for which $G \cup F$ is with high probability not Hamiltonian, so the constant $\sqrt{1/2}$ is sharp. Under the additional condition that $G$ is nearly regular, meaning $\Delta(G)=O(\delta(G))$, the paper proves that minimum degree $\omega(\log^3 n)$ suffices. It also shows that for random $C_\ell$-factors with $\ell$ at least a large constant depending on $\alpha$, minimum degree $\alpha n$ suffices for every $\alpha>0$.

Load-bearing premise

The load-bearing premise is that a vertex pair's usefulness as a connection depends only on the two labelled vertices and the set of vertices already exposed, not on their order along the growing path; if path order ever mattered, the equally-likely-order step would fail and the final count would not be a binomial variable.

Editorial extensions

If this is right

For every $\varepsilon>0$ and all large $n$, every $n$-vertex graph with minimum degree at least $(1+\varepsilon)\sqrt{n \log n/2}$ becomes Hamiltonian with high probability after adding a random 2-factor.
The threshold is asymptotically exact: there are graphs of minimum degree $(1-\varepsilon)\sqrt{n \log n/2}$ whose union with a random 2-factor is with high probability non-Hamiltonian.
The same conclusions hold if the random perturbation is the graph of a uniformly random permutation instead of a random 2-factor, because loops and parallel edges cannot help in forming a Hamiltonian cycle.
Nearly regular graphs need only a polylogarithmic minimum degree, $\omega(\log^3 n)$, to become Hamiltonian after a random 2-factor.
For random $C_\ell$-factors with $\ell$ large, minimum degree $\alpha n$ suffices for every fixed $\alpha>0$, so the required linear density can be made arbitrarily small.

Reading between the lines

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

The transposition-uniformity mechanism is a general switching principle: any edge-acceptability predicate that depends only on vertex labels and exposed vertices inherits the same all-orderings-equally-likely property, so the multiple-exposure architecture should transfer to other spanning structures such as powers of cycles or $\ell$-factors.
The lower-bound construction suggests the real obstruction is component structure rather than raw edge count: a random 2-factor typically has many short cycles trapped inside the large side of a bipartite split, and the small side cannot connect them. One testable extension is that random $d$-regular perturbations with constant $d>2$ might still have threshold of order $\sqrt{n \log n}$, with a $d
A small computational experiment could test the proof's pivotal step directly: simulate the first exposure phase for moderate $n$, tally the conditional distribution of the $2^{|M|}$ orderings of matched good pairs, and check that it is uniform; any measurable bias would locate a flaw in the binomial step.

Share X Bluesky LinkedIn Reddit HN

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

The headline is that the paper pins down the asymptotic minimum-degree threshold: δ(G) = (1+o(1)) sqrt(n log n/2) guarantees whp Hamiltonicity in G ∪ F with F a random 2-factor, and this is sharp. That is a genuine resolution of an open problem, and the near-regular polylog result is a nice bonus. The proofs are mostly self-contained and use standard concentration machinery; the lower bound construction is clean and the writing is honest about relying on random permutation theory.

What is new: the sharp threshold, improving the prior interval [log n/5, n^{3/4+o(1)}], and the randomized Pósa rotation adapted to multiple exposure. The paper deserves credit for these ideas.

Now the soft spot. The Phase 2 argument claims that transposing the endpoints of any pair xy in the matching M leaves every M_i unchanged, which justifies that all 2^{|M|} orders of the pairs on P0 are equally likely conditional on M. That is only true if no other M-edge lies within the four-vertex window of xy. The definition of M_i only excludes pairs that are i'-good within that window, so two M-edges can sit at positions (j,j+1) and (j+2,j+3): the second pair's window includes the vertex at j+1, which changes label when the first pair is transposed. That changes whether the second pair remains in M. So the conditioning event is not invariant, and the uniform-order property—and with it the binomial model for successes—is not established. This is not a minor typo; it is a load-bearing step in the proof of Theorem 1.1. I suspect it can be repaired, perhaps by strengthening the isolation condition in the definition of M_i or by a more careful orientation-counting argument, but as written the proof has a genuine gap.

Elsewhere the paper is solid: the lower bound, the concentration lemmas, and the near-regular theorem all check out. The self-citation for 'special vertices' is appropriate. The minor typo in Lemma 3.2 doesn't affect the conclusion.

My take: this is an important paper with a credible main theorem, but the Phase 2 gap means it is not ready as-is. A serious referee should see it, and the authors should be asked to tighten that step. If the gap is closable, this will be a strong contribution; if not, the lower bound and the near-regular result may still stand alone.

Referee Report

1 major / 3 minor

Summary. The paper determines the asymptotic minimum-degree threshold for Hamiltonicity of the union of an n-vertex graph G and a random 2-factor F on the same vertex set: the threshold is (1+o(1))√(n log n / 2). Theorem 1.1 gives a positive result for δ(G) ≥ (1+ε)√(n log n/2), Theorem 1.2 gives a matching lower-bound construction, and Theorem 1.3 shows that for nearly regular G, a polylogarithmic minimum degree suffices. The proofs use the random-permutation representation of F, a two-phase Pósa-rotation argument with multiple exposure, and concentration inequalities including Chernoff, McDiarmid, and Talagrand-type bounds for permutations.

Significance. If correct, this resolves the problem posed by Girão and Espuny Díaz, improving the previous interval [log n / 5, n^{3/4+o(1)}] to the sharp threshold. The lower-bound construction is simple and exact, and the upper bound introduces a multiphase exposure framework that is likely to be useful in other randomly perturbed graph problems. The paper is largely self-contained, proving the needed random-permutation facts and concentration lemmas. The main caveat is a gap in the uniform-order property in Phase 2 of Theorem 1.1, which appears repairable but requires restructuring the proof.

major comments (1)

[Section 4, 'Preparation for Phase 2'] The assertion that for any xy ∈ M, transposing x and y in π does not affect any Mi is not a consequence of the stated definition. If M contains two edges xy and zq at consecutive positions (j,j+1) and (j+2,j+3) of P0, then the four-vertex window surrounding zq is {y,z,q,r}; after transposing x and y it becomes {x,z,q,r}. Because i-goodness depends on the labels of the vertices, the set of i′-good ordered pairs in that window can change, so membership of zq in M can change; the matching property only excludes shared vertices, not edges at distance two. The later whp claim that all Yi = 0 does rule out such adjacent M-edges, since the endpoint z of zq would be an unexposed neighbour of b_{i′−1} or a_{i′} in the window of xy, but this is proved after the invariance assertion is used. To make the binomial model for X in Phase 2 rigorous, the proof should first define and condition on the whp event from the Yi calculation, then prove that M is 2-separated on that event, and only then derive the transposition invariance and the uniform-order property for pairs in M.

minor comments (3)

[Section 4, Phase 1] The displayed estimate '∼ d(√n log n)/n = Ω(log^{3/2} n)' is arithmetically incorrect; the quantity is Θ(log n). The argument still works with a union bound over the O(log n) long cycles, but the exponent should be corrected.
[Section 4, Preparation for Phase 2] In the sentence 'the conditional distribution of π given M1, . . . , Mk', the list should run to M_{k+1}, since the final Hamilton-cycle step is included in the argument.
[Section 4, Preparation for Phase 2] The phrase 'the only ordered pairs that are i′-good for some i′ ∈ [k+1]' is ambiguous: it should be stated explicitly whether the local-uniqueness witness i′ may depend on the edge, and the later argument should use the same index for the adjacent-edge exclusion.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the derivation is self-contained and the only self-citation is a non-load-bearing definitional reference.

full rationale

The paper's central theorems are proved from explicit concentration inequalities (Chernoff, McDiarmid/Azuma, Talagrand for permutations) and from lemmas proved internally in Sections 3--5. Theorem 1.1 establishes an asymptotic minimum-degree threshold and proves a whp Hamiltonicity statement without fitting any parameter to the desired conclusion; no 'prediction' is renamed from an input. Theorem 1.2 is a separate lower-bound construction using direct moment estimates, not derived from the claim it tests. The only self-citation is [12], used in Section 5 for the terminology 'special vertices'; the definition is reproduced in the paper and Lemma 5.1 proves the needed existence using the paper's own concentration and expansion lemmas, so this citation is not load-bearing. The 'uniform-order property' in Phase 2 is asserted as a consequence of the constructed matching M and the conditional distribution of the random permutation; even if a correctness objection to that assertion were raised, it is not a circularity, because the assertion is not imported from the theorem being proved or from a fitted input. Overall, the paper is self-contained against external benchmarks and exhibits no definitional circularity, no fitted-input-as-prediction, and no load-bearing self-citation chain.

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

The proofs rest on standard concentration inequalities and elementary random-permutation facts; no free parameters are fitted and no new entities are postulated. The only overlap with the authors' prior work is the definition of 'special vertices' from [12], but Lemma 5.1 is proved in the paper.

assumptions (4)

standard math Chernoff bounds for binomial and hypergeometric random variables
Invoked throughout Section 3 and the proofs of Theorems 1.1 and 1.3, e.g., in Lemma 3.2 and Lemma 3.4.
standard math McDiarmid's bounded differences inequality (Azuma's inequality)
Used in Lemma 3.4 to prove expansion of the neighbourhood of a random set.
standard math Talagrand's concentration inequality for random permutations (McDiarmid's simplified form [30])
Used in Lemma 3.6 to lower bound the number of good consecutive pairs on the random path.
domain assumption Identification of a random 2-factor with a random permutation conditioned on having no cycles of length 1 or 2
Stated in the introduction and used throughout; it is a standard model fact and is partially justified by Lemma 2.1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of P\'osa rotation through a random permutation." pith.science (2026). https://pith.science/paper/BNN66V65

@misc{pith2026250200489,
  author       = {Pith},
  title        = {Pith review of: P\'osa rotation through a random permutation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BNN66V65}},
  note         = {Machine review of arXiv:2502.00489}
}

abstract

What minimum degree of a graph $G$ on $n$ vertices guarantees that the union of $G$ and a random $2$-factor (or permutation) is with high probability Hamiltonian? Gir\~ao and Espuny D{\'\i}az showed that the answer lies in the interval $[\tfrac15 \log n, n^{3/4+o(1)}]$. We improve both the upper and lower bounds to resolve this problem asymptotically, showing that the answer is $(1+o(1))\sqrt{n\log n/2}$. Furthermore, if $G$ is assumed to be (nearly) regular then we obtain the much stronger bound that any degree growing at least polylogarithmically in $n$ is sufficient for Hamiltonicity. Our proofs use some insights from the rich theory of random permutations and a randomised version of the classical technique of P\'osa rotation adapted to multiple exposure arguments.

Figures

Figures reproduced from arXiv: 2502.00489 by the authors.

**Figure 1.** Using a good pair to incorporate a short cycle C in the current path P. Proof of Theorem 1.1. Let G be an n-vertex graph with δ(G) = d = (1 + ε)(p n log n/2), where ε > 0 is small and n > n0(ε) is large. Let F ∼ Gn,2 be a random 2-regular graph on the same vertex set as G. We want to show that whp G ∪ F is Hamiltonian. By Lemma 2.1, whp F has (1 + o(1)) log n cycles, of which ( 1 2 + o(1)) log n are short (of length… view at source ↗

**Figure 2.** A sequence v1 < . . . < v5 of special vertices. The following lemma will be used to incorporate cycles into the path; the intended use (see [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Incorporating the cycle C2 into the long path on V (C1). The new path starts at v − 2 , following the blue and green paths and then the intervals I2, I3, . . . , Ik. In the next step, v − 2 plays the role of v1 and we find the special vertices in I2. Proof of Theorem 1.3. Let G be an n-vertex graph with δ(G) = ω(log3 n) and ∆(G) = O(δ(G)). Let F ∼ Gn,2 be a random 2-regular graph on V (G). We condition on the length… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Hamilton cycles in regular graphs perturbed by a random 2-factor
math.CO 2025-06 conditional novelty 7.0 of 10

For every integer d ≥ 2, the union of any d-regular graph on n vertices with a uniformly random 2-factor is Hamiltonian with high probability.

Reference graph

Works this paper leans on

35 extracted references · 32 canonical work pages · cited by 1 Pith paper

[1]

Ajtai, J

M. Ajtai, J. Koml´ os, and E. Szemer´ edi. First occurrenc e of Hamilton cycles in random graphs. North-Holland Math. Stud. , 115(C):173–178, 1985

work page 1985
[2]

Bohman, A

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

work page 2003
[3]

Bollob´ as

B. Bollob´ as. The evolution of sparse graphs. In Graph theory and combinatorics (Cambridge, 1983) , pages 35–57, 1984

work page 1983
[4]

Bollob´ as, T

B. Bollob´ as, T. I. Fenner, and A. M. Frieze. An algorithm for ﬁnding Hamilton paths and cycles in random graphs. Combinatorica, 7:327–341, 1987

work page 1987
[5]

Cambridge University Press, 2001

B´ ela Bollob´ as.Random graphs (2nd ed.) . Cambridge University Press, 2001

work page 2001
[6]

Chv´ atal and P

V. Chv´ atal and P. Erd˝ os. A note on Hamiltonian circuits . Discrete Math., 2(2):111–113, 1972

work page 1972
[7]

On Hamilton’s ideals.Journal of Combinatorial Theory, Series B , 12(2):163–168, 1972

V´ aclav Chv´ atal. On Hamilton’s ideals.Journal of Combinatorial Theory, Series B , 12(2):163–168, 1972

work page 1972
[8]

Random regula r graphs of non-constant degree: con- nectivity and Hamilton cycles

Colin Cooper, Alan Frieze, and Bruce Reed. Random regula r graphs of non-constant degree: con- nectivity and Hamilton cycles. Combinatorics, Probability and Computing , 11(3):249–262, 2002

work page 2002

Show all 35 references

[9]

Csaba, D

B. Csaba, D. K¨ uhn, A. Lo, D. Osthus, and A. Treglown. Proo f of the 1-factorization and Hamilton decomposition conjectures. Mem. Amer. Math. Soc. , 244(monograph 1154):164, 2016

2016
[10]

Cuckler and J

B. Cuckler and J. Kahn. Hamiltonian cycles in Dirac grap hs. Combinatorica, 29:299–326, 2009

2009
[11]

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

1952
[12]

Pancyclicity of Hamiltonian graphs

Nemanja Dragani´ c, David Munh´ a Correia, and Benny Sudakov. Pancyclicity of Hamiltonian graphs. arXiv preprint arXiv:2209.03325 , 2022

2022 arXiv
[13]

Hamiltonicity of expanders: optimal bounds and ap plications

Nemanja Dragani´ c, Richard Montgomery, David Munh´ a C orreia, Alexey Pokrovskiy, and Benny Sudakov. Hamiltonicity of expanders: optimal bounds and ap plications. arXiv preprint arXiv:2402.06603, 2024

2024 arXiv
[14]

Open problem section

Alberto Espuny D ´ ıaz. Open problem section. Novi Sad FOCS Workshop , 2024

2024
[15]

Hamiltonicity of graphs perturbed by a random regular graph

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

2023
[16]

Ferber, E

A. Ferber, E. Long, and B. Sudakov. Counting Hamilton de compositions of oriented graphs. Int. Math. Res. Not. IMRN , 2018:6908–6933, 2017

2018
[17]

Hamilton cycles in the union of random perm utations

Alan Frieze. Hamilton cycles in the union of random perm utations. Random Structures & Algorithms , 18(1):83–94, 2001

2001
[18]

R. J. Gould. Recent advances on the Hamiltonian problem : Survey iii. Graphs Combin. , 30:1–46, 2014

2014
[19]

Ham ilton cycles in highly connected and expand- ing graphs

Dan Hefetz, Michael Krivelevich, and Tibor Szab´ o. Ham ilton cycles in highly connected and expand- ing graphs. Combinatorica, 29(5):547–568, 2009

2009
[20]

Hamilton cycles in regular 2-connected g raphs

Bill Jackson. Hamilton cycles in regular 2-connected g raphs. Journal of Combinatorial Theory, Series B, 29(1):27–46, 1980

1980
[21]

Random graphs

Svante Janson, Tomasz Luczak, and Andrzej Rucinski. Random graphs. John Wiley & Sons, 2011

2011
[22]

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
[23]

Krivelevich

M. Krivelevich. The critical bias for the Hamiltonicit y game is (1 + o(1)). J. Amer. Math. Soc. , 24(1):125–131, 2011

2011
[24]

Krivelevich, C

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

2014
[25]

Krivelevich, B

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

2001
[26]

Sparse pseudo- random graphs are Hamiltonian

Michael Krivelevich and Benny Sudakov. Sparse pseudo- random graphs are Hamiltonian. Journal of Graph Theory, 42(1):17–33, 2003

2003
[27]

K¨ uhn and D

D. K¨ uhn and D. Osthus. Hamilton decompositions of regu lar expanders: a proof of Kelly’s conjecture for large tournaments. Adv. Math., 237:62–146, 2013

2013
[28]

K¨ uhn and D

D. K¨ uhn and D. Osthus. Hamilton cycles in graphs and hyp ergraphs: an extremal perspective. In Proceedings of the International Congress of Mathematicians , Seoul, Korea. , volume 4, pages 381– 406, 2014

2014
[29]

Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments

Daniela K¨ uhn, John Lapinskas, Deryk Osthus, and Vires h Patel. Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments. Proceedings of the London Mathematical Soci- ety, 109(3):733–762, 2014

2014
[30]

Concentration for independent permu tations

Colin McDiarmid. Concentration for independent permu tations. Combinatorics, Probability and Computing, 11(2):163–178, 2002

2002
[31]

Edge-disjoint Hamiltonian circ uits in graphs with vertices of large valency

C St JA Nash-Williams. Edge-disjoint Hamiltonian circ uits in graphs with vertices of large valency. In Studies in Pure Mathematics (Presented to Richard Rado) , pages 157–183. Academic Press London, 1971

1971
[32]

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

1976
[33]

Almost all cub ic graphs are Hamiltonian

Robert W Robinson and Nicholas C Wormald. Almost all cub ic graphs are Hamiltonian. Random Structures & Algorithms , 3(2):117–125, 1992

1992
[34]

Almost all reg ular graphs are Hamiltonian

Robert W Robinson and Nicholas C Wormald. Almost all reg ular graphs are Hamiltonian. Random Structures & Algorithms , 5(2):363–374, 1994

1994
[35]

Hamilton cycl es containing randomly selected edges in random regular graphs

Robert W Robinson and Nicholas C Wormald. Hamilton cycl es containing randomly selected edges in random regular graphs. Random Structures & Algorithms , 19(2):128–147, 2001. 11

2001

Pith tools

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

[1] [1]

Ajtai, J

M. Ajtai, J. Koml´ os, and E. Szemer´ edi. First occurrenc e of Hamilton cycles in random graphs. North-Holland Math. Stud. , 115(C):173–178, 1985

work page 1985

[2] [2]

Bohman, A

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

work page 2003

[3] [3]

Bollob´ as

B. Bollob´ as. The evolution of sparse graphs. In Graph theory and combinatorics (Cambridge, 1983) , pages 35–57, 1984

work page 1983

[4] [4]

Bollob´ as, T

B. Bollob´ as, T. I. Fenner, and A. M. Frieze. An algorithm for ﬁnding Hamilton paths and cycles in random graphs. Combinatorica, 7:327–341, 1987

work page 1987

[5] [5]

Cambridge University Press, 2001

B´ ela Bollob´ as.Random graphs (2nd ed.) . Cambridge University Press, 2001

work page 2001

[6] [6]

Chv´ atal and P

V. Chv´ atal and P. Erd˝ os. A note on Hamiltonian circuits . Discrete Math., 2(2):111–113, 1972

work page 1972

[7] [7]

On Hamilton’s ideals.Journal of Combinatorial Theory, Series B , 12(2):163–168, 1972

V´ aclav Chv´ atal. On Hamilton’s ideals.Journal of Combinatorial Theory, Series B , 12(2):163–168, 1972

work page 1972

[8] [8]

Random regula r graphs of non-constant degree: con- nectivity and Hamilton cycles

Colin Cooper, Alan Frieze, and Bruce Reed. Random regula r graphs of non-constant degree: con- nectivity and Hamilton cycles. Combinatorics, Probability and Computing , 11(3):249–262, 2002

work page 2002