Random Minimum Spanning Tree and Dense Graph Limits

2023/10/18 by Jan Hladký, Gopal Viswanathan, G.B. Viswanathan +2 · 1 citation
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Complex Network Analysis Techniques #Limits and Structures in Graph Theory

paper · pdf · doi:10.1002/rsa.70053

Abstract

ABSTRACT A theorem of Frieze from 1985 asserts that the total length of the minimum spanning tree of the complete graph whose edges get independent lengths from the distribution converges to Apéry's constant in probability, as . We generalize this result to sequences of graphs that converge to a graphon . Further, we allow the lengths of the edges to be drawn from different distributions (subject to moderate conditions). The limiting total length of the minimum spanning tree is expressed in terms of a certain branching process defined on , which was studied previously by Bollobás, Janson and Riordan in connection with the giant component in inhomogeneous random graphs.

Citations

• On the shortest spanning subtree of a graph and the traveling salesman problem

Cited by

• Probability-graphons: Limits of large dense weighted graphs

Related

• The scaling limit of the minimum spanning tree of the complete graph
• The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights
• On the probability that a random subtree is spanning
• The GHP scaling limit of uniform spanning trees of dense graphs
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes