{"id":"f9c4ca25-00bb-4b75-b068-40e5c21a0fcf","arxiv_id":"2507.04867","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Running Prim's algorithm for tn+o(n) steps on a locally convergent weighted graph sequence converges in local process convergence to the expanded invasion percolation cluster of the limit graph.","lead":"This paper proves a limit theorem for what Prim's algorithm discovers locally on large random graphs when it is stopped after a fraction of the total steps. The result gives a single dynamic description that interpolates between invasion percolation and the minimum spanning tree.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 3.1's coupling bound is inconsistent as written: the proof assumes edge-weight separation 1/(2k_n) while the coupling in (5) only gives closeness 1/k_n, so edge-order preservation on the ball is not established.","rationale":"The reader's verdict is CONDITIONAL and high confidence, and the reader identified the same Proposition 3.1 gap in the rationale, although the reader's stated weakest assumption is Assumption 3. I agree that the proof as written has a real technical flaw: the numerical inconsistency between 1/(2k_n) and 1/k_n means the central coupling step is not justified. This is load-bearing because Proposition 3.1 is the key bridge from the finite graph to the infinite expanded invasion percolation cluster. However, the flaw appears repairable: for a fixed finite ball the minimum weight gap is positive almost surely, so replacing 1/(2k_n) by a threshold larger than 2/k_n gives an event whose probability still tends to 1, and the rest of the proof structure goes through unchanged. I do not see a reason to reject the theorem's mathematical content; Assumption 3 limits the scope (e.g., union graphs), but that is an explicitly stated condition rather than an internal contradiction. The paper is careful, well-written, and the examples in Section 4.2 honestly demarcate the boundary of the theorem. Thus the reader's CONDITIONAL verdict should stand, and no verdict change is needed.","tokens_in":26739,"tokens_out":22985,"duration_ms":255346,"concrete_test":"Re-derive Proposition 3.1 with the coupling in (5) taken literally: replace the weight-separation threshold 1/(2k_n) by 3/k_n (or more generally by > 2/k_n), and verify that (i) the event bound P(inf gap ≤ 3/k_n) ≤ ε/3 still holds for large n because the ball is finite and its minimum edge-weight gap is a.s. positive, and (ii) with this corrected threshold, the proof's assertions about order preservation, |C_{v(p)}^{G_n}(p)| ≥ k_0, and the isomorphism T ≡_r F_G^+(p) all go through. If the corrected bound works, the proof gap is repairable and the theorem stands; if not, Proposition 3.1 and hence Theorem 1.1 fail as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on Proposition 3.1, which couples Prim's algorithm on G_n with the limit G. In that proof, an event E_n is defined that includes the condition that the weights of edges in B_{k_{n2}}(G) are mutually separated by more than 1/(2k_n). The proof then asserts that on E_n^c the ordering of these edges is the same in G_n and G, because 'the edge weights of Gn and G are at a distance at most 1/(2k_n)'. But the coupling invoked earlier, via (5), is G_n ≡_{k_n} G and T_{G_n} ≡_{k_n} F_G with k_n = k_n(0), and the local topology ε-isomorphism in (4) gives weight differences at most 1/k_n, not 1/(2k_n). With weight error up to 1/k_n, two edges in G whose weights differ by, say, 1.5/k_n can be reordered in G_n, breaking the exact order preservation that Proposition 3.1 uses to conclude that Prim explores the same vertices in the same order until reaching the giant component. This is a concrete correctness gap in the proof of the main engine; the theorem is not established as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the local evolution of Prim's algorithm on large finite weighted graphs that converge locally in probability to a rooted weighted limit graph. The main theorem (Theorem 1.1) asserts that after a linearly growing number of steps, the rooted subtree produced by Prim's algorithm converges in the local process topology to an explicitly defined limiting process, the expanded invasion percolation cluster F_G^+(θ^{-1}(t)), which interpolates between the invasion percolation cluster at t=0 and the minimum spanning forest at t=1. The proof proceeds via a Skorohod coupling of the finite graphs and their MSTs with the limit graph and its minimum spanning forest, one-dimensional and then finite-dimensional convergence, and a tightness argument under the local process topology. The paper also states a corollary on addition and completion times, discusses grids, Erdős-Rényi graphs, configuration models, and preferential attachment graphs as applications, and analyzes union graphs as counterexamples to the assumptions.","tokens_in":26939,"tokens_out":4883,"duration_ms":60081,"significance":"If the result is correct, it gives the first dynamical local limit for Prim's algorithm, showing that the MST local limit is reached through a two-phase mechanism: a sublinear exploration phase producing the invasion percolation cluster, followed by a linear-time phase in which heavier MST edges are added in the local neighbourhood. This is a natural and interesting contribution to the recently developed theory of dynamic local convergence. The paper is honest about the scope of its assumptions, provides explicit examples where each assumption holds and where it fails, and the limiting object F_G^+(θ^{-1}(t)) is defined independently of the finite graph sequence, so the statement is falsifiable. The proof architecture is coherent and the use of external benchmark results is clearly indicated.","major_comments":[{"comment":"The proof of Proposition 3.1 contains a constant mismatch that is load-bearing for the coupling argument. The event E_n is defined to include the condition that the weights of edges in B_{k_{n2}}(G) are mutually separated and separated from p by more than 1/(2k_n). Later the proof says that on E_n^c, 'the edge weights of G_n and G are at a distance at most 1/(2k_n)', and concludes that edge order is preserved. However, the coupling in (5) and in Section 2.4 gives G_n ≡_{k_n(0)} G, which means that weights are within 1/k_n(0), not 1/(2k_n(0)). With error up to 1/k_n, two edges whose weights in G differ by, say, 1.5/k_n can be reordered in G_n, so the exact order preservation used to identify the exploration sequence until the giant component is not established. This affects the central engine of the theorem. The gap is repairable: one may require separation by 1/k_n instead of 1/(2k_n) in the definition of E_n, or alternatively couple with a ball of radius 2k_n so that the weight error is 1/(2k_n); either change preserves the fact that the bad event has probability tending to zero.","section":"Section 3.1, Proposition 3.1"}],"minor_comments":[{"comment":"The notation in the proof of Proposition 3.1 is confusing: the object written as 1/(2kn3) should presumably be 1/(2k_n), and the subscripts n0, n1, n2, n3 are used both as indices of the sequence and as thresholds. Please clarify the definition of the separation event and the threshold used for the coupling error.","section":"Section 3.1"},{"comment":"In the tightness proof, the sentence 'the previous definition of δ0 implies that P(...) ≤ ε/2' appears to use the uniform continuity of θ^{-1} and the local finiteness of G, but the double use of ε/2 for both the finite-dimensional event and the edge-weight separation event should be stated more transparently.","section":"Section 3.3"},{"comment":"There is a typo in the title: 'Muti-dimensional convergence' should read 'Multi-dimensional convergence'.","section":"Corollary 3.3"},{"comment":"In the displayed formula for the limit of C_n(r)/n, the maximum over edges e in E(B_r(F_G)) \\ E(P_∞(G)) should be explicitly defined as an empty maximum when the set is empty; otherwise the formula is ambiguous for small r or in graphs where the invasion percolation cluster already contains the whole ball.","section":"Section 1.4"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely correct and the central result is interesting, but the proof of Proposition 3.1 has a genuine constant mismatch that must be fixed before the main theorem is established. The fix appears local: replace 1/(2k_n) by 1/k_n in the separation event or couple with radius 2k_n. I therefore recommend major revision rather than rejection. The authors should also re-check the analogous factor-of-two statements elsewhere in the proof of Proposition 3.1 and in the surrounding text."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Cole—\n\nShort version: this is a genuine step forward. The paper proves a dynamic local limit for Prim's algorithm on locally convergent weighted graphs, with the interpolation object F_G^+(θ^{-1}(t)) running from the invasion percolation cluster at t=0 to the MST forest at t=1. That interpolation is new; earlier literature only had the endpoints (Aldous–Steele for the MST, invasion percolation as the sublinear limit). The expanded IPC is a natural and useful object, and the proof architecture—Skorohod coupling, one-dimensional convergence, finite-dimensional extension, tightness in J1—is sound.\n\nWhat the paper does well: it states its assumptions honestly, explains why each is needed, and gives counterexamples (union graphs) where the limit statement genuinely changes. Section 4 is a model of how to discuss scope. The simulations are illustrative, not formal, but fine.\n\nThe soft spot is real and matches the stress-test note. In Proposition 3.1, the event E_n separates the edge weights in B_{k_{n2}}(G) by more than 1/(2k_n). The proof then says that because 'the edge weights of Gn and G are at a distance at most 1/(2k_n)', the edge order is preserved. But the coupling (5) gives G_n ≡_{k_n} G, which is a 1/k_n-isomorphism, so the weight error is at most 1/k_n, not 1/(2k_n). Two edges whose weights differ by, say, 1.5/k_n in G can be reversed in G_n. The order preservation on the ball is load-bearing for the rest of Proposition 3.1. This is likely fixable—take the separation threshold to be 2/k_n (or any c/k_n with c>2), or run the coupling at radius 2k_n—but as written the proof has a gap. The reader's conditional verdict is correct.\n\nThe other weaknesses are scope rather than correctness. Assumption 3 is strong and fails for the union graphs the authors themselves construct; they acknowledge this and conjecture Assumption 1 may be removable. Assumption 2 (smoothness of θ) may be redundant, and they say so. Theorem 1.2 on addition/completion times is stated without a proof in the submitted text; that should be supplied.\n\nI'd send this to a serious referee. The main theorem is important and the gap is a constant error, not a conceptual one. If the authors fix the coupling/separation mismatch (and provide the proof of Theorem 1.2), the paper will be a solid contribution to the local convergence literature. I'd cite it for the dynamic limit result.","headline":"Genuinely new dynamic local limit for Prim's algorithm, but the proof has a fixable constant mismatch in Proposition 3.1; worth refereeing.","tokens_in":27525,"tokens_out":4550,"would_cite":true,"duration_ms":45851,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60K35","05C80","60B10","60F17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For locally converging graphs, running Prim's algorithm for tn+o(n) steps has a local process limit: the expanded invasion percolation cluster at level θ^{-1}(t).","keywords":["local weak convergence","Prim's algorithm","minimum spanning tree","invasion percolation cluster","expanded invasion percolation cluster","dynamic local convergence","percolation survival probability","random graphs"],"falsifier":"Take the union graph of Section 4.2, two half-size random d-regular graphs joined by a single edge, and percolate at a level p where both halves have giant components; the expected number of disjoint pairs of large components stays bounded below by a positive constant, so Assumption 3 fails, and the local limit of P_{k_n(t)}(G_n) then depends on the connector edge instead of F_G^+($θ^{{-1}}$(t)).","tokens_in":26460,"feed_emoji":"🌲","tokens_out":8253,"duration_ms":80728,"temperature":0.7,"pith_summary":"This paper proves that the local structure produced by Prim's algorithm on a large finite weighted graph has a limit that depends only on how many steps it has run. If the graphs converge locally in probability to an infinite rooted limit, then running the algorithm for tn+o(n) steps, where t∈[0,1], yields a rooted tree whose local process limit is the expanded invasion percolation cluster of the limit graph at level $θ^{{-1}}$(t). At t=0 this object is the invasion percolation cluster; at t=1 it is the full minimum spanning forest. The result thus describes how the minimum spanning tree is assembled around a root over time, and the paper shows the description applies to grids, Erdős–Rényi graphs, configuration models, and preferential attachment graphs.","feed_headline":"Prim's algorithm has a universal local limit process","feed_subtitle":"The first sub-linear phase builds the invasion percolation cluster; then the minimum spanning forest appears edge by edge.","key_machinery":"The central object is the expanded invasion percolation cluster F_G^+(p), defined as the union of the invasion percolation cluster P_∞(G) and the edges of the minimum spanning forest whose weights are at most p. The proof's engine is a comparison: after K(p)+|C_{(1)}^{G_n}(p)| steps of Prim's algorithm on the finite graph, the discovered tree is locally isomorphic to F_G^+(p), where K(p) is the first time an infinite percolation component is reached and C_{(1)}^{G_n}(p) is the largest percolation component. Assumption 3 makes the size of that largest component close to nθ(p) and ensures it is the only large component in any finite neighbourhood, while the inverse percolation function $θ^{{-1}}$(t) converts the linear step count into the edge-weight level of the limit tree. The three conditions of local process convergence (finite-dimensional distributions, continuity at 1, and absence of high increments) then upgrade the pointwise comparison to a process limit.","core_discovery":"Under Assumptions 1, 2, and 3, the process (P_{k_n(t)}(G_n))_{t∈[0,1]} converges in local process convergence to (F_G^+($θ^{{-1}}$(t)))_{t∈[0,1]}, where θ(p) is the annealed percolation survival probability of the infinite limit and F_G^+(p) is the union of the invasion percolation cluster with all edges of the minimum spanning forest of weight at most p. The time-rescaled tree obtained at parameter t is exactly the tree formed by first exploring the invasion percolation cluster (a sub-linear number of steps) and then adding MST edges of weight below $θ^{{-1}}$(t). Because $θ^{{-1}}$(0)=p_c and $θ^{{-1}}$(1)=1, the process interpolates between the invasion percolation cluster and the full MST forest.","pith_inferences":["Going beyond the paper: the time-rescaling identity P_∞(G) ⊆ F_G^+(p) suggests that for any locally finite limit with a unique infinite percolation component, the same two-phase description should hold for other MST-building greedy algorithms run at a linear speed, with the same θ^{-1}(t) calibration.","Going beyond the paper: the union-graph counterexample suggests a limit theorem for mixtures of local limits, where the limiting process is a mixture of expanded invasion percolation clusters with time accelerated by the inverse of each component's percolation function; this could be tested on the two-component example.","Going beyond the paper: the completion-time formula predicts that edges of the minimum spanning forest with high percolation levels are added at linear times, so a numerical simulation on a large grid should show late edges appearing in every neighbourhood of the root, as the paper's own simulations already suggest."],"forward_implications":["For k=o(n) steps the local limit is the invasion percolation cluster, so any sublinear number of steps cannot reveal the full local neighbourhood of the minimum spanning tree when p_c<1.","Between cn and (c+δ)n steps, Prim's algorithm returns to the root's neighbourhood and adds exactly the minimum spanning forest edges whose weights lie between θ^{-1}(c) and θ^{-1}(c+δ).","The normalised addition time of the m-th vertex in a fixed-radius ball, and the normalised completion time of that ball, converge in distribution to limits computable from θ and the edge weights of the infinite limit.","The local structure around the root no longer changes once Prim's algorithm has run for n-o(n) steps, meaning the last o(n) steps explore only faraway parts of the graph."],"supporting_citations":[{"why":"supplies the local weak convergence definition and, via Theorem 5.4, the local limit of the minimum spanning tree to the minimum spanning forest, anchoring the t=1 endpoint and the coupling.","marker":"[6]"},{"why":"provides Theorems 2.28 and 2.32, quoted as Propositions 2.5 and 2.6, that relate the largest percolation component's size and local structure to θ(p) under Assumption 3.","marker":"[36]"},{"why":"supplies the dynamic local convergence framework and process topology used to state Theorem 1.1.","marker":"[47]"},{"why":"introduces local convergence of finite graphs to an infinite rooted graph, the base notion on which the whole statement is built.","marker":"[12]"},{"why":"establishes the equivalence between the 'giant is almost local' property and the convergence of the largest component's size, used to verify Assumption 3 in examples.","marker":"[35]"},{"why":"defines Prim's algorithm as the recursive nearest-edge process whose partial outputs P_k(G) are the subject of the theorem.","marker":"[54]"}],"fun_headline_variants":["Prim's local limit: invasion cluster then MST edges","How Prim's algorithm builds the MST locally","Prim's dynamic local limit: percolation to MST","The local dynamics of Prim's algorithm"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that at every edge-weight level the finite graphs have essentially one large percolation component, meaning that any two components which are both large are asymptotically disjoint only with negligible density; if that premise fails, as in the union graphs of Section 4.2, the limiting object depends on the connections between large components and the formula F_G^+($θ^{{-1}}$(t)) no longer holds.","fun_headline_variants_meta":{"raw":{"variants":["Prim's local limit: invasion cluster then MST edges","How Prim's algorithm builds the MST locally","Prim's dynamic local limit: percolation to MST","The local dynamics of Prim's algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000144,"raw_usage":{"total_tokens":1161,"prompt_tokens":917,"completion_tokens":244,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":185}},"tokens_in":533,"tokens_out":244,"duration_ms":3045,"temperature":1.0,"reasoning_tokens":185,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:38:11.744218+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the union graph of Section 4.2, two half-size random d-regular graphs joined by a single edge, and percolate at a level p where both halves have giant components; the expected number of disjoint pairs of large components stays bounded below by a positive constant, so Assumption 3 fails, and the local limit of P_{k_n(t)}(G_n) then depends on the connector edge instead of F_G^+($θ^{{-1}}$(t)).","supporting_citations":[{"cited_title":"Aldous and J","cited_arxiv_id":null,"evidence_quote":"supplies the local weak convergence definition and, via Theorem 5.4, the local limit of the minimum spanning tree to the minimum spanning forest, anchoring the t=1 endpoint and the coupling."},{"cited_title":"van der Hofstad","cited_arxiv_id":null,"evidence_quote":"provides Theorems 2.28 and 2.32, quoted as Propositions 2.5 and 2.6, that relate the largest percolation component's size and local structure to θ(p) under Assumption 3."},{"cited_title":"Milewska, R","cited_arxiv_id":null,"evidence_quote":"supplies the dynamic local convergence framework and process topology used to state Theorem 1.1."},{"cited_title":"Benjamini and O","cited_arxiv_id":null,"evidence_quote":"introduces local convergence of finite graphs to an infinite rooted graph, the base notion on which the whole statement is built."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines Prim's algorithm as the recursive nearest-edge process whose partial outputs P_k(G) are the subject of the theorem."}],"review_version":1}