Pith. sign in

REVIEW 4 major objections 6 minor 1 cited by

Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions

T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper proves optimal resilience and approximate Hamilton decompositions for sparse pseudorandom graphs, showing that subgraphs with minimum degree above d/2 are Hamiltonian and that edge-disjoint Hamilton cycles achieve (1±ε)d/2.

desk verdict Strong paper: asymptotically optimal resilience and approximate Hamilton decompositions for constant spectral ratio (n,d,λ)-graphs, conditional on deferred expander proofs from [19]. read the letter →

arxiv 2507.22807 v1 pith:XFQHBM2H submitted 2025-07-30 math.CO

Nemanja Draganić , Jaehoon Kim , Hyunwoo Lee , David Munhá Correia , Matías Pavez-Signé , Benny Sudakov This is my paper
classification math.CO MSC 05C4505C4805C7005C80
keywords Hamiltoncyclespseudorandomgraphsresiliencegraphdecompositionssparseregularitylemma(ndλ)-graphsexpanderHamilton-connectedness
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 proves that sparse pseudorandom graphs obey the classical minimum-degree threshold for Hamilton cycles, and that their edges can be almost perfectly organized into Hamilton cycles. Concretely, it shows that every spanning subgraph of an (n,d,λ)-graph—a d-regular graph whose non-trivial adjacency eigenvalues are bounded by λ—with d/λ a sufficiently large constant and minimum degree above d/2 contains a Hamilton cycle. It also shows that every such graph contains at least (1−ε)d/2 edge-disjoint Hamilton cycles, and that all of its edges can be covered by at most (1+ε)d/2 Hamilton cycles, for any fixed ε>0. These bounds are asymptotically optimal, since a d-regular graph can contain at most d/2 edge-disjoint Hamilton cycles and needs at least d/2 to cover all its edges. The results are proved for the more general class of (η,β,p)-sparse graphs, which only forbid locally dense subgraphs, and are then transferred to (n,d,λ)-graphs through the expander mixing lemma.

What carries the argument

The central object is the (η,β,p)-sparse graph: for every pair of vertex sets U,W with ηpn≤|U|=|W|≤ηn, the number of edge-incidences e(U,W) is at most (1+β)ηpn|U|. This upper-tail sparsity condition is exactly what the expander mixing lemma supplies for (n,d,λ)-graphs, and it replaces eigenvalue assumptions throughout the proofs. The Hamiltonicity argument partitions the vertex set, via the sparse regularity lemma, into balanced bipartite D-expanders (graphs in which small sets expand by a factor D and any two large opposite-side sets share an edge) placed cyclically so that consecutive parts share an edge, then uses Hamilton-connectedness of bipartite expanders to stitch a cycle together; this Hamilton-connectedness is Theorem 4.1, which the paper does not prove but states follows from earlier expander work. For packing and covering, the paper randomly splits G into G1 and G2, preserving a 'joinedness' property in G2 between large sets, and proves a sparse-augmentation lemma that builds each Hamilton cycle while using very few G2-edges and controlling the m-max degree of the borrowed edges, so the process can iterate to (1−ε)d/2 cycles; the leftover edges are absorbed by extra cycles.

What would settle it

Exhibit, for arbitrarily large C, a bipartite graph with equal parts of size n that is n/(2C)-bipartite-joined and in which every subset of size at most n/(2C) expands by factor C into the opposite part, yet two vertices in opposite parts have no Hamiltonian path between them. Such a graph would directly falsify Theorem 4.1 and, with it, the stated proof chain of the resilience and decomposition theorems. Alternatively, a spanning subgraph of an (n,d,λ)-graph with minimum degree (1/2+γ)d and no Hamilton cycle for arbitrarily large d/λ would falsify Theorem 1.5 directly.

Watch

Extended reading notes

Core claim

The central discovery is that excluding excessively dense subgraphs is enough to recover the full Hamiltonian picture of random-like graphs: a minimum-degree condition at the classical threshold yields a Hamilton cycle, and packing and covering both reach the optimal (1±ε)d/2 scale. The paper isolates this through the (η,β,p)-sparsity condition, a one-sided upper bound on edge counts between medium-sized sets, and proves the resilience, packing, and covering theorems for it. Because every (n,d,λ)-graph with d/λ≥C is (η,β,d/n)-sparse, the pseudorandom theorems follow: Theorem 1.5 for resilience and Theorem 1.8 for the simultaneous (1−ε)d/2 packing and (1+ε)d/2 covering. All the stated bounds are asymptotically optimal, and the paper notes that its proof gives a tower-type dependence of C on 1/γ while the examples force C=Ω(1/γ).

Load-bearing premise

The load-bearing premise is the unproved assertion that every balanced bipartite C-expander has a Hamiltonian path between any two prescribed vertices in opposite parts (Theorem 4.1); if that assertion needs stronger expansion or is false, the main theorems lose their proof even if they remain true.

Editorial extensions

If this is right

  • If the main theorems are correct, the classical n/2 minimum-degree Hamiltonicity theorem holds in sparse pseudorandom graphs with the spectral ratio only a large constant, improving prior resilience results that required d/λ≥log^{1+o(1)}n.
  • Approximate Hamilton decompositions become available at the optimal scale: every (n,d,λ)-graph with d/λ≥C contains (1−ε)d/2 edge-disjoint Hamilton cycles and is coverable by (1+ε)d/2 Hamilton cycles.
  • Random d-regular graphs with large d, being (n,d,λ)-graphs with λ=O(√d), inherit optimal resilience and approximate decomposition bounds in the sparse regime.
  • Because the theorems are stated for (η,β,p)-sparse graphs, any graph that merely avoids locally dense subgraphs—not just eigenvalue-defined graphs—satisfies the same Hamiltonian guarantees.
  • The packing and covering constants being asymptotically optimal means the only remaining step toward the paper's concluding conjecture is exactness: an exact Hamilton decomposition for even d with d/λ>C.

Reading between the lines

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

  • The unproved Hamilton-connectedness theorem (Theorem 4.1) is a genuine contingency: since the resilience proof invokes it directly, a reader verifying the paper should confirm that the cited expander argument indeed yields Hamilton-connectedness for bipartite C-expanders with these exact parameters.
  • The random edge-splitting with an m-max-degree budget looks like a transferable method: the same 'borrow few edges from a reserve graph, keep the reserve joined' scheme could produce approximate decompositions into other spanning subgraphs, such as spanning trees or F-factors.
  • The paper's examples force C=Ω(1/γ), while the proof only gives a tower-type bound; one implicit open problem is whether the true constant can be polynomial in 1/γ, which would be a natural next target.
  • The (η,β,p)-sparsity formulation suggests a spectral-free test: any deterministic or random graph whose medium-sized sets have no density surplus should show the same resilience, independently of eigenvalue computations.
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.

Referee Report

4 major / 6 minor

Summary. The paper studies Hamiltonicity, resilience, and Hamilton decompositions of sparse pseudorandom graphs. It introduces the notion of (η,β,p)-sparse graphs, proves a resilience theorem (Theorem 1.4) for such graphs with minimum degree at least (1/2+γ)d, and derives the corresponding optimal result for (n,d,λ)-graphs (Theorem 1.5). It then proves packing and covering results: every sufficiently sparse almost-regular graph contains at least (1−ε)d/2 edge-disjoint Hamilton cycles (Theorem 1.6) and its edges can be covered by at most (1+ε)d/2 Hamilton cycles (Theorem 1.7), again yielding optimal statements for (n,d,λ)-graphs (Theorem 1.8). The proofs combine a structural decomposition into cyclically arranged bipartite expanders (Theorem 3.1), a bipartite Hamilton-connectedness assertion (Theorem 4.1), and a general 'Sparse Augmentation' lemma (Lemma 5.3) that controls the use of reserve edges during iterative cycle extraction.

Significance. If the main results stand, this is a substantial contribution: it resolves the natural pseudorandom analogues of Dirac's theorem and of the Nash-Williams decomposition problem in the sparse spectral regime, and it improves known results for packing and covering Hamilton cycles in (n,d,λ)-graphs by reducing the required spectral ratio from polylogarithmic to constant. The formulation in terms of (η,β,p)-sparse graphs is a useful unifying framework, and the paper explicitly identifies the sharp trade-offs (the examples before Definition 1.3 and the concluding remarks). The claimed asymptotic optimality of the bounds is significant. However, the present version leaves several load-bearing technical steps as assertions that they follow 'by the same argument' as in [19], and one of these steps (Theorem 4.1) is not a literal consequence of the cited theorem. The central claim of the paper is therefore not yet fully verifiable from the submitted text.

major comments (4)
  1. [Section 4, Theorem 4.1] Theorem 4.1 is stated as a standalone result but no proof is given; the text says it follows from the analogous arguments as the proof of Theorem 1.2 in [19]. This is not a direct logical consequence: a balanced bipartite C-expander does not satisfy the general joinedness condition of Theorem 1.2 for two sets lying inside the same part, so a separate bipartite argument is genuinely required. Since Theorem 4.1 is used directly in the proof of Theorem 1.4 (it supplies the Hamiltonian paths P_i inside each G[U_{2i-1}, U_{2i}]), the resilience theorem depends on this unproved statement. The authors should either include a full proof of Theorem 4.1 or give an exact reference to a published theorem that contains it.
  2. [Section 5.3, Claim 9 and Lemma 5.5] In the proof of Lemma 5.3, the graph F_1^0 is obtained from Lemma 2.5, which only guarantees at most 2δn paths and gives no upper bound on the length of individual paths and no lower bound on the number of paths. Lemma 5.5, however, requires condition (ii): a spanning linear forest with n^0.9 ≤ ℓ ≤ δn paths and each path of length at most n^0.15. The manuscript does not explain how F_1^0 is refined to satisfy these length and count bounds. This is a concrete gap in the proof of the central sparse augmentation lemma, and it needs to be resolved either by proving a suitable refinement or by modifying Lemma 5.5.
  3. [Section 5.2 and Appendix A.3] The proof of Lemma 5.6 delegates key steps to Lemma A.12 and Lemma A.13, whose proofs are said to be identical to or small variations of Lemmas 3.5 and 3.6 in [19], and to Lemma A.17, said to follow from Lemma 4.7 in [19]. These adaptations are not written out. The manuscript itself notes that the m-joined property must be replaced by βn-bipartite-joinedness and that this requires checking that the relevant sets are (F,βn)-balanced; that check is the crux and is only asserted. Because Lemma 5.6 is used in Lemma 5.8 and then in Claim 10 of the proof of Lemma 5.3, the packing and covering theorems inherit this unverified step.
  4. [Appendix A.2, Lemma A.7] Lemma A.7, the existence of the rooted bipartite linking structure H*, is stated with 'We omit the proof of Lemma A.7 as the proof is same.' The lemma includes a rootedness condition and length bounds that do not literally appear in Lemma 5.5 of [19]; the appendix does not provide a construction or a precise reduction. Since Lemma A.7 is used to build the linking structure inside Lemma 5.5, and Lemma 5.5 is the starting engine for the whole sparse augmentation proof, this omission leaves the proof of Theorems 1.6 and 1.7 incomplete. The authors should include the full construction or an exact lemma-reference with the modified parameters made explicit.
minor comments (6)
  1. [Section 2.4, Lemma 2.13] The conclusion of Lemma 2.13 reads |N_G(U) ∩ Y| ≥ D|X|, but since U ⊆ X and the hypothesis bounds |U|, the intended conclusion is surely |N_G(U) ∩ Y| ≥ D|U|. As written, the inequality is dimensionally suspect and the later applications (e.g., in Lemma 5.5 and Section 5.2) use the D|U| form.
  2. [Section 5, Definition 5.1] In the definition of m-max degree, the notation Δ_m(G) is introduced but the formula m·Δ(H)+t(H) refers to H; the definition should use a single letter, or the two graphs should be explicitly identified. Also 'a collection of pairs E ⊂ (V(H) choose 2)' overloads E with the edge set notation used elsewhere.
  3. [Section 5.3, proof of Lemma 5.3] In the paragraph after Claim 10, the proof says 'for some i' and 'for some t ≤ |A|', but the relabelling of endpoints of F is not fully spelled out; a short explicit description of the pairing between endpoints of F and the linked paths P_i would improve readability.
  4. [Section 6.1, proof of Theorem 1.6] The proof asserts 'since we do not yet have the packing we want, we can find a path x_1 z x_2 of length two in G_1 \ C.' This requires a brief justification; it is not immediate from the stated degree bounds that such a path exists at the moment it is invoked.
  5. [Section 1, Theorem 1.8] The statement of Theorem 1.8 says 'contains at least (1−ε)d/2 edge-disjoint Hamilton cycles' in the abstract but the theorem statement in Section 1.2 says 'contains at least (1−ε)d/2 edge-disjoint Hamilton cycles' inconsistently with the previous line; the theorem statement should include the word 'edge-disjoint' explicitly if that is the intended meaning.
  6. [Throughout] The paper relies heavily on [19] for several auxiliary lemmas and on [52] for the path partition theorem; it would help the reader if each such invocation included the exact lemma number in the cited paper and a one-sentence explanation of which parameters are modified.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the proofs are mathematical deductions from stated expansion and sparsity assumptions; deferred arguments from [19] are prior external results, not inputs in disguise.

full rationale

I walked the derivation chain of Theorems 1.4–1.8 and found no step in which a claimed output is defined in terms of itself, no fitted parameter renamed as a prediction, and no result that is forced by an unverified self-citation in place of an argument. The paper's central input is the notion of (η, β, p)-sparsity, which is a definition satisfied by (n, d, λ)-graphs via the Expander Mixing Lemma (Lemma 2.15); the main theorems are then derived from this definition using the sparse regularity lemma, expansion lemmas, and connecting/linking lemmas. There is no data-fitting or approximate-empirical component, so the 'prediction reduces to a fit' pattern does not occur. The closest item to a circularity concern is Theorem 4.1, where the text says 'We do not give an explicit proof of Theorem 4.1 as it follows from the analogous arguments as the proof of Theorem 1.2 ([19]).' This is a real load-bearing deferral, but it is not circular: Theorem 1.2 in [19] is a distinct prior theorem with its own stated assumptions (C-expanders), and those assumptions do not include the present theorems' conclusions. Overlapping authorship of [19] is normal and, under the rules, a cited result with stated assumptions not containing the target result counts as independent evidence. A second cluster of deferred proofs appears in Section 5 and Appendix A: Lemma 5.5 is proved in Appendix A.2, Lemma 5.6 is said to be 'similar to the proof of Lemma 3.7 in [19]', and Lemmas A.7, A.12, A.13 and A.17 are stated with phrases such as 'we omit the proof as the proof is same' or 'follows from the same proof'. These omissions make the paper incomplete as a fully self-contained proof, and the skeptic's specific point about Lemma 5.5's hypothesis (ii) — that Section 5.3 applies Lemma 5.5 to F_1^0 obtained from Lemma 2.5, which guarantees only an upper bound of 2δn paths and not the required lower bound n^0.9 — is a verification gap that could invalidate the proof if not fixable. But a missing or deferred proof is a correctness risk, not circularity: no equation in the paper is equivalent by construction to its own input, and no conclusion is imported from a uniqueness theorem asserted only by the present authors. The 'Hamilton-connected bipartite C-expander' statement is not defined in terms of the resilience or decomposition conclusions; it is an independent intermediate assertion that the paper chooses to inherit from [19] by analogy.

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

The paper introduces the (eta,beta,p)-sparsity condition as a modeling assumption; for (n,d,lambda)-graphs this is derived from the Expander mixing lemma. All constants are universally quantified parameters, not fitted to data. The main proofs rely on external theorems from the same research group ([19], [52]), which are cited with proofs elsewhere and are not available inside this manuscript; those are listed above as domain assumptions. No invented physical or combinatorial entities are postulated.

assumptions (6)
  • standard math Sparse regularity lemma (Kohayakawa and Rödl)
    Used in Lemma 2.8 and in the proofs of Theorem 3.1 and Lemma 5.6 to find (epsilon,p)-regular partitions of sparse graphs.
  • standard math Expander mixing lemma
    Used in Lemma 2.15 to prove that (n,d,lambda)-graphs with lambda/d <= beta*eta are (eta,beta,d/n)-sparse, connecting the spectral condition to the paper's main hypothesis.
  • standard math Dirac's theorem
    Invoked in the proof of Theorem 3.1 to find a Hamilton cycle in the dense reduced graph R, whose minimum degree is at least (1/2+gamma/2)K.
  • domain assumption Theorem 1.2 of [19]: C-expanders are Hamiltonian and Hamilton-connected
    Used in the proof of Theorem 1.7 to find a Hamilton path in G[Z], and cited as the basis for Theorem 4.1 in Section 4.
  • domain assumption Theorem 2.4 of [52] on path decompositions of regular graphs
    Used in Lemma 2.5 to bound the number of paths needed to partition the vertices of an almost-regular graph, a step in constructing linear forests.
  • standard math Vizing's theorem on edge-coloring
    Used in the proof of Theorem 1.7 to decompose the leftover graph G' into at most Delta(G')+1 matchings.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions." pith.science (2026). https://pith.science/paper/XFQHBM2H

@misc{pith2026250722807,
  author       = {Pith},
  title        = {Pith review of: Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XFQHBM2H}},
  note         = {Machine review of arXiv:2507.22807}
}
abstract

Dirac's classical theorem asserts that, for $n \ge 3$, any $n$-vertex graph with minimum degree at least $n/2$ is Hamiltonian. Furthermore, if we additionally assume that such graphs are regular, then, by the breakthrough work of Csaba, K\"uhn, Lo, Osthus and Treglown, they admit a decomposition into Hamilton cycles and at most one perfect matching, solving the well-known Nash-Williams conjecture. In the pseudorandom setting, it has long been conjectured that similar results hold in much sparser graphs. We prove two overarching theorems for graphs that exclude excessively dense subgraphs, which yield asymptotically optimal resilience and Hamilton-decomposition results in sparse pseudorandom graphs. In particular, our results imply that for every fixed $\gamma > 0$, there exists a constant $C > 0$ such that if $G$ is a spanning subgraph of an $(n,d,\lambda)$-graph satisfying $\delta(G) \ge (\tfrac12 + \gamma)d$ and $d/\lambda \ge C$, then $G$ must contain a Hamilton cycle. Secondly, we show that for every $\varepsilon > 0$, there is $C > 0$ so that every $(n,d,\lambda)$-graph with $d/\lambda \ge C$ contains at least $(\tfrac12 - \varepsilon)d$ edge-disjoint Hamilton cycles, and, finally, we prove that the entire edge set of $G$ can be covered by no more than $(\tfrac12 + \varepsilon)d$ such cycles. All bounds are asymptotically optimal and significantly improve earlier results on Hamiltonian resilience, packing, and covering in sparse pseudorandom graphs.

Discussion (0). Sign in 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

  1. Efficient Hamilton covers and linear arboricity of random graphs

    math.CO 2026-07 conditional novelty 7.0 of 10

    Random graphs with any edge probability have Hamilton covers of the smallest possible size, once Hamilton cycles exist.

Reference graph

Works this paper leans on

62 extracted references · 60 canonical work pages · cited by 1 Pith paper

  1. [19]

    Dragani´ c, R

    N. Dragani´ c, R. Montgomery, D. Munh´ a Correia, A. Pokrovskiy, and B. Sudakov. Hamiltonicity of expanders: optimal bounds and applications. arXiv preprint arXiv:2402.06603 , 2024

    arXiv 2024

  2. [1]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. First occurrence of Hamilton cycles in random graphs. In Cycles in Graphs, edited by B.R. Alspach and C.D. Godsil, volume 27 of Ann. Discrete Math., pages 173–178. North-Holland, 1985. 23

    work page 1985

  3. [2]

    Allen, J

    P. Allen, J. B¨ ottcher, H. H` an, Y. Kohayakawa, and Y. Person. Powers of Hamilton cycles in pseudorandom graphs. Combinatorica, 37(4):573–616, 2017

    work page 2017

  4. [3]

    B. Alspach. The wonderful Walecki construction. Bull. Inst. Combin. Appl. , 52:7–20, 2008

    work page 2008

  5. [4]

    Alspach, J

    B. Alspach, J. C. Bermond, and D. Sotteau. Decomposition into cycles. I. Hamilton decompositions. In Cycles and rays (Montreal, PQ, 1987) , volume 301 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 9–18. Kluwer Acad. Publ., 1990

    work page 1987

  6. [5]

    Ara´ ujo, M

    P. Ara´ ujo, M. Pavez-Sign´ e, and N. Sanhueza-Matamala. Ramsey numbers of cycles in random graphs. Random Struct. Algorithms , 66(1):e21253, 2025

    work page 2025

  7. [6]

    Bang-Jensen and G

    J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications . Springer Monogr. Math. Springer-Verlag, 2nd edition, 2009

    work page 2009

  8. [7]

    Ben-Shimon, M

    S. Ben-Shimon, M. Krivelevich, and B. Sudakov. Local resilience and Hamiltonicity Maker-Breaker games in random regular graphs. Combin. Probab. Comput. , 20(2):173–211, 2011

    work page 2011

Show all 62 references
  1. [8]

    Bollob´ as

    B. Bollob´ as. Almost all regular graphs are hamiltonian. Eur. J. Comb. , 4(2):97–106, 1983

    1983

  2. [9]

    Bollob´ as

    B. Bollob´ as. The evolution of sparse graphs. InGraph theory and combinatorics (Cambridge, 1983) , pages 97–106. Academic Press, London, 1983

    1983

  3. [10]

    Bollob´ as and A

    B. Bollob´ as and A. M. Frieze. On matchings and hamiltonian cycles in random graphs. Ann. Discrete Math., 28:23–46, 1985

    1985

  4. [11]

    A. G. Chetwynd and A. J. W. Hilton. Regular graphs of high degree are 1-factorizable. Proc. Lond. Math. Soc. (3) , 50(2):193–206, 1985

    1985

  5. [12]

    Christoph, N

    M. Christoph, N. Dragani´ c, A. Gir˜ ao, E. Hurley, L. Michel, and A. M¨ uyesser. New bounds for linear arboricity and related problems. arXiv preprint arXiv:2507.20500 , 2025

    2025 arXiv

  6. [13]

    Condon, A

    P. Condon, A. Espuny D ´ ıaz, A. Gir˜ ao, D. K¨ uhn, and D. Osthus. Dirac’s theorem for random regular graphs. Combin. Probab. Comput. , 30(1):17–36, 2021

    2021

  7. [14]

    Cooper, A

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

    2002

  8. [15]

    Csaba, D

    B. Csaba, D. K¨ uhn, A. Lo, D. Osthus, and A. Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures. Mem. Am. Math. Soc. , 244(1154), 2016

    2016

  9. [16]

    R. Diestel. Graph Theory. Grad. Texts Math. 173. Springer, 5th edition, 2018

    2018

  10. [17]

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

    1952

  11. [18]

    Dragani´ c, M

    N. Dragani´ c, M. Krivelevich, and R. Nenadov. Rolling backwards can move you forward: on embedding problems in sparse expanders. Trans. Amer. Math. Soc. , 375(7):5195–5216, 2022

    2022

  12. [20]

    Dragani´ c, S

    N. Dragani´ c, S. Glock, D. Munh´ a Correia, and B. Sudakov. Optimal Hamilton covers and linear arboricity for random graphs. Proc. Amer. Math. Soc. , 153(3):921–935, 2025

    2025

  13. [21]

    T. I. Fenner and A. M. Frieze. Hamiltonian cycles in random regular graphs. J. Comb. Theory B , 37(2):103–112, 1984. 24

    1984

  14. [22]

    Ferber, J

    A. Ferber, J. Han, D. Mao, and R. Vershynin. Hamiltonicity of sparse pseudorandom graphs. Combin. Probab. Comput. , pages 1–25, 2024

    2024

  15. [23]

    Ferber, B

    A. Ferber, B. Frederickson, D. Mao, L. Yepremyan, and Y. Zhu. Regular bipartite decompositions of pseudorandom graphs. arXiv preprint arXiv:2410.12981 , 2024

    2024 arXiv

  16. [24]

    Ferber, G

    A. Ferber, G. Kronenberg, and E. Long. Packing, counting and covering Hamilton cycles in random directed graphs. Isr. J. Math. , 220:57–87, 2017

    2017

  17. [25]

    Friedman and N

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

    1987

  18. [26]

    Gerke and A

    S. Gerke and A. Steger. The sparse regularity lemma and its applications. In Surveys in Combina- torics 2005 , volume 327 of LMS Lect. Note Ser. , pages 227–258. Cambridge Univ. Press, 2005

    2005

  19. [27]

    R. Glebov. On Hamilton cycles and other spanning structures . PhD thesis, Freie Universit¨ at Berlin, 2013

    2013

  20. [28]

    Glock, F

    S. Glock, F. Joos, J. Kim, D. K¨ uhn, and D. Osthus. Resolution of the Oberwolfach problem. J. Eur. Math. Soc. (JEMS) , 23(8):2511–2547, 2021

    2021

  21. [29]

    Glock, D

    S. Glock, D. K¨ uhn, and D. Osthus. Extremal aspects of graph and hypergraph decomposition problems. In Surveys in Combinatorics 2021 , volume 470 of LMS Lect. Note Ser. , pages 235–265. Cambridge Univ. Press, 2021

    2021

  22. [30]

    Glock, D

    S. Glock, D. Munh´ a Correia, and B. Sudakov. Hamilton cycles in pseudorandom graphs. Adv. Math., 458:109984, 2024

    2024

  23. [31]

    R. J. Gould. Advances on the Hamiltonian problem—a survey. Graphs Comb., 19(1):7–52, 2003

    2003

  24. [32]

    R. K. Guy. Unsolved combinatorial problems. In Combinatorial Mathematics and its Applications , pages 121–127. Academic Press, 1971

    1971

  25. [33]

    P. E. Haxell. Tree embeddings. J. Graph Theory , 36(3):121–130, 2001

    2001

  26. [34]

    Hefetz, M

    D. Hefetz, M. Krivelevich, and T. Szab´ o. Hamilton cycles in highly connected and expanding graphs. Combinatorica, 29(5):547–568, 2009

    2009

  27. [35]

    J. Hyde, N. Morrison, A. M¨ uyesser, and M. Pavez-Sign´ e. Spanning trees in pseudorandom graphs via sorting networks. Proc. Amer. Math. Soc. , 153(6):2353–2367, 2025

    2025

  28. [36]

    Keevash and K

    P. Keevash and K. Staden. The generalised Oberwolfach problem. J. Comb. Theory B , 152:281–318, 2022

    2022

  29. [37]

    J. H. Kim and N. C. Wormald. Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs. J. Comb. Theory B , 81(1):20–44, 2001

    2001

  30. [38]

    F. Knox, D. K¨ uhn, and D. Osthus. Approximate Hamilton decompositions of random graphs. Random Struct. Algorithms , 40(2):133–149, 2012

    2012

  31. [39]

    F. Knox, D. K¨ uhn, and D. Osthus. Edge-disjoint Hamilton cycles in random graphs.Random Struct. Algorithms, 46(3):397–445, 2015

    2015

  32. [40]

    Kohayakawa

    Y. Kohayakawa. Szemer´ edi’s regularity lemma for sparse graphs. In Foundations of Computational Mathematics, pages 216–230. Springer, 1997. 25

    1997

  33. [41]

    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

  34. [42]

    A. D. Korshunov. Solution of a problem of Erd˝ os and R´ enyi on Hamiltonian cycles in non-oriented graphs. Dokl. Akad. Nauk SSSR , 228:529–532, 1976

    1976

  35. [43]

    Krivelevich

    M. Krivelevich. On the number of Hamilton cycles in pseudo-random graphs. Electron. J. Comb. , 19(1):P25, 2012

    2012

  36. [44]

    Krivelevich and B

    M. Krivelevich and B. Sudakov. Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory , 42(1):17–33, 2003

    2003

  37. [45]

    Krivelevich and B

    M. Krivelevich and B. Sudakov. Pseudo-random graphs. In More sets, graphs and numbers , vol- ume 15 of Bolyai Soc. Math. Stud. , pages 199–262. Springer, 2006

    2006

  38. [46]

    Krivelevich and W

    M. Krivelevich and W. Samotij. Optimal packings of Hamilton cycles in sparse random graphs. SIAM J. Discrete Math. , 26(3):964–982, 2012

    2012

  39. [47]

    Krivelevich, B

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

    2001

  40. [48]

    K¨ uhn and D

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

    2013

  41. [49]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. Hamilton decompositions of regular expanders: applications. J. Comb. Theory B, 104:1–27, 2014

    2014

  42. [50]

    Lee and B

    C. Lee and B. Sudakov. Dirac’s theorem for random graphs. Random Struct. Algorithms, 41(3):293– 305, 2012

    2012

  43. [51]

    Montgomery

    R. Montgomery. Spanning trees in random graphs. Adv. Math., 356:106793, 2019

    2019

  44. [52]

    Montgomery, A

    R. Montgomery, A. M¨ uyesser, A. Pokrovskiy, and B. Sudakov. Approximate path decompositions of regular graphs. arXiv preprint arXiv:2406.02514 , 2024

    2024 arXiv

  45. [53]

    Perkovic and B

    L. Perkovic and B. Reed. Edge coloring regular graphs of high degree. Discrete Math., 165/166:567– 578, 1997

    1997

  46. [54]

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

    1976

  47. [55]

    D. K. Ray-Chaudhuri and R. M. Wilson. Solution of Kirkman’s schoolgirl problem. InCombinatorics (Proc. Sympos. Pure Math., Vol. XIX) , pages 187–203. Am. Math. Soc., 1971

    1971

  48. [56]

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

    1994

  49. [57]

    Sauer and J

    N. Sauer and J. Spencer. Edge disjoint placement of graphs. J. Comb. Theory B , 25(3):295–302, 1978

    1978

  50. [58]

    J. Spencer. A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Am. Math. Soc., 195(910), 2008

    2008

  51. [59]

    B. Sudakov. Robustness of graph properties. In Surveys in Combinatorics 2017 , volume 440 of LMS Lect. Note Ser. , pages 372–408. Cambridge Univ. Press, 2017. 26

    2017

  52. [60]

    Sudakov and V

    B. Sudakov and V. H. Vu. Local resilience of graphs. Random Struct. Algorithms , 33(4):409–433, 2008

    2008

  53. [61]

    Szemer´ edi

    E. Szemer´ edi. Regular partitions of graphs. In Probl` emes combinatoires et th´ eorie des graphes (Colloq. Internat. CNRS, Orsay, 1976) , pages 399–401. CNRS, 1978. A Appendix A.1 The extendability method To find path-like structures in expander graphs, we use an embedding t...

    1976

  54. [62]

    We also need a modification of Lemma 3.6 in [19]

    That is, the proof of Lemma 3.5 in [19] also proves Lemma A.12. We also need a modification of Lemma 3.6 in [19]. Lemma A.13. Suppose 0 < 1/n ≪ β, 1/D ≪ 1. Let G1 be an n-vertex bipartite with bipartition V1 ∪ V2, and let G2 be a βn-bipartite-joined graph with parts V1, V2, an...

Pith tools

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