{"id":"b185156a-5a7f-473a-91ff-eaf4858da80f","arxiv_id":"2507.22807","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For pseudorandom graphs with large spectral gap, every subgraph with minimum degree above d/2 is Hamiltonian, and the whole edge set can be packed into, and covered by, about d/2 Hamilton cycles.","lead":"This paper proves that sparse pseudorandom graphs, which look random while being deterministic, remain Hamiltonian even after losing many edges, and that their edges can be almost perfectly grouped into Hamilton cycles. It settles, up to small error terms, long-standing conjectures about Hamilton decompositions of such graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unproved/deferred expander lemmas (Theorem 4.1; Lemma 5.3 and its appendix dependencies) are the main load-bearing risk; no concrete error found, but Theorem 1.8 needs full proofs or exact references.","rationale":"The reader's weakest-assumption analysis identifies Theorem 4.1, and I agree that this is a real gap: it is stated without proof and is not a formal special case of Theorem 1.2 because bipartite graphs fail the general joinedness condition for sets inside one part. However, for the strongest claim singled out (Theorem 1.8), the more directly load-bearing object is Lemma 5.3 and the appendix lemmas it uses, since the packing and covering proofs in Section 6 rely on Lemma 5.3, not on Theorem 4.1. Theorem 4.1 is load-bearing for the resilience result (Theorems 1.4/1.5), but the reader's emphasis on it as the weakest assumption for all central claims is slightly off-center. The manuscript does contain substantial independent scaffolding: the proof of Theorem 3.1 (sparse regularity partition into bipartite expanders) is detailed, the random edge-splitting argument in Section 6 is coherent, and Lemma 5.3 itself has a long proof with only specific sublemmas deferred. I found no circularity and no clearly false step. The main risk is verification risk: several lemmas are promised to follow from 'analogous arguments' in [19], and in a subject where expansion constants and joinedness thresholds matter, such deferrals can hide a subtle mismatch. This supports a CONDITIONAL verdict rather than an ACCEPT. Since the reader already assigned CONDITIONAL, my read does not change the verdict.","tokens_in":37848,"tokens_out":25528,"duration_ms":287540,"concrete_test":"Independently write out a complete proof of Lemma 5.3 by adapting [19] step by step, tracking every use of the bipartite setting and the bounded-G2-edge constraint; begin with the rotation argument in Lemma 5.6 (adapted from Lemma 3.7 of [19]) and verify that it produces a (2,βn,H)-bounded G2-edge without exceeding the claimed expansion budget. Separately, prove Theorem 4.1 for bipartite C-expanders, checking at every point where [19] uses general n/(2C)-joinedness that the bipartite m/(2C)-bipartite-joinedness suffices, especially when the two endpoint sets may lie inside the same part. If the proof requires an extra hypothesis, the theorem statements need amendment; if it goes through unchanged, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central decomposition theorem (Theorem 1.8) stands on Lemma 5.3, whose proof is not fully self-contained: it invokes Lemma 5.5, Lemma 5.6, Lemma 5.8 and, in the appendix, Lemma A.7 ('We omit the proof as the proof is same'), Lemma A.12/A.13/A.17 ('the proof ... also proves'), all adapted from [19]. None of these adaptations is written out. The identical gap is explicit in Theorem 4.1 ('We do not give an explicit proof ... follows from the analogous arguments'), and this theorem is not a literal consequence of Theorem 1.2 in [19]: a bipartite graph cannot satisfy the general C-expander joinedness condition for two sets inside the same part, so the bipartite version genuinely requires a separate argument. If the analogous arguments in [19] need a stronger expansion or joinedness condition than stated, both Theorem 1.5 (resilience) and the packing/covering proof of Theorem 1.8 are affected. One concrete unaddressed point inside the proof of Lemma 5.3: Lemma 5.5 is applied to a linear forest F_1^0 obtained from Lemma 2.5, which only guarantees at most 2δn paths, without the length bound n^0.15 or the lower bound n^0.9 on the number of paths; the manuscript does not explain how to refine F_1^0 so that condition (ii) of Lemma 5.5 holds. No fatal flaw was found; the risk is that these deferred proofs conceal a condition at the stated parameters.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":38082,"tokens_out":3519,"duration_ms":38047,"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":[{"comment":"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.","section":"Section 4, Theorem 4.1"},{"comment":"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.","section":"Section 5.3, Claim 9 and Lemma 5.5"},{"comment":"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.","section":"Section 5.2 and Appendix A.3"},{"comment":"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.","section":"Appendix A.2, Lemma A.7"}],"minor_comments":[{"comment":"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.","section":"Section 2.4, Lemma 2.13"},{"comment":"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.","section":"Section 5, Definition 5.1"},{"comment":"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.","section":"Section 5.3, proof of Lemma 5.3"},{"comment":"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.","section":"Section 6.1, proof of Theorem 1.6"},{"comment":"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.","section":"Section 1, Theorem 1.8"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The manuscript addresses an important problem and the overall strategy is credible, but the submitted version is not fully self-contained at several load-bearing points. The most pressing issue is Theorem 4.1, which is used directly in the resilience proof and is only claimed to follow by analogy. The appendix lemmas A.7, A.12, A.13 and A.17 are also formally unproved in this version. If the authors add a complete appendix with these proofs (or make the dependence on [19] precise by stating and proving the exact adapted statements), the paper would be ready for serious consideration; as it stands, the central claims cannot be fully verified from the text alone."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main results are as good as the abstract claims: constant d/λ resilience at the Dirac threshold and approximate Hamilton decompositions, both optimal up to the epsilon terms. The (η,β,p)-sparsity framework is a genuine improvement over the (n,d,λ) setting and lets the authors get the Sudakov–Vu log-type bound down to a constant. Theorems 1.4–1.8 are new and the packing/covering theorem is a substantial step toward the suggested exact decomposition conjecture.\n\nWhat I like: the structure is sound, the sparse-regularity lemma is used carefully, and the random edge-splitting/dyadic analysis in Section 6 is a clean way to control the m-max degree. The authors are honest about where proofs are deferred, and the deferred lemmas come from a track-record paper that is itself a major result.\n\nThe soft spots are exactly where the reader put them, though I’d phrase them as verification debt rather than errors. Theorem 4.1 is not proved, and it is not a literal restatement of Theorem 1.2 from [19]—the bipartite version with joinedness for cross-part sets needs its own argument. Similarly, Lemma 5.3 rests on Lemma 5.5, whose proof in the appendix in turn cites Lemma A.7/A.12/A.13/A.17 as ‘same proof’ or ‘also proves’ adaptations. None of these adaptations is written out. The stress-test note about Lemma 5.5’s application to F_1^0 is fair: Lemma 2.5 gives at most 2δn paths with no length bounds, and the manuscript does not spell out how to refine it to satisfy condition (ii) of Lemma 5.5. I did not find a concrete contradiction, and the hierarchical constant choices seem to leave room for such a refinement, but it is exactly the kind of gap that can hide a missing condition.\n\nMinor: the paper repeatedly uses ‘we omit the proof’ for standard lemmas (2.10, 2.11) that are not hard, and the conclusion claims a tower-type dependency on 1/γ, which is consistent with the method rather than a flaw.\n\nThis paper deserves a serious referee. The main theorems are important enough that the referee time is justified even if verification is heavy. The right decision is to send to an expert in sparse expanders and ask specifically: (i) write out or precisely reference a proof of Theorem 4.1, (ii) reconcile Lemma 2.5’s output with Lemma 5.5’s condition (ii), (iii) confirm that the adaptations in the appendix do not require stronger expansion parameters. My own reading says these are likely fixable, but they are load-bearing and should be explicit before the results are treated as established.","headline":"Strong paper: asymptotically optimal resilience and approximate Hamilton decompositions for constant spectral ratio (n,d,λ)-graphs, conditional on deferred expander proofs from [19].","tokens_in":38790,"tokens_out":1361,"would_cite":true,"duration_ms":15002,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C45","05C48","05C70","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Hamilton cycles","pseudorandom graphs","resilience","graph decompositions","sparse regularity lemma","(n,d,λ)-graphs","expander graphs","Hamilton-connectedness"],"falsifier":"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.","tokens_in":37579,"feed_emoji":"🔄","tokens_out":11001,"duration_ms":120816,"temperature":0.7,"pith_summary":"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.","feed_headline":"Optimal Hamilton decompositions for sparse pseudorandom graphs","feed_subtitle":"Minimum degree above d/2 forces a Hamilton cycle; edge-disjoint cycles reach (1±ε)d/2.","key_machinery":"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.","core_discovery":"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/γ).","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the expander Hamiltonicity theorem whose arguments Theorem 4.1 is stated to follow, so the resilience proof stands on it.","marker":"[19]"},{"why":"Provides the sparse regularity lemma used to partition sparse graphs into balanced bipartite expanders.","marker":"[40]"},{"why":"Supplies the path-partition theorem used to partition almost-regular subgraphs into few paths inside the sparse-augmentation proof.","marker":"[52]"},{"why":"Establishes the earlier resilience result for pseudorandom graphs with a larger spectral ratio, the baseline this paper improves to a constant.","marker":"[60]"},{"why":"Gives the previous approximate Hamilton packing result that does not apply to (n,d,λ)-graphs, motivating the new packing theorem.","marker":"[24]"},{"why":"States the classical minimum-degree Hamiltonicity theorem whose sparse analogue is established here.","marker":"[17]"}],"fun_headline_variants":["Sparse graphs hiding dense spots still pack optimal Hamilton cycles","Pseudorandom graphs: one-sided density bound gives optimal Hamilton cycles","D/2 threshold yields Hamilton cycles in sparse pseudorandom graphs","Optimal packing and covering of Hamilton cycles in sparse random-like graphs","Excluding dense subgraphs recovers optimal Hamilton decompositions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sparse graphs hiding dense spots still pack optimal Hamilton cycles","Pseudorandom graphs: one-sided density bound gives optimal Hamilton cycles","D/2 threshold yields Hamilton cycles in sparse pseudorandom graphs","Optimal packing and covering of Hamilton cycles in sparse random-like graphs","Excluding dense subgraphs recovers optimal Hamilton decompositions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000685,"raw_usage":{"total_tokens":3166,"prompt_tokens":1065,"completion_tokens":2101,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":2014}},"tokens_in":681,"tokens_out":2101,"duration_ms":17280,"temperature":1.0,"reasoning_tokens":2014,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T11:15:50.170857+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Kohayakawa","cited_arxiv_id":null,"evidence_quote":"Provides the sparse regularity lemma used to partition sparse graphs into balanced bipartite expanders."},{"cited_title":"Approximate path decompositions of regular graphs","cited_arxiv_id":"2406.02514","evidence_quote":"Supplies the path-partition theorem used to partition almost-regular subgraphs into few paths inside the sparse-augmentation proof."},{"cited_title":"Sudakov and V","cited_arxiv_id":null,"evidence_quote":"Establishes the earlier resilience result for pseudorandom graphs with a larger spectral ratio, the baseline this paper improves to a constant."},{"cited_title":"Ferber, G","cited_arxiv_id":null,"evidence_quote":"Gives the previous approximate Hamilton packing result that does not apply to (n,d,λ)-graphs, motivating the new packing theorem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the classical minimum-degree Hamiltonicity theorem whose sparse analogue is established here."}],"review_version":1}