{"id":"28fa3cd4-bc33-4ff5-ae03-7a6be01e0453","arxiv_id":"2506.23970","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Erdős-Rényi and random regular graphs asymptotically satisfy the Itai-Zehavi conjecture, containing (1-o(1))np and (1-o(1))d independent spanning trees, with a d/4-factor guarantee for sparse regular graphs.","lead":"Random graphs with average degree tending to infinity faster than log n, and random regular graphs with degree growing faster than log n, asymptotically satisfy the Itai-Zehavi conjecture: they contain nearly the maximum possible number of independent spanning trees rooted at any vertex. This answers a question of Draganić and Krivelevich and gives a constant-factor version for sparse regular graphs.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Odd-n transfer: Lemma 4.24 only yields constant probability for fixed ε, not w.h.p.; Theorem 4.1 for odd n does not follow as written.","rationale":"The paper's main results are attractive, and Theorem 1 (Erdős–Rényi case) appears sound: the sprinkling, core-set, and matching arguments are coherent, and the dense-regular reduction via stochastic domination (Theorem 2.5) is standard. The sparse regular case is where the load-bearing weakness sits. The reader's verdict flagged Theorem 2.6 (one-sided contiguity from the companion paper) as the weakest assumption; I agree that this dependency is worth a verification step, but I do not think it is the most dangerous concern because it is an explicit external theorem and likely correct. The sharper problem is internal: the odd-n transfer through operation op only proves a constant-probability statement (Lemma 4.24), while the theorem needs a w.h.p. statement with o(n) exceptional vertices. The proof of Lemma 4.24 is quantitative only for fixed ε; it does not supply the uniformity to set ε=ε_n→0. My concrete check targets exactly this. If the check confirms p_bad is not o((log n)^{−2}), the first part of Theorem 2 is currently unproven for odd n, and the paper needs a strengthened averaging argument or a different odd-n transfer. If the check shows the bound is sufficient with explicit constants, the concern is resolved. I therefore keep the reader's CONDITIONAL verdict: the result is plausible but the proof as written needs repair.","tokens_in":33068,"tokens_out":19358,"duration_ms":198896,"concrete_test":"Re-run the proof of Lemma 4.18 with ε=ε_n=1/log n, keeping explicit constants. Define p_bad(n) = P(random (r,S) pair fails to admit k strong ISTs). Check whether p_bad(n)=o((log n)^{−2}). From Claim 4.19 the per-pair failure is at least (log n)^{−5}; after the union bound over k=O((log n)^2) in Claim 4.20, the best bound is p_bad ≥ c (log n)^{−1}. If this lower bound holds, then p_bad/ε_n^2 = Ω(log n), so the Markov argument in Lemma 4.24 cannot yield μ_d(U(D_{ε_n}))=1−o(1); hence the odd-n case of Theorem 4.1 is unsupported as written. If instead p_bad can be shown to be o((log n)^{−2}) with explicit constants, the gap closes.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 4.2, Lemma 4.24 is stated as: for every ε>0, P(Gu(n,d)∈U(D_ε))≥1−ε. Theorem 4.1 for odd n, however, asserts a w.h.p. bound with o(n) exceptional vertices, i.e., requires the property D_{ε_n} for some ε_n→0. The proof of Lemma 4.24 cannot pass to ε_n→0: Lemma 4.18 is proved only for fixed ε, and its averaging argument gives a bad-root probability bound of order o(1)/ε^2. The failure probability for a random root–matching pair is at least (log n)^{−5} from Claim 4.19, and the union bound over k=O((log n)^2) in Claim 4.20 leaves only an o(1) (not o((log n)^{−2})) per-pair error. Hence for ε=1/log n the Markov estimate is o(1)/ε^2 = Ω(log n) unless additional quantitative uniformity is supplied, which it is not. Thus the final line of Section 4.2, 'Theorem 4.1 for odd n follows by combining Lemma 4.22 and Lemma 4.24,' is unjustified. This is an internal gap in the sparse regular proof, independent of the external contiguity theorem, and it affects the first part of Theorem 2 for every odd n.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves asymptotic versions of the Itai–Zehavi conjecture for two random graph models. For G(n,p) with np=\\omega(\\log n), it shows that with high probability every root vertex admits (1-o(1))np independent spanning trees (Theorem 1). For G(n,d), it shows that with high probability (1-o(1))n vertices admit \\lfloor d/4\\rfloor ISTs for every d\\in[4,n-1], and when d=\\omega(\\log n) every vertex admits (1-o(1))d ISTs (Theorem 2). The Erd\\H{o}s-R\\'enyi proof uses a two-round sprinkling decomposition, a BFS construction of disjoint core sets, and a bipartite perfect-matching step. The random-regular proof works in the 1-factorisation-weighted model G''(n,d), groups the d matchings into \\lfloor d/4\\rfloor triples plus one matching each, builds BFS trees in the triples, and repairs bad vertices by rerouting along the reserved matchings. The odd-n case is handled by deleting an induced matching from G(n-1,d), adding a vertex, and transferring via a coupling based on Strassen's theorem.","tokens_in":33335,"tokens_out":10574,"duration_ms":111818,"significance":"Assuming the companion-paper contiguity statement and a repaired odd-n transfer, the results are substantial: they answer the question of Dragani\\'c and Krivelevich in the random setting, give the first constant-factor IST result for sparse random regular graphs, and the G(n,p) statement is asymptotically optimal and algorithmic. The proof is detailed and mostly coherent, with explicit probabilistic estimates and a clear structural decomposition. The main reservations are that the odd-n conclusion is not justified as written and that a central transfer theorem is imported from the authors' own companion paper [20].","major_comments":[{"comment":"The deduction of Theorem 4.1 for odd n is not justified. Lemma 4.24 is a fixed-ε statement: it asserts, for every ε>0, P(Gu(n,d)∈U(D_ε))≥1−ε, and the proof actually ends with the weaker bound 1−3ε. Theorem 4.1, however, requires a single high-probability event D_{ε_n} with ε_n→0. The proof of Lemma 4.18 supplies P(G''(n−1,d)∈C^s_ε)=1−o(1) only for fixed ε, and the Markov step used to convert a random-root success statement into the fraction of roots and matchings required by C^s_ε incurs a 1/ε factor. Therefore, for a sequence ε_n→0, the inequality λ(H′)≥1−ε_n−o(1) need not hold, and the final line 'Theorem 4.1 for odd n follows by combining Lemma 4.22 and Lemma 4.24' does not follow. This affects the first part of Theorem 2 for every odd n.","section":"§4.2 (Step 4), Lemma 4.24"},{"comment":"The sparse regular proof transfers all statements from the 1-factorisation-weighted model G''(n,d) to the uniform model G(n,d) using Theorem 2.6, a one-sided contiguity result quoted from the authors' companion paper [20, Theorem 1.5] without proof. This theorem is load-bearing: if it fails at the required scale, the constant-factor statement ⌊d/4⌋ for d≤(log n)^2 is not established for G(n,d). Please include a proof, or a precise statement with quantitative error bounds, or make the dependency fully explicit and publicly verifiable.","section":"§2, Theorem 2.6"}],"minor_comments":[{"comment":"The proof concludes with P≥1−3ε while the lemma states P≥1−ε; although for fixed ε the gap can be closed by rescaling ε to ε/3, the text should say this explicitly rather than asserting the lemma follows directly.","section":"§4.2, proof of Lemma 4.24"},{"comment":"The claim conditions on the high-probability event from Lemma 4.14 that there are at most β^20 unsafe vertices, but the conditioning is only implicit; making it explicit would clarify the union bound that follows.","section":"§4.1.4, Claim 4.15"},{"comment":"In the bipartite graph W, the notation 'op(Hd) with multiplicity' is used without defining the multiplicity; a sentence stating that B contains one copy for each preimage under op would improve readability.","section":"§4.2, Definition 4.23 and Claim 4.26"},{"comment":"After proving that a uniformly random root and a uniformly random matching are good with high probability, the proof says this is sufficient for the conclusion C^s_ε, but the averaging/Markov step that turns this into a statement about (1−ε)n roots and a (1−ε) fraction of matchings is left implicit.","section":"§4.2, Lemma 4.18"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically serious but depends essentially on the authors' companion work [20] for the contiguity transfer; the editor may wish to verify that Theorem 2.6 of [20] is publicly available and accepted. The odd-n gap is internal and fixable with additional quantitative uniformity, so I do not see grounds for rejection if the authors supply the missing argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth your time in two different ways. The Erdős-Rényi half of this (Theorem 1) is a genuine advance: for np = ω(log n) they get (1−o(1))np independent spanning trees rooted at every vertex, which is asymptotically optimal and answers Draganić and Krivelevich's question in that regime. I read the BFS-core-plus-matching proof through and the steps cohere: the sprinkling split, the disjoint core sets with their unexplored boundaries, the bipartite matching over the connecting layer, the union bounds. The dense regular case follows honestly from the Gao–Isaev–McKay sandwich theorem combined with Theorem 1.\n\nThe sparse regular proof is where I want to slow down. The even-n argument is an intricate construction — the 1-factorisation model, the random-overlay technique, the rerouting of bad vertices — and on a first read it holds together. But it rests on two results from the authors' own companion paper [20]: the one-sided contiguity (Theorem 2.6) and the overlay no-double-edge estimate (Lemma 4.7). Both are load-bearing and neither is proved here. That is normal practice, but a referee has to check [20] before signing off.\n\nThe genuine gap is the odd-n transfer in Section 4.2. The stress-test note is right, though I'd sharpen it. The 1−3ε versus 1−ε discrepancy inside Lemma 4.24 is cosmetic — since ε is a free parameter, renaming ε/3 fixes the lemma statement. The real problem is the quantifier jump in Step 4. Lemma 4.24 is a fixed-ε statement with no rate of convergence; Theorem 4.1 for odd n needs U(D_{ε_n}) with ε_n → 0 to hold with probability 1−o(1). The chain loses a constant factor at each step, and the averaging in Lemma 4.18 only controls the bad-root fraction up to a factor like o(1)/ε², so you cannot pass to ε_n → 0 without redoing the bookkeeping with explicit rates. The sentence \"Theorem 4.1 for odd n follows by combining Lemma 4.22 and Lemma 4.24\" is not justified as written. This affects the ⌊d/4⌋ statement for every odd n in the sparse regime.\n\nOne smaller note: the even-n proof also uses the random-root averaging in the fixed-ε, then 'therefore almost all vertices' form. There the failure terms are explicit polynomial bounds, so extracting a rate is routine; I count that as bookkeeping, not a gap.\n\nWho reads this: random graph theorists and anyone working on spanning tree packings under vertex-connectivity assumptions. Theorem 1 is citable on its own and will survive review; the sparse case needs a real fix to the odd-n step before Theorem 2 stands whole. Send it to a good referee — the ER result alone justifies the time — but make sure the referee chases both the companion paper and the odd-n quantifier.","headline":"The Erdős–Rényi theorem is new, asymptotically optimal, and looks sound; the sparse regular-graph proof has a real gap in the odd-n transfer that must be fixed, and it leans on unproved results from a companion paper.","tokens_in":33863,"tokens_out":16721,"would_cite":true,"duration_ms":168641,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C05","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random graphs nearly meet the Itai–Zehavi spanning-tree bound","keywords":["independent spanning trees","Itai–Zehavi conjecture","random graphs","Erdős–Rényi graph","random regular graphs","vertex connectivity","spanning trees","sprinkling"],"falsifier":"Test the one-sided contiguity theorem at d = (log n)^2 by computing, say, the probability of a given small cut in both the uniform random d-regular graph and the 1-factorisation-weighted model; if one model accepts a property with high probability while the other rejects it, the transfer breaks and the sparse-regular theorem would not follow.","tokens_in":1838,"feed_emoji":"","tokens_out":3379,"duration_ms":84102,"temperature":0.7,"pith_summary":"This paper tries to prove an approximate version of the Itai–Zehavi conjecture for two random graph models. The conjecture says that every vertex of a d-vertex-connected graph can be the root of d spanning trees whose root-to-vertex paths are internally vertex-disjoint. The authors show that when the edge probability satisfies np = ω(log n), the random graph G(n,p) contains, with high probability, (1−o(1))np such trees rooted at every vertex, asymptotically the maximum possible. For random d-regular graphs they prove that with high probability almost all vertices root ⌊d/4⌋ independent spanning trees, and when d = ω(log n) every vertex roots (1−o(1))d of them. These results positively answer a question posed by Draganić and Krivelevich.","feed_headline":"Random graphs nearly meet Itai–Zehavi tree bound","feed_subtitle":"Dense random graphs root nearly np independent spanning trees at every vertex; sparse regular graphs give a quarter.","key_machinery":"The Erdős–Rényi argument splits G(n,p) into two independent random graphs G1 and G2, uses breadth-first search in G1 to build disjoint core sets attached to k = (1−ε)np neighbours of the root, and then uses G2 to attach every remaining vertex to the core sets through paths of length at most two; the final step is a perfect-matching argument in a bipartite Erdős–Rényi graph. The sparse regular argument works inside the 1-factorisation model G″(n,d), the union of d uniformly chosen edge-disjoint perfect matchings, grouped into k = ⌊d/4⌋ triples. Each triple forms a 3-regular graph whose breadth-first search supplies a candidate spanning tree, and the fourth matching of each group is used to reroute the few vertices whose root-to-vertex paths would collide. The proof transfers results from this model to G(n,d) via a one-sided contiguity theorem, and it handles odd n by reducing to an even graph on n−1 vertices and adding one new vertex as a leaf.","core_discovery":"The central claim is that the Itai–Zehavi bound is asymptotically attainable in random graphs. Theorem 1 states that for p = p(n) with np = ω(log n), with high probability every vertex r of G(n,p) is the root of (1−o(1))np independent spanning trees. Theorem 2 states that for d = d(n) ∈ [4,n−1], with high probability at least (1−o(1))n vertices r of the random d-regular graph G(n,d) root ⌊d/4⌋ independent spanning trees, and that when d = ω(log n), with high probability every vertex roots (1−o(1))d such trees. The d = ω(log n) regular case follows from the Erdős–Rényi result through a stochastic comparison between G(n,p) and G(n,d). The sparse regular case is proved in a model built from d edge-disjoint perfect matchings and then transferred to the uniform random regular graph.","pith_inferences":["The sparse-regime result depends on the one-sided contiguity theorem stated as Theorem 2.6 without proof in this paper; if that model equivalence fails at the relevant densities, the ⌊d/4⌋ conclusion is only established in the artificial 1-factorisation model.","The paper itself notes that the constant 1/4 could likely be pushed to 1/3 with a more technical presentation, and it identifies ⌊d/2⌋ as a natural structural barrier for its approach.","A direct testable extension is the authors' Conjecture 5.1: for p ≥ (log n)/n, verify whether G(n,p) contains as many independent spanning trees as its minimum degree, which would make the Itai–Zehavi conjecture exact on Erdős–Rényi graphs.","The random-overlay computations suggest the sparse-regular statement should survive for degrees up to n^{1/10}; closing the unproved contiguity gap at d = (log n)^2 would extend the result from the 1-factorisation model to the uniform random graph."],"forward_implications":["For Erdős–Rényi graphs with np = ω(log n), every vertex is simultaneously the root of (1−o(1))np independent spanning trees, so the Itai–Zehavi bound is attained up to a 1−o(1) factor for every root at once.","The same asymptotic bound transfers to random d-regular graphs with d = ω(log n), giving (1−o(1))d independent spanning trees rooted at every vertex.","For sparse random regular graphs with d ∈ [4, (log n)^2], almost all vertices root at least ⌊d/4⌋ independent spanning trees, the first linear-in-d constant-factor statement in this regime.","The Erdős–Rényi construction is algorithmic: the proof runs a randomised polynomial-time procedure that outputs the family of independent spanning trees with high probability.","The odd-n regular case is derived from an even graph on n−1 vertices together with one additional vertex attached as a leaf, so the argument is not interrupted by parity."],"supporting_citations":[{"why":"States the Itai–Zehavi conjecture that this paper approximates, and supplies the d=3 case.","marker":"[41]"},{"why":"Posed the question whether random graphs contain Θ(d) or Θ(np) independent spanning trees, which Theorem 1 and Theorem 2 answer.","marker":"[13]"},{"why":"Provides the one-sided contiguity theorem (Theorem 2.6) that transfers the sparse regular-graph result from the 1-factorisation model to G(n,d).","marker":"[20]"},{"why":"Recent sprinkling technique for random regular graphs that the sparse-regular proof adapts.","marker":"[22]"},{"why":"McKay's subgraph-counting theorem is used to count perfect matchings and extensions in dense graphs.","marker":"[31]"},{"why":"Supplies the perfect-matching theorem for bipartite Erdős–Rényi graphs used in Theorem 1, along with the Chernoff bound.","marker":"[24]"},{"why":"Sandwiching result comparing G(n,p) and G(n,d), used to deduce the d=ω(log n) case of Theorem 2.","marker":"[19]"}],"fun_headline_variants":["Random graphs asymptotically meet Itai–Zehavi bound","Itai–Zehavi holds for random graphs with high probability","Dense random graphs nearly maximize spanning tree roots","Sparse regular graphs get a quarter of Itai–Zehavi trees"],"cache_read_input_tokens":35968,"weakest_assumption_plain":"The proof for sparse random regular graphs relies on an unproved correspondence between the uniform random regular graph and a model built from edge-disjoint perfect matchings; if that correspondence fails at the required densities, the constant-factor result would not transfer to the actual random graph.","fun_headline_variants_meta":{"raw":{"variants":["Random graphs asymptotically meet Itai–Zehavi bound","Itai–Zehavi holds for random graphs with high probability","Dense random graphs nearly maximize spanning tree roots","Sparse regular graphs get a quarter of Itai–Zehavi trees"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000703,"raw_usage":{"total_tokens":3158,"prompt_tokens":919,"completion_tokens":2239,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":535,"completion_tokens_details":{"reasoning_tokens":2167}},"tokens_in":535,"tokens_out":2239,"duration_ms":20485,"temperature":1.0,"reasoning_tokens":2167,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:29:09.624580+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test the one-sided contiguity theorem at d = (log n)^2 by computing, say, the probability of a given small cut in both the uniform random d-regular graph and the 1-factorisation-weighted model; if one model accepts a property with high probability while the other rejects it, the transfer breaks and the sparse-regular theorem would not follow.","supporting_citations":[{"cited_title":"Zehavi and A","cited_arxiv_id":null,"evidence_quote":"States the Itai–Zehavi conjecture that this paper approximates, and supplies the d=3 case."},{"cited_title":"Draganić and M","cited_arxiv_id":null,"evidence_quote":"Posed the question whether random graphs contain Θ(d) or Θ(np) independent spanning trees, which Theorem 1 and Theorem 2 answer."},{"cited_title":"Hollom, L","cited_arxiv_id":null,"evidence_quote":"Provides the one-sided contiguity theorem (Theorem 2.6) that transfers the sparse regular-graph result from the 1-factorisation model to G(n,d)."},{"cited_title":"Isaev, B","cited_arxiv_id":null,"evidence_quote":"Recent sprinkling technique for random regular graphs that the sparse-regular proof adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"McKay's subgraph-counting theorem is used to count perfect matchings and extensions in dense graphs."},{"cited_title":"Janson, T","cited_arxiv_id":null,"evidence_quote":"Supplies the perfect-matching theorem for bipartite Erdős–Rényi graphs used in Theorem 1, along with the Chernoff bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Sandwiching result comparing G(n,p) and G(n,d), used to deduce the d=ω(log n) case of Theorem 2."}],"review_version":1}