Pith. sign in

REVIEW 1 major objections 4 minor 59 references

Local limit of Prim's algorithm

T0 review · 1 major / 4 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 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).

desk verdict Genuinely new dynamic local limit for Prim's algorithm, but the proof has a fixable constant mismatch in Proposition 3.1; worth refereeing. read the letter →

arxiv 2507.04867 v1 pith:3JWBGMPT submitted 2025-07-07 math.PR

Benoît Corsini , Rowel Gündlach , Remco van der Hofstad This is my paper · ORCID
classification math.PR MSC 60K3505C8060B1060F17
keywords localweakconvergencePrim'salgorithmminimumspanningtreeinvasionpercolationclusterexpandeddynamicsurvivalprobabilityrandomgraphs
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

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.

What carries the argument

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.

What would settle it

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)).

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

1 major / 4 minor

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.

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 (1)
  1. [Section 3.1, Proposition 3.1] 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.
minor comments (4)
  1. [Section 3.1] 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.
  2. [Section 3.3] 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.
  3. [Corollary 3.3] There is a typo in the title: 'Muti-dimensional convergence' should read 'Multi-dimensional convergence'.
  4. [Section 1.4] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the limiting object is defined from the infinite limit graph, and the proof couples finite Prim runs to it via independent MST and percolation-giant ingredients.

full rationale

The main result, Theorem 1.1, asserts that local limits satisfy (P_{k_n(t)}(G_n))_{t\in[0,1]} \to (F_G^+(\theta^{-1}(t)))_{t\in[0,1]}. The objects on the right are defined solely from the infinite rooted weighted limit graph G: F_G^+(p) is the union of the invasion percolation cluster P_\infty(G) with the edges of the minimum spanning forest F_G of weight at most p (Section 2.2), and \theta(p) is the annealed survival probability from (1). Neither is fitted to the finite graphs G_n, and the proof reduces the convergence to external results: the Aldous\u2013Steele MST local limit (Theorem 2.4), the almost-local giant theorems quoted as Propositions 2.5 and 2.6 from [36], and the generic process-topology framework of Section 2.6. The self-citations to [35], [36], and [47] are load-bearing but independent: they concern percolation giants and dynamic local convergence, not the Prim-limit being proved, and their assumptions do not include the target result. The paper even flags Assumptions 1 and 2 as conjecturally removable open problems, which further supports the claim that the theorem is not forced by definition. The only flagged issue is the factor-two mismatch in the proof of Proposition 3.1: the event E_n imposes weight separation 1/(2k_n) while coupling (5) only guarantees weight closeness 1/k_n, so the assertion that edge order is preserved on the ball is not established as written. That is a potential correctness gap in the proof, not circularity, since repairing it would not make the conclusion equivalent to an input.

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

No free parameters are fitted to data. The theorem is conditional on three stated assumptions and on a coupling condition embedded in the definition of linearly growing sequences. The proof also imports standard results from local convergence, Aldous-Steele's MST limit, van der Hofstad's giant-component theorems, and the dynamic local convergence framework. No new physical or unexplained entities are introduced; the expanded invasion percolation cluster is a directly defined mathematical object.

assumptions (8)
  • standard math Local convergence theory of Benjamini-Schramm and Aldous-Steele (Section 2.4)
    Provides the definition of local weak convergence in probability and its Polish space structure, used throughout.
  • standard math MST local limit theorem of Aldous-Steele ([6, Theorem 5.4], quoted as Theorem 2.4)
    Gives the t=1 endpoint of the result: the local limit of the full MST is the MST forest of the infinite limit.
  • standard math Giant component almost local results of van der Hofstad ([36, Theorems 2.28 and 2.32], quoted as Propositions 2.5 and 2.6)
    Relates the largest component size in finite graphs to the annealed percolation probability θ(p) under Assumption 3.
  • standard math Dynamic local convergence framework from Milewska-van der Hofstad-Zwart ([47], Section 2.6)
    Supplies the process topology and the three conditions (6)-(8) used to define and prove local process convergence.
  • ad hoc to paper Assumption 1 (local percolation of a giant)
    Ensures that when θ(p)>0, Prim's algorithm reaches an infinite component at level p in finite time (via Proposition 2.1). The authors conjecture it may be removable.
  • ad hoc to paper Assumption 2 (smoothness of the percolation function)
    Continuity and strict monotonicity of θ on (pc,1] are needed to make θ^{-1} continuous and strictly increasing, a key step in the proof.
  • ad hoc to paper Assumption 3 (percolation giant is almost local)
    Second-order control on large percolation components in finite graphs; fails for union graphs, and its failure changes the limiting object.
  • domain assumption Existence of a coupling satisfying (5) in the definition of linearly growing sequences
    Assumes the finite graphs and their MSTs can be coupled with the limit graph and its MST forest so that they match on a slowly growing radius with probability 1. This is standard for slowly growing radii but is a nontrivial construction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Local limit of Prim's algorithm." pith.science (2026). https://pith.science/paper/3JWBGMPT

@misc{pith2026250704867,
  author       = {Pith},
  title        = {Pith review of: Local limit of Prim's algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3JWBGMPT}},
  note         = {Machine review of arXiv:2507.04867}
}
abstract

We study the local evolution of Prim's algorithm on large finite weighted graphs. When performed for $n$ steps, where $n$ is the size of the graph, Prim's algorithm will construct the minimal spanning tree (MST). We assume that our graphs converge locally in probability to some limiting rooted graph. In that case, Aldous and Steele already proved that the local limit of the MST converges to a limiting object, which can be thought of as the MST on the limiting infinite rooted graph. Our aim is to investigate {\em how} the local limit of the MST is reached \textit{dynamically}. For this, we take $tn+o(n)$ steps of Prim, for $t\in[0,1]$, and, under some reasonable assumptions, show how the local structure interpolates between performing Prim's algorithm on the local limit when $t=0$, to the full local limit of the MST for $t=1$. Our proof relies on the use of the recently developed theory of {\em dynamic local convergence}. We further present several examples for which our assumptions, and thus our results, apply.

Figures

Figures reproduced from arXiv: 2507.04867 by the authors.

Figure 1
Figure 1. Simulation of Prim’s algorithm on a large grid, starting from the root (in turquoise, in the middle). Vertices and edges are coloured based on the step at which Prim’s algorithm adds them to the current tree (from green to yellow, and finally red) and the three images correspond to running Prim’s algorithm for n/3, 2n/3, and n steps [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Simulation of Prim’s algorithm on a large triangular lattice, start￾ing from the root (in turquoise, in the middle). Vertices and edges are coloured based on the step at which Prim’s algorithm adds them to the current tree (from green to yellow, and finally red) and the three images correspond to running Prim’s algorithm for n/3, 2n/3, and n steps [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Simulation of Prim’s algorithm on a large 3-regular graph, starting from the root (in turquoise, in the middle). Vertices and edges are coloured based on the step at which Prim’s algorithm adds them to the current tree (from green to yellow, and finally red) and the three images correspond to running Prim’s algorithm for n/3, 2n/3, and n steps. to be the time that the mth vertex in Br(Gn) is added. Additionally, for… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Simulation of Prim’s algorithm on a 2000 × 2000 grid, starting from the root (in turquoise, in the middle). Each pixel corresponds to a single vertex and vertices and edges are coloured based on the step at which Prim’s algorithm adds them to the current tree (from gre…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 55 canonical work pages

  1. [1]

    Addario-Berry

    L. Addario-Berry. The local weak limit of the minimum spanning tree of the complete graph. Preprint available at arXiv:1301.1667v2 [math.PR], 2013

    arXiv 2013

  2. [2]

    Addario-Berry, N

    L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont. The scaling limit of the minimum spanning tree of the complete graph. The Annals of Probability, 45(5):3075–3144, 2017

    work page 2017

  3. [3]

    Addario-Berry and S

    L. Addario-Berry and S. Sen. Geometry of the minimal spanning tree of a random 3-regular graph. Probability Theory and Related Fields, 180(3-4):553–620, 2021

    work page 2021

  4. [4]

    Albenque, L

    M. Albenque, L. M´ enard, and G. Schaeffer. Local convergence of large random triangulations coupled with an Ising model. Transactions of the American Mathematical Society, 374:175–217, 2021

    work page 2021

  5. [5]

    Aldous and J

    D. Aldous and J. M. Steele. Asymptotics for Euclidean minimal spanning trees on random points. Proba- bility Theory and Related Fields, 92(2):247–258, jun 1992

    work page 1992

  6. [6]

    Aldous and J

    D. Aldous and J. M. Steele. The objective method: Probabilistic combinatorial optimization and local weak convergence. Probability on Discrete Structures, 110:1–72, 2004

    work page 2004

  7. [7]

    K. S. Alexander. Percolation and minimal spanning forests in infinite graphs. The Annals of Probability, 23(1):347–370, jan 1995

    work page 1995

  8. [8]

    Anandkumar and R

    A. Anandkumar and R. Valluvan. Latent graphical model selection: Efficient methods for locally tree- like graphs. In Advances in Neural Information Processing Systems, volume 25, pages 1052–1060. Curran Associates, Inc., 2012

    work page 2012

Show all 59 references
  1. [9]

    G. B. Arous, S. Molchanov, and A. F. Ram ´ ırez. Transition from the annealed to the quenched asymptotics for a random walk on random obstacles. The Annals of Probability, 33(6):2149–2187, 2005

    2005

  2. [10]

    Banerjee, S

    S. Banerjee, S. Bhamidi, J. Shen, and S. P. Young. Local weak convergence and its applications. Preprint available at arXiv:2403.01544 [math.PR], 2024

    2024 arXiv

  3. [11]

    Benjamini, A

    I. Benjamini, A. Nachmias, and Y. Peres. Is the critical percolation probability local? Probability Theory and Related Fields, 149(1):261–269, 2011

    2011

  4. [12]

    Benjamini and O

    I. Benjamini and O. Schramm. Recurrence of distributional limits of finite planar graphs. Electronic Journal of Probability, 6:1–13, 2001

    2001

  5. [13]

    Berger, C

    N. Berger, C. Borgs, J. T. Chayes, and A. Saberi. Asymptotic behavior and distributional limits of preferential attachment graphs. The Annals of Probability, 42(1):1–40, 2014

    2014

  6. [14]

    Bhamidi, S

    S. Bhamidi, S. N. Evans, and A. Sen. Spectra of large random trees. Journal of Theoretical Probability, 25(3):613–654, 2012

    2012

  7. [15]

    Bhamidi and S

    S. Bhamidi and S. Sen. Geometry of the minimal spanning tree in the heavy-tailed regime: New universality classes. Probability Theory and Related Fields, 188(3–4):729–804, 2024

    2024

  8. [16]

    Billingsley

    P. Billingsley. Convergence of Probability Measures. Wiley Series in Probability and Statistics. John Wiley & Sons, Inc., second edition, 1999

    1999

  9. [17]

    Bollob´ as, S

    B. Bollob´ as, S. Janson, and O. Riordan. The phase transition in inhomogeneous random graphs. Random Structures and Algorithms, 31(1):3–122, 2007

    2007

  10. [18]

    Bordenave, M

    C. Bordenave, M. Lelarge, and J. Salez. The rank of diluted random graphs. The Annals of Probability, 39(3):1097–1121, 2011

    2011

  11. [19]

    L. A. Braunstein, S. V. Buldyrev, R. Cohen, S. Havlin, and H. E. Stanley. Optimal paths in disordered complex networks. Physical Review Letters, 91(16):1–4, 2003

    2003

  12. [20]

    Coja-Oghlan, C

    A. Coja-Oghlan, C. Efthymiou, and N. Jaafari. Local convergence of random graph colorings. Combina- torica, 38(2):341–380, 2018

    2018

  13. [21]

    Contreras, S

    D. Contreras, S. Martineau, and V. Tassion. Locality of percolation for graphs with polynomial growth. Electronic Communications in Probability, 28(1):1–9, 2023

    2023

  14. [22]

    Dembo and A

    A. Dembo and A. Montanari. Ising models on locally tree-like graphs. The Annals of Applied Probability, 20(2):565–592, 2010

    2010

  15. [23]

    Dembo, A

    A. Dembo, A. Montanari, and N. Sun. Factor models on locally tree-like graphs. The Annals of Probability, 41(6):4162–4213, 2013. 28 BENO ˆIT CORSINI, ROWEL G¨UNDLACH, AND REMCO V AN DER HOFSTAD

    2013

  16. [24]

    Dobrin and P

    R. Dobrin and P. M. Duxbury. Minimum spanning trees on random networks. Physical Review Letters, 86(22):5076–5079, 2001

    2001

  17. [25]

    Dommers, C

    S. Dommers, C. Giardin` a, and R. van der Hofstad. Ising critical exponents on random trees and graphs. Communications in Mathematical Physics, 328(1):355–395, 2014

    2014

  18. [26]

    Dort and E

    L. Dort and E. Jacob. Local weak limit of dynamical inhomogeneous random graphs. Preprint available at arXiv:2303.17437v1 [math.PR], 2023

    2023 arXiv

  19. [27]

    Easo and T

    P. Easo and T. Hutchcroft. The critical percolation probability is local. Preprint available at arXiv:2310.10983 [math.PR], 2023

    2023 arXiv

  20. [28]

    E. O. Endo and D. Valesin. Local limits of spatial Gibbs random graphs. Alea (Rio de Janeiro), 17(1):51– 63, 2020

    2020

  21. [29]

    A. M. Frieze. On the value of a random minimum spanning tree problem. Discrete Applied Mathematics, 10(1):47–56, jan 1985

    1985

  22. [30]

    Garavaglia, R

    A. Garavaglia, R. S. Hazra, R. van der Hofstad, and R. Ray. Universality of the local limit of preferential attachment models. Preprint available at arXiv:2212.05551v2 [math.PR], 2023

    2023

  23. [31]

    Garavaglia, R

    A. Garavaglia, R. van der Hofstad, and N. Litvak. Local weak convergence for PageRank. The Annals of Applied Probability, 30(1):40–79, 2020

    2020

  24. [32]

    Grimmett

    G. Grimmett. Percolation. Springer, New-York, second edition, 1999

    1999

  25. [33]

    R. S. Hazra, R. van der Hofstad, and R. Ray. Percolation on preferential attachment models. Preprint available at arXiv:2312.14085, 2023

    2023 arXiv

  26. [34]

    Heydenreich and R

    M. Heydenreich and R. van der Hofstad. Progress in high-dimensional percolation and random graphs. CRM Short Courses Series. Springer, Cham, (2017)

    2017

  27. [35]

    van der Hofstad

    R. van der Hofstad. The giant in random graphs is almost local. Preprint available at arXiv:2103.11733v2 [math.PR], 2021

    2021

  28. [36]

    van der Hofstad

    R. van der Hofstad. Random Graphs and Complex Networks, Volume 2. Cambridge University Press, 2024

    2024

  29. [37]

    van der Hofstad and M

    R. van der Hofstad and M. Pandey. Are giants in random digraphs ‘almost’ local? Preprint available at arXiv:2403.02137 [math.PR], 2024

    2024 arXiv

  30. [38]

    van der Hofstad and F

    R. van der Hofstad and F. Redig. Maximal clusters in non-critical percolation and related models. J. Statist. Phys., 122(4):671–703, 2006

    2006

  31. [39]

    van der Hofstad, P

    R. van der Hofstad, P. van der Hoorn, and N. Maitra. Scaling of the clustering function in spatial inho- mogeneous random graphs. Journal of Statistical Physics, 190(110):1–43, 2023

    2023

  32. [40]

    Huo and R

    R. Huo and R. Durrett. Latent voter model on locally tree-like random graphs. Stochastic Processes and their Applications, 128(5):1590–1614, 2018

    2018

  33. [41]

    A. Khan, A. A. Aesha, and J. Sarker. A new algorithmic approach to finding minimum spanning tree. 4th International Conference on Electrical Engineering and Information and Communication Technology, iCEEiCT 2018, pages 590–594, 2019

    2018

  34. [42]

    J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem.Proceedings of the American Mathematical Society, 7:48–50, 1956

    1956

  35. [43]

    Kurauskas

    V. Kurauskas. On local weak limit and subgraph counts for sparse random graphs. Journal of Applied Probability, 59(3):755–776, 2022

    2022

  36. [44]

    Lacker, K

    D. Lacker, K. Ramanan, and R. Wu. Local weak convergence for sparse networks of interacting processes. The Annals of Applied Probability, 33(2):843 – 888, 2023

    2023

  37. [45]

    R. Lyons. Asymptotic enumeration of spanning trees. Combinatorics Probability and Computing , 14(4):491–522, 2005

    2005

  38. [46]

    Michelen, R

    M. Michelen, R. Pemantle, and J. Rosenberg. Quenched survival of Bernoulli percolation on Gal- ton–Watson trees. Journal of Statistical Physics, 181(4):1323–1364, 2020

    2020

  39. [47]

    Milewska, R

    M. Milewska, R. van der Hofstad, and B. Zwart. Dynamic random intersection graph: Dynamic local convergence and giant structure. Random Structures & Algorithms, 66(1):e21264, 2025

    2025

  40. [48]

    Milewska, R

    M. Milewska, R. van der Hofstad, and B. Zwart. Sir on locally converging dynamic random graphs. Preprint available at arXiv:2501.09623 [math.PR], 2025

    2025 arXiv

  41. [49]

    Montanari, E

    A. Montanari, E. Mossel, and A. Sly. The weak limit of Ising models on locally tree-like graphs. Probability Theory and Related Fields, 152:31–51, 2012

    2012

  42. [50]

    Mountford, D

    T. Mountford, D. Valesin, and Q. Yao. Metastable densities for the contact process on power law random graphs. Electronic Journal of Probability, 18(11201150), 2013

    2013

  43. [51]

    Nachmias and P

    A. Nachmias and P. Tang. The wired minimal spanning forest on the poisson-weighted infinite tree. The Annals of Applied Probability, 34(2):2415–2446, 2024. LOCAL LIMIT OF PRIM’S ALGORITHM 29

    2024

  44. [52]

    Neˇ setˇ ril, E

    J. Neˇ setˇ ril, E. Milkov´ a, and H. Neˇ setˇ rilov´ a. Otakar Bor ˚ uvka on minimum spanning tree problem: Trans- lation of both the 1926 papers, comments, history. Discrete Mathematics, 233(1-3):3–36, 2001

    1926

  45. [53]

    Pettie and V

    S. Pettie and V. Ramachandran. An optimal minimum spanning tree algorithm. Journal of the ACM, 49(1):16–34, 2002

    2002

  46. [54]

    R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6):1389–1401, 1957

    1957

  47. [55]

    J. Salez. Weighted enumeration of spanning subgraphs in locally tree-like graphs. Random Structures and Algorithms, 43(3):377–397, 2013

    2013

  48. [56]

    J. M. Steele. Growth rates of Euclidean minimal spanning trees with power weighted edges. The Annals of Probability, 16(4):347–370, oct 1988

    1988

  49. [57]

    J. M. Steele. Minimal spanning trees for graphs with random edge lengths. In Mathematics and Computer Science II, pages 223–245. Birkh¨ auser Basel, Basel, 2002

    2002

  50. [58]

    B. Stufler. Local convergence of random planar graphs. Journal of the European Mathematical Society, 25(1):1–73, 2021

    2021

  51. [59]

    Yu and Y

    Q. Yu and Y. Polyanskiy. Ising model on locally tree-like graphs: Uniqueness of solutions to cavity equations. IEEE Transactions on Information Theory, 70(3):1913–1938, 2023

    1913

Pith tools

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