Efficient Hamilton covers and linear arboricity of random graphs

Michael Krivelevich; Nemanja Dragani\'c

REVIEW 2 major objections 5 minor 36 references

Efficient Hamilton covers and linear arboricity of random graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read With high probability, a binomial random graph whose edge probability ranges from the Hamiltonicity threshold to 1−ω(n)/n² has all its edges covered by exactly ⌈Δ(G)/2⌉ Hamilton cycles.

desk verdict A substantial paper that plausibly closes the Hamilton-cover and linear-arboricity problems for random graphs; the sparse-range construction is the real new work, and the main results look correct, with a few rough edges that a careful referee should smooth out. read the letter →

arxiv 2607.14881 v1 pith:NIBFG7I3 submitted 2026-07-16 math.CO

Nemanja Draganić , Michael Krivelevich This is my paper

classification math.CO MSC 05C8005C4505C70

keywords HamiltoncoverrandomgraphG(np)tightlineararboricityHamiltonicitythresholdforestshittingtimeexpanders

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 proves that the maximum-degree lower bound is the only obstruction to covering all edges of a random graph by Hamilton cycles: with high probability, G(n,p) has a cover by exactly ⌈Δ(G)/2⌉ Hamilton cycles for every p from the Hamiltonicity threshold up to the natural dense endpoint. The main new work is the sparse regime, where the degree spread is large; the proof isolates the exceptional very-high-degree and very-low-degree vertices, shows they are well separated, covers the typical part by controlled linear forests, and then extends each forest into a Hamilton cycle using reserved random structure. The same method gives a hitting-time result (the cover appears exactly when the minimum degree reaches two) and implies the linear arboricity conjecture for all binomial random graphs.

What carries the argument

The key objects are linear forests (disjoint unions of paths): unlike arbitrary edge sets, any linear forest can be extended to a Hamilton cycle if enough unused random edges are reserved around its endpoints. The proof splits the graph into a constant number of subgraphs, covers the typical part by approximate linear forests with slack, builds cherry/path gadgets for the exceptional high-degree and low-degree vertices, and pairs typical with exceptional forests so that the leftover has bounded degree. A separation estimate (no short paths or cycles between exceptional vertices) keeps these local gadgets from interfering, and a bounded-degree merging lemma absorbs the leftover. Each final li

What would settle it

Compute the expected number of length-6 paths in G(n, Clog n/n) with both endpoints in the top-degree set (degree at least (1−1/10)Δ). If for any fixed C this expectation is not o(1), the separation lemma fails and the cover construction loses control. A more direct falsifier is any graph in the stated range with an edge between two vertices whose degrees are close to the maximum, since the proof requires such high-degree stars to be disjoint.

Watch

Extended reading notes

Core claim

The central claim is that tight Hamilton covers exist with high probability for G(n,p) throughout the range (log n + log log n + ω(n))/n ≤ p ≤ 1 − ω(n)/n². The proof's new engine is the sparse end: it identifies the small set of vertices whose degree is far from Δ(G), proves these exceptional vertices are separated by no short paths or cycles, covers the typical part by a family of linear forests with slack, merges explicit gadgets for high- and low-degree vertices, and then extends each merged linear forest to a Hamilton cycle via an expander-based tree-embedding (extendability) argument. As corollaries, the tight-cover property appears at the hitting time of minimum degree 2 in the random

Load-bearing premise

The construction depends on a first-moment separation estimate: with high probability no short path (length at most 6) joins two exceptional vertices, and no short cycle passes through the exceptional set or its neighbourhood, and if that estimate failed the local gadgets around different exceptional vertices could collide and the bounded-degree leftover argument would lose control.

Editorial extensions

If this is right

For every p in the stated range, the edges of G(n,p) are covered by the theoretical minimum number of Hamilton cycles, matching the maximum-degree lower bound.
The hitting-time statement says the tight-cover property appears at the same moment the graph first has minimum degree at least two, so Hamiltonicity and tight-coverability share a threshold in the random graph process.
The linear arboricity conclusion gives a path-decomposition of all edges into at most ⌈(Δ+1)/2⌉ linear forests for every p, confirming the linear arboricity conjecture for random graphs.
The proof is constructive and yields a randomized polynomial-time algorithm to find the required cover.
The range of p is best possible up to the critical window 1−p ≍ n⁻², where no whp statement holds because the complement may consist of a single edge.

Reading between the lines

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

The same forest-extension mechanism may transfer to pseudorandom (n,d,λ)-graphs with a degree gap, provided a separation lemma analogous to the one used here can be established for them.
The hitting-time result suggests tight-coverability does not lag behind Hamiltonicity; one could test whether the directed random graph analogue also holds at the analogous hitting time.
The linear arboricity corollary is nearly immediate for the dense regime, so the new content lies in the sparse regime; the proof indicates the separation estimate is the main obstacle to further weakening the degree-range assumptions.
One could computationally explore the constants (the split t and the slack α) to see whether the construction tolerates less separation; the paper does not optimize these constants.

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 paper proves the tight Hamilton-cover theorem for G(n,p) across the full range from the Hamiltonicity threshold to the dense endpoint, and deduces the linear arboricity conjecture for all p. The sparse regime near the threshold is the genuinely new part: the multi-stage construction with separated exceptional vertices, local gadgets for high/low degree vertices, and the extension to Hamilton cycles via reserved random sets is coherent and detailed. The dense range (complement with q = o(1/n^2)) is handled cleanly via regularisation and matchings, and the linear-arboricity deduction is standard once the cover theorem is in hand. The paper is honest about which parts are borrowed: the middle range is indeed [11] combined with [24], and the authors say so clearly.

The main soft spots are minor but real. First, in Section 6, the subcase 1-p = O(n^{-2}) says "whp G has o(n) edges" — that is plainly wrong; the complement has O(1) edges, not G. It reads like a typo, but it sits in a proof of Theorem 1.3, so it should be fixed before publication. Second, Theorem 1.2 (hitting time) is only sketched in the concluding remarks. The sketch is plausible and probably correct, but for a theorem stated in the abstract, a full proof or a precise reduction to the fixed-p case is expected. Third, the sparse argument uses the Hamilton-connectivity theorem from the preprint [14] as a black box. That is fine if the preprint is solid, but the referee should check it; a failure there would weaken the whole construction. The separation property in Proposition 2.5(2) is the kind of first-moment estimate that could worry a reader, but it is standard and the proof gives the right exponents; I do not see a hidden flaw.

Overall, the central argument holds up. The paper is a capstone result for the Hamilton-cover and linear-arboricity questions in random graphs, and it deserves a serious referee. With the typo corrected and the hitting-time proof expanded (or explicitly deferred to a follow-up), it should be accepted. I would bring it to a reading group and cite it in my own work.

Referee Report

2 major / 5 minor

Summary. The paper proves that for edge probabilities p in the range (log n + log log n + omega(n))/n <= p <= 1 - omega(n)/n^2, the binomial random graph G(n,p) has with high probability a Hamilton cover of size ceil(Delta(G)/2), matching the trivial maximum-degree lower bound. This resolves a conjecture of Draganić, Glock, Munhá Correia and Sudakov for the sparse regime near the Hamiltonicity threshold. The paper also states a hitting-time version for the random graph process and uses the Hamilton-cover result to prove the linear arboricity conjecture for all p. The main technical contribution is a constructive proof for the sparse range: the graph is split into a typical middle part and exceptional high/low-degree parts, the typical part is decomposed into linear forests with slack, the exceptional vertices are handled by local gadgets, and an extendability method extends the resulting linear forests to Hamilton cycles. A separate argument handles the very dense range via a Hamilton decomposition theorem.

Significance. If the results are correct, they close the Hamilton-cover problem for random graphs essentially completely, answer the hitting-time question of Hefetz, Kühn, Lapinskas and Osthus, and prove the linear arboricity conjecture for all binomial random graphs. The sparse-range construction is novel and substantial, combining first-moment separation of exceptional vertices, forest-padding and merging mechanisms, and the Friedman–Pippenger extendability method. The paper also delivers a randomized polynomial-time algorithm for finding the cover. The proof of Theorem 1.1 is detailed and, in my reading, internally coherent. However, two advertised results have gaps: the hitting-time theorem is only sketched, and the linear arboricity proof contains a false statement in the dense case. These issues are fixable, but they currently prevent the paper from being fully established.

major comments (2)

[Section 7 (Theorem 1.2)] Theorem 1.2 is stated as a theorem in the abstract and introduction, but its proof is only a sketch. The assertion that 'the same estimates hold uniformly in the random graph process' is not proved. In particular, the exceptional sets B and S and their separation properties are not monotone, and the proof of Theorem 4.1 is written for a fixed binomial graph with a fixed p. A rigorous proof would need a coupling between the process and binomial graphs in the window, a union bound over m, or a direct verification of all deterministic hypotheses for every G_m with m in [m_-, m_+]. As written, Theorem 1.2 is not established.
[Section 6 (Theorem 1.3, case 1-p=O(n^{-2}))] The statement 'Then whp G has o(n) edges' is false. If 1-p=O(n^{-2}), the complement of G has O(1) edges whp, so G has C(n,2)-O(1) edges. The subsequent conclusion that G has a vertex of degree n-1 is correct (because the complement has O(1) edges), and the argument can be repaired by intersecting Walecki's linear-forest decomposition of K_n with E(G). However, the erroneous sentence must be corrected, as it is part of the proof of a stated theorem.

minor comments (5)

[Proposition 2.5, Item 2] The proof uses 'P[v in B] <= n^{-0.59+o(1)}', but the Chernoff calculation in Item 1 gives n^{-0.56+o(1)}. The stronger bound is not justified. The weaker bound suffices for the first-moment argument, but the constants should be made consistent.
[Lemma 5.3] The line 'Let H:= G' should read 'Let H := \bar G' (the complement), since the next equations use delta(H) and Delta(H) for the complement. The subsequent text writes 'H ~ G(n,q)', confirming the intended meaning.
[Section 7] The definition 'm_\pm = n^2 (\log n + \log\log n \pm \xi)' appears dimensionally wrong: the number of edges in the process should be linear in n, i.e., m_\pm = (n/2)(\log n + \log\log n \pm \xi) (or the equivalent binomial-coefficient form). This is likely a typographical error.
[Throughout] The manuscript refers to lemmas as 'Algorithm 2.4', 'Algorithm 3.2', 'Algorithm 4.1', etc. This is confusing and nonstandard. Use 'Lemma' for the statements and reserve 'Algorithm' for computational procedures.
[Section 4, Lemma 4.2] In the proof, the phrase 'The conditional distribution of e_G(v,R_i) given v not in R_i' is unnecessary: the number of neighbours of v in R_i is Bin(d_G(v)-d_W(v), 1/t) regardless of whether v itself lies in R_i, because neighbours are assigned independently. The argument is correct but the conditioning wording may mislead.

Circularity Check

0 steps flagged · score 1.0 of 10

No material circularity: the sparse-range derivation is independent of its target, with only non-load-bearing self-citations.

full rationale

The paper's central derivation is not forced by its own inputs. Theorem 1.1 is proved by an explicit construction: Section 4 partitions G−W, builds t controlled subgraphs via a random partition (Lemma 4.2), covers them by linear forests using Alon's approximate linear arboricity theorem (Theorem 2.2), handles the high- and low-degree vertices by explicit local cherry/path devices (Lemmas 4.4, 4.5), merges the pieces with Lemma 2.1, and finally extends the resulting k=⌈Δ(G)/2⌉ linear forests to Hamilton cycles via Lemma 3.7. The target value k is not used to define the gadgets or to fit any parameter; it is only the final counting target of the construction. The lower bound ⌈Δ(G)/2⌉ is an external obstruction, not an input. The middle range of Theorem 1.1 is inherited from the independent results [11] and [24], and the very dense range is handled by the Kühn–Osthus Hamilton decomposition theorem (Theorem 5.1) plus a standard matching-to-Hamilton-cycle lemma. Theorem 1.3 on linear arboricity is a consequence of the Hamilton-cover theorem, not a premise of it, and the sparse linear-arboricity range is proved separately by direct cherry/path decomposition. Several cited tools involve the present authors ([11], [14], [29]), but they are stated theorems with independent proofs and stated assumptions that do not include the target Hamilton-cover result; citing them is ordinary mathematical practice and does not reduce the main claim to a self-citation. The hitting-time statement is sketched rather than fully expanded, but that is an omitted-detail issue, not circularity. No fitted-input-called-prediction, ansatz-smuggling, renaming, or imported-uniqueness pattern is present.

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

The proof imports standard probabilistic inequalities, tree-embedding and Hamilton decomposition theorems, and one preprint by overlapping authors ([14]). No parameter is fitted to the target result; the constants α,t,ε,K are proof slack chosen as functions of C. No new entities are postulated.

free parameters (4)

α
Small positive constant; 1/10 in Proposition 2.5, and chosen in Theorem 4.1 as a function of C (e.g. 1/(10^4√C)). Controls the size of the high-degree set B; any sufficiently small constant works, not fitted to data.
t = ⌈24/α⌉
Number of parts in the random partition of G−W; chosen to make the slack inequality t(1−2α/3)/(t−2) ≤ 1−α/2 hold.
ε
Slack constant used in the approximate linear arboricity decomposition and in Lemma 3.7 (where ε=K²/100); chosen ≪ min(α,1/C). No data fitting.
K = 1/(3t)
Reservoir fraction required in Lemma 3.7 and used in Lemma 4.8 to guarantee |V(G)\V(F)| ≥ Kn.

assumptions (9)

standard math Alon's approximate linear arboricity theorem (Theorem 2.2): every graph with max degree Δ decomposes into ⌈(1+ε)Δ/2⌉ linear forests.
Used in Lemma 4.2 and in the linear-arboricity proof to cover G−W and G0.
standard math Montgomery's extendability corollary (Corollary 3.5, from [33]) connecting endpoints of an (m,D)-extendable subgraph in an m-joined graph.
Used in Lemma 3.7 Step 3 to join paths of the linear forest.
domain assumption Hamiltonicity of expanders (Theorem 3.6, [14]): every sufficiently large C-expander is Hamilton-connected.
Black-box used in Lemma 3.7 Step 4; [14] is a preprint with overlapping authorship, not machine-checked.
domain assumption Kühn–Osthus Hamilton decomposition theorem (Theorem 5.1): every even-regular graph on n vertices with δ ≥ (1/2+γ)n has a Hamilton decomposition.
Used to finish the very dense range.
standard math Pósa's lemma (Lemma 5.4): in a very dense graph J, any matching can be completed to a Hamilton cycle containing it.
Used in the peeling argument in Theorem 5.2.
standard math Shannon's edge-colouring theorem: the edges of a multigraph of maximum degree d can be coloured with at most 3d/2 colours.
Used to split the multigraph R into matchings in Theorem 5.2.
standard math Standard Chernoff, Lovász Local Lemma, and first-moment estimates for G(n,p).
Used throughout Sections 2–4; assumed without proof.
standard math Walecki decomposition of K_n into Hamilton cycles.
Used for the p=1 case in the linear arboricity proof.
standard math Dirac's theorem: a graph on B vertices with minimum degree > B/2 has a Hamiltonian cycle (hence a perfect matching when B is even).
Used in Lemma 5.3 to find the regularising multigraph R.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient Hamilton covers and linear arboricity of random graphs." pith.science (2026). https://pith.science/paper/NIBFG7I3

@misc{pith2026260714881,
  author       = {Pith},
  title        = {Pith review of: Efficient Hamilton covers and linear arboricity of random graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NIBFG7I3}},
  note         = {Machine review of arXiv:2607.14881}
}

abstract

A Hamilton cover of a graph is a collection of Hamilton cycles whose union contains all edges. Since each Hamilton cycle covers two edges at every vertex, every Hamilton cover has size at least $\lceil \Delta(G)/2\rceil$. We prove that this lower bound is tight for binomial random graphs $G(n,p)$ throughout the widest possible range of edge probabilities: if $\omega(n)\to\infty$ and \[ \frac{\log n+\log\log n+\omega(n)}{n} \le p=p(n) \le 1-\frac{\omega(n)}{n^{2}}, \] then $G\sim G(n,p)$ with high probability has a Hamilton cover of size $\left\lceil \frac{\Delta(G)}{2}\right\rceil. $ The main new contribution is the sparse regime near the Hamiltonicity threshold, where we prove a conjecture of Dragani\'c, Glock, Munh\'a Correia and Sudakov. Our proof develops constructive tools for decomposing such graphs into controlled forest systems and extending them, using reserved pseudorandom structure, into Hamilton cycles. We also prove the corresponding hitting-time result for the random graph process, answering a question of Hefetz, K\"uhn, Lapinskas and Osthus. Finally, we use our methods to show that $G\sim G(n,p)$ with high probability satisfies the celebrated Linear arboricity conjecture for every $p\leq 1$.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

36 extracted references · 3 linked inside Pith

[11]

Optimal Hamilton covers and linear arboricity for random graphs.Proceedings of the American Mathematical Society, 153(3):921–935, 2025

Nemanja Dragani´ c, Stefan Glock, David Munh´ a Correia, and Benny Sudakov. Optimal Hamilton covers and linear arboricity for random graphs.Proceedings of the American Mathematical Society, 153(3):921–935, 2025

2025
[24]

Optimal covers with Hamilton cycles in random graphs.Combinatorica, 34(5):573–596, 2014

Dan Hefetz, Daniela K¨ uhn, John Lapinskas, and Deryk Osthus. Optimal covers with Hamilton cycles in random graphs.Combinatorica, 34(5):573–596, 2014

2014
[14]

Hamiltonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

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

arXiv 2024
[1]

The first occurrence of Hamilton cycles in random graphs.Annals of Discrete Mathematics, 27:173–178, 1985

Mikl´ os Ajtai, J´ anos Koml´ os, and Endre Szemer´ edi. The first occurrence of Hamilton cycles in random graphs.Annals of Discrete Mathematics, 27:173–178, 1985

1985
[2]

Covering and packing in graphs

Jin Akiyama, Geoffrey Exoo, and Frank Harary. Covering and packing in graphs. III. Cyclic and acyclic invariants.Mathematica Slovaca, 30(4):405–417, 1980

1980
[3]

The linear arboricity of graphs.Israel Journal of Mathematics, 62(3):311–325, 1988

Noga Alon. The linear arboricity of graphs.Israel Journal of Mathematics, 62(3):311–325, 1988

1988
[4]

Algorithms with large domination ratio

Noga Alon, Gregory Gutin, and Michael Krivelevich. Algorithms with large domination ratio. Journal of Algorithms, 50(1):118–131, 2004

2004
[5]

Spencer.The Probabilistic Method

Noga Alon and Joel H. Spencer.The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Hoboken, NJ, fourth edition, 2016. 20

2016

Show all 36 references

[6]

The wonderful Walecki construction.Bulletin of the Institute of Combinatorics and its Applications, 52:7–20, 2008

Brian Alspach. The wonderful Walecki construction.Bulletin of the Institute of Combinatorics and its Applications, 52:7–20, 2008

2008
[7]

The evolution of sparse graphs

B´ ela Bollob´ as. The evolution of sparse graphs. InGraph Theory and Combinatorics (Cambridge, 1983), pages 35–57. Academic Press, London, 1984

1983
[8]

Cambridge Studies in Advanced Mathematics, volume 73

B´ ela Bollob´ as.Random Graphs. Cambridge Studies in Advanced Mathematics, volume 73. Cambridge University Press, Cambridge, second edition, 2001

2001
[9]

B´ ela Bollob´ as and Alan M. Frieze. On matchings and Hamiltonian cycles in random graphs. In Random Graphs ’83 (Pozna´ n, 1983), volume 118 ofNorth-Holland Mathematics Studies, pages 23–46. North-Holland, Amsterdam, 1985

1983
[10]

New bounds for linear arboricity and related problems.arXiv preprint arXiv:2507.20500, 2025

Micha Christoph, Nemanja Dragani´ c, Ant´ onio Gir˜ ao, Eoin Hurley, Lukas Michel, and Alp M¨ uyesser. New bounds for linear arboricity and related problems.arXiv preprint arXiv:2507.20500, 2025

2025 arXiv
[12]

Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions.arXiv preprint arXiv:2507.22807, 2025

Nemanja Dragani´ c, Jaehoon Kim, Hyunwoo Lee, David Munh´ a Correia, Mat ´ ıas Pavez-Sign´ e, and Benny Sudakov. Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions.arXiv preprint arXiv:2507.22807, 2025

2025 arXiv
[13]

Rolling backwards can move you forward: on embedding problems in sparse expanders.Transactions of the American Mathem- atical Society, 375(7):5195–5216, 2022

Nemanja Dragani´ c, Michael Krivelevich, and Rajko Nenadov. Rolling backwards can move you forward: on embedding problems in sparse expanders.Transactions of the American Mathem- atical Society, 375(7):5195–5216, 2022

2022
[15]

Towards the linear arboricity conjecture.Journal of Combinatorial Theory, Series B, 142:56–79, 2020

Asaf Ferber, Jacob Fox, and Vishesh Jain. Towards the linear arboricity conjecture.Journal of Combinatorial Theory, Series B, 142:56–79, 2020

2020
[16]

Packing, counting and covering Hamilton cycles in random directed graphs.Israel Journal of Mathematics, 220:57–87, 2017

Asaf Ferber, Gal Kronenberg, and Eoin Long. Packing, counting and covering Hamilton cycles in random directed graphs.Israel Journal of Mathematics, 220:57–87, 2017

2017
[17]

Minimum degree edge-disjoint Hamilton cycles in random directed graphs

Asaf Ferber and Adva Mond. Minimum degree edge-disjoint Hamilton cycles in random directed graphs. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), pages 336–347. ACM, 2025. doi:10.1145/3717823.3718261

2025
[18]

Expanding graphs contain all small trees.Combinatorica, 7(1):71–76, 1987

Joel Friedman and Nicholas Pippenger. Expanding graphs contain all small trees.Combinatorica, 7(1):71–76, 1987

1987
[19]

On two Hamilton cycle problems in random graphs.Israel Journal of Mathematics, 166:221–234, 2008

Alan Frieze and Michael Krivelevich. On two Hamilton cycle problems in random graphs.Israel Journal of Mathematics, 166:221–234, 2008

2008
[20]

On covering expander graphs by Hamilton cycles.Random Structures & Algorithms, 44(2):183–200, 2014

Roman Glebov, Michael Krivelevich, and Tibor Szab´ o. On covering expander graphs by Hamilton cycles.Random Structures & Algorithms, 44(2):183–200, 2014

2014
[21]

Optimal path and cycle decompositions of dense quasirandom graphs.Journal of Combinatorial Theory, Series B, 118:88–108, 2016

Stefan Glock, Daniela K¨ uhn, and Deryk Osthus. Optimal path and cycle decompositions of dense quasirandom graphs.Journal of Combinatorial Theory, Series B, 118:88–108, 2016

2016
[22]

TSP tour domination and Hamilton cycle decompositions of regular digraphs.Operations Research Letters, 28:107–111, 2001

Gregory Gutin and Anders Yeo. TSP tour domination and Hamilton cycle decompositions of regular digraphs.Operations Research Letters, 28:107–111, 2001

2001
[23]

Penny E. Haxell. Tree embeddings.Journal of Graph Theory, 36(3):121–130, 2001. 21

2001
[25]

Wiley-Interscience, New York, 2000

Svante Janson, Tomasz Luczak, and Andrzej Ruci´ nski.Random Graphs. Wiley-Interscience, New York, 2000

2000
[26]

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.Journal of the ACM, 51(4):671–697, 2004

Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.Journal of the ACM, 51(4):671–697, 2004

2004
[27]

Edge-disjoint Hamilton cycles in random graphs.Random Structures & Algorithms, 46(3):397–445, 2015

Fiachra Knox, Daniela K¨ uhn, and Deryk Osthus. Edge-disjoint Hamilton cycles in random graphs.Random Structures & Algorithms, 46(3):397–445, 2015

2015
[28]

Limit distribution for the existence of Hamiltonian cycles in a random graph.Discrete Mathematics, 43(1):55–63, 1983

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

1983
[29]

Optimal packings of Hamilton cycles in sparse random graphs.SIAM Journal on Discrete Mathematics, 26(3):964–982, 2012

Michael Krivelevich and Wojciech Samotij. Optimal packings of Hamilton cycles in sparse random graphs.SIAM Journal on Discrete Mathematics, 26(3):964–982, 2012

2012
[30]

Hamilton decompositions of regular expanders: applications

Daniela K¨ uhn and Deryk Osthus. Hamilton decompositions of regular expanders: applications. Journal of Combinatorial Theory, Series B, 104:1–27, 2014

2014
[31]

An improved bound for the linear arboricity conjecture.Com- binatorica, 43(3):547–569, 2023

Richard Lang and Luke Postle. An improved bound for the linear arboricity conjecture.Com- binatorica, 43(3):547–569, 2023

2023
[32]

Linear arboricity of random regular graphs.Random Struc- tures & Algorithms, 1(4):443–445, 1990

Colin McDiarmid and Bruce Reed. Linear arboricity of random regular graphs.Random Struc- tures & Algorithms, 1(4):443–445, 1990

1990
[33]

Spanning trees in random graphs.Advances in Mathematics, 356:106793, 2019

Richard Montgomery. Spanning trees in random graphs.Advances in Mathematics, 356:106793, 2019

2019
[34]

Moser and G´ abor Tardos

Robin A. Moser and G´ abor Tardos. A constructive proof of the general Lov´ asz local lemma. Journal of the ACM, 57(2):1–15, 2010

2010
[35]

On the circuits of finite graphs.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 8(3):355–361, 1963

Lajos P´ osa. On the circuits of finite graphs.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 8(3):355–361, 1963

1963
[36]

Hamiltonian circuits in random graphs.Discrete Mathematics, 14(4):359–364, 1976

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

1976

Pith tools

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

[1] [11]

Optimal Hamilton covers and linear arboricity for random graphs.Proceedings of the American Mathematical Society, 153(3):921–935, 2025

Nemanja Dragani´ c, Stefan Glock, David Munh´ a Correia, and Benny Sudakov. Optimal Hamilton covers and linear arboricity for random graphs.Proceedings of the American Mathematical Society, 153(3):921–935, 2025

2025

[2] [24]

Optimal covers with Hamilton cycles in random graphs.Combinatorica, 34(5):573–596, 2014

Dan Hefetz, Daniela K¨ uhn, John Lapinskas, and Deryk Osthus. Optimal covers with Hamilton cycles in random graphs.Combinatorica, 34(5):573–596, 2014

2014

[3] [14]

Hamiltonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

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

arXiv 2024

[4] [1]

The first occurrence of Hamilton cycles in random graphs.Annals of Discrete Mathematics, 27:173–178, 1985

Mikl´ os Ajtai, J´ anos Koml´ os, and Endre Szemer´ edi. The first occurrence of Hamilton cycles in random graphs.Annals of Discrete Mathematics, 27:173–178, 1985

1985

[5] [2]

Covering and packing in graphs

Jin Akiyama, Geoffrey Exoo, and Frank Harary. Covering and packing in graphs. III. Cyclic and acyclic invariants.Mathematica Slovaca, 30(4):405–417, 1980

1980

[6] [3]

The linear arboricity of graphs.Israel Journal of Mathematics, 62(3):311–325, 1988

Noga Alon. The linear arboricity of graphs.Israel Journal of Mathematics, 62(3):311–325, 1988

1988

[7] [4]

Algorithms with large domination ratio

Noga Alon, Gregory Gutin, and Michael Krivelevich. Algorithms with large domination ratio. Journal of Algorithms, 50(1):118–131, 2004

2004

[8] [5]

Spencer.The Probabilistic Method

Noga Alon and Joel H. Spencer.The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Hoboken, NJ, fourth edition, 2016. 20

2016