{"id":"4789c05c-87e7-4621-99e0-fdf111137d85","arxiv_id":"2608.06358","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"An absolute constant C suffices for bounded-degree tree universality in G(n, C ln n/n), and cycle-factor universality is optimal up to constants via depth-optimal linking systems.","lead":"This paper shows that a sparse random graph with about C ln n edges per vertex already contains a copy of every n-vertex tree of bounded degree, for one fixed constant C that does not grow with the degree bound. It also determines, up to a constant factor, the shortest cycle girth for which such random graphs contain every sufficiently high-girth cycle factor.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 6.7's termination and layer-size bounds for Algorithm 6.6 are asserted, not proved; Proposition 6.16's many-to-one matching and the constant-size layer-vector union bound both depend on them.","rationale":"I agree with the reader's identification of the load-bearing spot. The central claim of Theorem 1 requires an absolute constant C and a proof for every bounded Delta, and the T2 case is where the new absorption machinery is deepest. The reduction to a constant number of layer-size vectors is exactly what makes the union bound feasible, and that reduction is Lemma 6.7. The lemma's proof is a short paragraph whose crucial assertion about |S_i| is not derived from the algorithm: it is not shown that the number of shifted roots is forced to lie in the claimed interval uniformly over all trees in T'_2. If the algorithm can stop with a layer size outside Lambda_Gamma, or with more than delta_2 alpha shifted vertices, then Proposition 6.16 cannot be applied and the embedding of the layers L_1,...,L_Gamma fails. I do not claim the lemma is false; I claim the written proof does not establish it. The T3 sketch in Section 6.3 is also a gap in the written proof, as the reader notes, but it is a presentation and verification gap rather than the structural keystone of the new argument, so I focus the attack on Algorithm 6.6. This supports keeping the conditional verdict: the concern is concrete, testable, and central, but it is not a demonstrated falsification.","tokens_in":58567,"tokens_out":29346,"duration_ms":354765,"concrete_test":"Re-derive Lemma 6.7 as an induction on i: from the stopping rule |L_i| <= lambda_i + Delta^Gamma, prove either that |S_i| lies in [delta_1^i alpha / Delta^Gamma, 2 delta_1^i alpha] or exhibit a tree where S_{i-1} is exhausted before the layer enters the target interval. Run this derivation on the extremal spider forest (every root in D_{Gamma+1} with Delta legs of length Gamma) and on a complete Delta-ary truncation, tracking |L_i| and S_i symbolically for Delta = 3 and Gamma = 27. If either tree produces a final layer-size vector outside Lambda_Gamma or more than delta_2 alpha shifted vertices, Lemma 6.7 is false and the T2 absorption guarantee in Proposition 6.16 collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The hard T2 case rests on Lemma 6.7, which claims that Algorithm 6.6 always terminates with all layer sizes in the bounded set Lambda_Gamma defined in (16) and with the total number of shifted vertices |L*_2 cup ... cup L*_{Gamma+1}| at most delta_2 alpha. The proof, however, does not verify the key invariant. It states that 'the final size of S_i is between delta_1^i alpha / Delta^Gamma and 2 delta_1^i alpha' and uses this to conclude termination and the shifted-vertex bound, but no derivation from the stopping rule is given. The decrease in |L_i| from one shift depends on the pruned descending tree and can be anywhere between 1 and Delta^Gamma, so it is not shown that the available roots in S_{i-1} \\ S_i suffice before |L_i| enters [lambda_i, lambda_i + Delta^Gamma], nor that the process cannot exhaust this set for some T in T'_2. If such a tree exists, its layer-size vector is not covered by the constant-size union bound over Lambda_Gamma, and the expansion estimates in Proposition 6.16, Claims 6.17-6.19, are not available because they are proved only under the layer-size and shifted-vertex assumptions of Lemma 6.7. This is the load-bearing point of the absorption argument for T2, so the correctness of Lemma 6.7 is the first thing that must be settled.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a framework for proving universality results in sparse random graphs via linking systems of optimal depth. The main results are: Theorem 1, which asserts the existence of an absolute constant C such that, for every fixed Δ≥2, whp G(n,C ln n/n) is universal for all n-vertex trees of maximum degree at most Δ, thereby answering a question of Montgomery; Theorem 2, which constructs (a,b;k)-linking systems of depth Θ(ln n/(ψ ln ln n)) for p=C(ln n)^ψ/n (with Corollary 3 for ψ=1); and Theorem 4, which establishes universality for cycle factors of girth at least K ln n/(ψ ln ln n), optimal up to an absolute constant. The proof decomposes the tree family into T1 (trees with many long bare paths), T2 (trees with an intermediate number of leaves), and T3 (trees with very many leaves). The hard T2 case uses a leaf-cutting and shifting procedure that reduces the number of layer-size vectors to a constant, followed by many-to-one matching constructions. The T1 case is reduced to linking systems and matchings, while T3 is treated by a simplified version of the T2 argument.","tokens_in":58887,"tokens_out":16827,"duration_ms":164991,"significance":"If the proofs are completed as intended, Theorem 1 resolves an open problem of Montgomery and a conjecture of Kahn, with the notable feature that the constant C is independent of Δ. The optimal-depth linking system result is a significant technical advance over sorting-network based constructions, and Theorem 4 gives cycle-factor universality that is tight up to an absolute constant factor. The paper is careful to build on prior results (the fractional expectation-threshold theorem of Frankston–Kahn–Narayanan–Park, Montgomery's rollback lemma, and the Alon–Krivelevich–Sudakov almost-spanning tree theorem) without circularity, and it provides several explicit, quantitative probabilistic lemmas (e.g., Lemmas 3.7, 3.8, 3.11). The claims are falsifiable and the constants are explicit enough to be checked, although the exposition is long and dense.","major_comments":[{"comment":"The termination proof of Algorithm 6.6 is incomplete. The statement 'at every step when i=i, L_i loses between 1 and Δ^Γ vertices and, therefore, the final size of S_i is between δ_1^i α/Δ^Γ and 2δ_1^i α' omits the essential comparison between the number of shifts and the number of available roots. To justify the claimed bounds one must use the definition of λ_i (the largest element of {20α + j δ_1^i α} not exceeding |L_i|-δ_1^i α) to show that the total reduction of |L_i| before stopping is Θ(δ_1^i α), and then combine this with the per-step reduction of at most Δ^Γ to bound the number of steps. One must also show that this number of steps is smaller than |S_{i-1}|, so that the process does not exhaust the available roots before entering the interval [λ_i, λ_i+Δ^Γ]. Neither of these steps appears in the proof. Since Lemma 6.7 supplies the bounded layer-size set Λ_Γ used in the union bound, and the shifted-vertex bound |L*_2 ∪ ... ∪ L*_{Γ+1}| ≤ δ_2 α used in Proposition 6.16, this gap is load-bearing for the T2-case. The argument appears repairable with a more detailed accounting, but as written the lemma is not proved.","section":"Section 6.1, Lemma 6.7"},{"comment":"The proof of T3-universality is explicitly presented as a sketch, with claims deferred by phrases such as 'one can verify' and 'similarly to Proposition 6.16'. Since T3 is one of the three families whose union is T_{n,Δ}, Theorem 1 depends on this case. The paper should provide a complete proof for T3 or a precise reduction to Montgomery's Case A that verifies the absolute-constant dependence on Δ. As it stands, the sketch does not constitute a proof of a load-bearing component of the main theorem.","section":"Section 6.3"}],"minor_comments":[{"comment":"In the line 'for every i∈[i,Γ+1]', the symbol i is used both for the current layer and for the loop variable; this should be relabeled (for example, using ℓ) to avoid confusion.","section":"Algorithm 6.6"},{"comment":"The definition of λ_i is written in a nonstandard form: 'max(20α+ (δ i 1α)N0)∩{1,...,|L i|−δ i 1α}'. It should be stated explicitly, for instance as λ_i := max{20α + j δ_1^i α : j ∈ N_0, 20α + j δ_1^i α ≤ |L_i| - δ_1^i α}.","section":"Algorithm 6.6"},{"comment":"The journal name 'Transaction of the American Mathematical Society' should be 'Transactions of the American Mathematical Society' in both occurrences.","section":"Abstract and Section 1.2"},{"comment":"In the proof of Proposition 6.8, the phrase 'the same same vertex v' should be 'the same vertex v'.","section":"Section 6.1.1"},{"comment":"The notation 'δ i 1' should be typeset as δ_1^i for readability; the same applies to 'δ 2' which should be δ_2.","section":"Section 6.1, proof of Lemma 6.7"}],"recommendation":"major_revision","confidential_remarks":"This paper addresses a significant open problem and the overall strategy is convincing, but the current version has two load-bearing gaps: the termination proof of Lemma 6.7 is too terse, and Section 6.3 is only a sketch. Both appear repairable within the scope of the manuscript, and I see no sign of circularity or of a fundamental error. I recommend inviting a revision that provides complete proofs of these parts."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this paper looks like it proves the right theorem. The absolute-constant tree universality (Theorem 1) answers Montgomery's question, and the cycle-factor result closes the log-log gap left by Kahn-Lubetzky-Wormald. The optimal-depth linking system in Corollary 3 is genuinely new, and the spread-improvement technique for path systems is a real contribution. I read the core architecture as coherent: T1 via linking systems plus matchings, T2 via layered leaf-cutting with absorption, T3 as a simplified version. The bookkeeping is heavy, but the strategy holds together.\n\nThe main soft spot is exactly where the stress-test points: Lemma 6.7. The termination of Algorithm 6.6 and the layer-size bounds are load-bearing for the T2 embedding, and the proof as written does not actually show the process cannot exhaust the available roots before each layer size enters the required interval. The statement that the final size of S_i is between delta_1^i alpha / Delta^Gamma and 2 delta_1^i alpha is asserted, not derived. This matters because Proposition 6.16 and Claims 6.17-6.19 only work for layer-size vectors in the constant-size set Lambda_Gamma. If some tree produced an off-menu layer-size vector, the union bound and the many-to-one matching argument would not cover it. I do not think this is fatal - the claim is plausible and likely follows from the stopping rule - but it needs to be settled before the paper is trusted.\n\nSecond gap: Section 6.3 calls the T3 universality proof a sketch. T3 is part of Theorem 1, so a sketch leaves a hole in the main theorem. It is the easy case and probably expands fine, but it is not a complete proof as written.\n\nMinor: the paper repeatedly defers divisibility and rounding issues. Normal for this community, but combined with the above it keeps the proof from being final form.\n\nThe citation pattern is honest: Montgomery, Alon-Krivelevich-Sudakov, Frankston-Kahn-Narayanan-Park are all used and credited correctly. No circularity. The new results are not repackaged old ones.\n\nVerdict: this is a major paper if the gaps close. It deserves a serious referee, not a desk reject. I would send it with specific instructions to check Lemma 6.7 and to require a full T3 proof. I would bring it to my reading group in the meantime.","headline":"Genuinely important results, but the proof has two open seams: Lemma 6.7's termination claim and the sketched T3 case; referee it with those checks.","tokens_in":59425,"tokens_out":2764,"would_cite":true,"duration_ms":29342,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"There is an absolute constant C>1 such that, with high probability, G(n,C ln n/n) contains every n-vertex tree of maximum degree at most Δ, for every fixed Δ; the same construction yields optimal girth bounds for all cycle factors.","keywords":["bounded-degree trees","tree universality","random graphs","linking systems","cycle factors","girth","bare paths","many-to-one matchings"],"falsifier":"For a fixed Δ and growing n, enumerate all n-vertex trees with at most exp($Δ^{5}$)α leaves and no Kα bare paths of length n/($K^{2}$α), and run the leaf-cutting plus shifting procedure on each one: finding a single tree whose final layer sizes fall outside the intervals [(20+jδ_1^i)α,(20+jδ_1^i)α+ΔΓ] for all allowed j would disprove the structural lemma on which the leaf-heavy universality proof rests.","tokens_in":58346,"feed_emoji":"🌲","tokens_out":6913,"duration_ms":80032,"temperature":0.7,"pith_summary":"This paper proves that a single absolute constant C>1 governs bounded-degree tree universality: with probability tending to 1 as n grows, the random graph G(n,C ln n/n) contains a copy of every n-vertex tree whose maximum degree is at most Δ, for every fixed Δ. Earlier results needed a constant C that grew with Δ, and deciding whether the constant could be made absolute was an open problem. The proof also determines, up to constant factors, the smallest girth ℓ for which G(n,p) contains every cycle factor of girth at least ℓ, covering all densities from C ln n/n up to $n^{{-1+o(1)}}$; at the lowest density the answer is ℓ≈ln n/ln ln n. The engine of the argument is a linking system of optimal depth, a graph that simultaneously realises every pairing of two boundary vertex sets by disjoint paths of a fixed length.","feed_headline":"One absolute constant embeds all bounded-degree trees","feed_subtitle":"At G(n,C ln n/n) every n-vertex tree of degree at most Δ appears, and cycle-factor girths are tight up to constants.","key_machinery":"The central object is an (a,b;k)-linking system: a graph that, for every permutation σ of [m], contains vertex-disjoint paths of length k pairing each a_i with b_{σ(i)}. The paper constructs such systems of depth k≈C ln n/(ψ ln ln n) in G(n,C(ln n)^ψ/n), which is tight up to a constant factor by a union-bound lower bound, and uses them to embed the families of trees and cycle factors whose many disjoint long paths can be threaded between pre-arranged matchings. For the complementary leaf-heavy trees, the load-bearing mechanism is a leaf-cutting layering of the tree together with a shifting procedure that forces the layer sizes to fall into a bounded set of intervals, so that a union bound over only constantly many size vectors is possible; generalized Hall-type many-to-one matchings then absorb each layer into the host graph.","core_discovery":"The central claim is that the threshold for universality among bounded-degree trees has no hidden dependence on the degree bound: at edge probability C ln n/n, with C an absolute constant, the binomial random graph is whp universal for the family T_{n,Δ} of all n-vertex trees of maximum degree at most Δ, simultaneously for every fixed Δ. The proof splits trees into those with many long bare paths, which are embedded by routing each path through a chain of matchings joined by a linking system, and those with many leaves, which require a leaf-cutting layering with many-to-one matchings. A companion theorem gives, for every p with C ln n/n ≤ p = $n^{{-1+o(1)}}$, the minimum girth ℓ up to an absolute multiplicative constant for which the random graph whp contains all cycle factors of girth at least ℓ; at p=C ln n/n this minimum is Θ(ln n/ln ln n).","pith_inferences":["If the depth of linking systems can be pushed from C ln n/ln ln n to (1+ε) ln n/ln ln n at p=(1+ε) ln n/n, the paper's reductions would likely deliver sharp thresholds for both tree universality and cycle-factor universality at the connectivity threshold.","The spread-improvement idea—prepare a rich family of prefixes in one random subgraph, then apply the fractional expectation-threshold theorem to complements of those prefixes in a second subgraph—looks transferable to other spanning embedding problems where the minimal fragments are contained in too many completions.","The layer-shifting procedure may also suggest a route toward hitting-time statements in the random graph process, though the large absolute constant C in the current proof makes such a transfer far from automatic."],"forward_implications":["For every fixed Δ, no Δ-dependent factor appears in the constant multiplying ln n/n in the tree-universality threshold, so the threshold is C ln n/n up to an absolute constant.","At p=C ln n/n, every cycle factor of girth at least Θ(ln n/ln ln n) appears whp, and this girth bound cannot be improved by more than a constant factor.","For all densities C ln n/n ≤ p = n^{-1+o(1)} with p=C(ln n)^ψ/n, cycle factors of girth at least K ln n/(ψ ln ln n) appear whp, matching the union-bound lower bound up to constants.","The same linking systems yield universality for graphs obtained by subdividing every edge of a bounded-degree graph by at least 24 ln n/ln ln n vertices, with a constant independent of Δ, and this implies spanning-subdivision minor universality in this density range.","The optimal-depth linking systems also give a new route to embedding spanning structures in sparse random graphs just above the connectivity threshold, where earlier linking-system constructions needed depth Θ((ln n)^2) or larger."],"supporting_citations":[{"why":"Supplies the earlier tree-universality theorem with constant depending on Δ and poses the question of removing that dependence, which Theorem 1 answers.","marker":"[70]"},{"why":"Supplies the nearly-spanning universality theorem used to embed the complement forest into V1 before the long bare paths are threaded.","marker":"[8]"},{"why":"Supplies the rollback technique used in multiple embedding steps for the leaf-heavy trees.","marker":"[34]"},{"why":"Supplies the fractional expectation-threshold theorem used to prove the existence of the path systems underlying the optimal linking systems.","marker":"[40]"},{"why":"Supplies the earlier cycle-factor universality theorem at higher densities that Theorem 4 extends down to the sparse regime.","marker":"[37]"},{"why":"Supplies the earlier deep bound on cycle factors in random graphs whose corollary is significantly improved by the paper's optimal-girth statement.","marker":"[57]"}],"fun_headline_variants":["Optimal linking systems prove tree universality in sparse random graphs","Absolute constant threshold for all bounded-degree trees in G(n,p)","Tree universality and tight cycle-factor girth in random graphs","All bounded-degree trees appear at C ln n/n in random graph"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hard leaf-heavy case stands or falls on the structural lemma that the leaf-cutting plus shifting procedure always terminates with every layer size inside one of a bounded (as a function of Δ) set of intervals and with the number of shifted vertices at most δ2 α; if some bounded-degree tree forced a layering outside those intervals, the constant-size union bound and the absorption matching would no longer be guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["Optimal linking systems prove tree universality in sparse random graphs","Absolute constant threshold for all bounded-degree trees in G(n,p)","Tree universality and tight cycle-factor girth in random graphs","All bounded-degree trees appear at C ln n/n in random graph"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000227,"raw_usage":{"total_tokens":1498,"prompt_tokens":996,"completion_tokens":502,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":430}},"tokens_in":612,"tokens_out":502,"duration_ms":6489,"temperature":1.0,"reasoning_tokens":430,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:27:11.124514+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed Δ and growing n, enumerate all n-vertex trees with at most exp($Δ^{5}$)α leaves and no Kα bare paths of length n/($K^{2}$α), and run the leaf-cutting plus shifting procedure on each one: finding a single tree whose final layer sizes fall outside the intervals [(20+jδ_1^i)α,(20+jδ_1^i)α+ΔΓ] for all allowed j would disprove the structural lemma on which the leaf-heavy universality proof rests.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the nearly-spanning universality theorem used to embed the complement forest into V1 before the long bare paths are threaded."},{"cited_title":"Draganić, M","cited_arxiv_id":null,"evidence_quote":"Supplies the rollback technique used in multiple embedding steps for the leaf-heavy trees."},{"cited_title":"Frankston, J","cited_arxiv_id":null,"evidence_quote":"Supplies the fractional expectation-threshold theorem used to prove the existence of the path systems underlying the optimal linking systems."},{"cited_title":"Ferber, G","cited_arxiv_id":null,"evidence_quote":"Supplies the earlier cycle-factor universality theorem at higher densities that Theorem 4 extends down to the sparse regime."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the earlier deep bound on cycle factors in random graphs whose corollary is significantly improved by the paper's optimal-girth statement."}],"review_version":1}