The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

Svante Janson

Type: Article

Publication Date: 1995-12-01

Citations: 77

DOI: https://doi.org/10.1002/rsa.3240070406

Abstract

Abstract The minimal weight of a spanning tree in a complete graph K n with independent, uniformly distributed random weights on the edges is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph.

Locations

CiteSeer X (The Pennsylvania State University) - View - PDF
Random Structures and Algorithms - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Addendum to “The Minimal Spanning Tree in a Complete Graph and a Functional Limit Theorem for Trees in a Random Graph”	2006	Svante Janson Johan Wästlund
+	Addendum to : "The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph" [Random Structures Algorithms 7 (1995), no. 4, 337--355; MR1369071] by Janson.	2006	Svante Janson Johan Wästlund
+	Random minimum spanning tree and dense graph limits	2023	Jan Hladký G.B. Viswanathan
+ PDF Chat	A random tree model associated with random graphs	1990	David Aldous
+	A functional limit theorem for random graphs with applications to subgraph count statistics	1990	Svante Janson
+	Limit distributions of the number of trees of a given size in a random forest	1996	Yu. L. Pavlov
+ PDF Chat	Properties and limit of random inhomogeneous minimum spanning trees	2021	Othmane Safsafi
+	Random subtrees of complete graphs	2013	Alex Chin Gary Gordon Kellie J. MacPhee C.H. Vincent
+	The scaling limit of the minimum spanning tree of the complete graph	2017	Louigi Addario‐Berry Nicolas Broutin Christina Goldschmidt Grégory Miermont
+	The expected value of random minimal length spanning tree of a complete graph	2005	David Gamarnik
+ PDF Chat	Minimal Spanning Trees for Graphs with Random Edge Lengths	2002	J. Michael Steele
+ PDF Chat	On the probability that a random subtree is spanning	2021	Stephan Wagner
+	The maximum tree of a random forest in the configuration graph	2021	Yu. L. Pavlov
+ PDF Chat	On the Random Minimum Spanning Subgraph Problem for Hypergraphs	2024	Nikita Zvonkov
+ PDF Chat	On the total length of the random minimal directed spanning tree	2006	Mathew D. Penrose Andrew R. Wade
+ PDF Chat	On the total length of the random minimal directed spanning tree	2006	Mathew D. Penrose Andrew R. Wade
+	Limit distributions of the maximum size of a tree in a random recursive forest	2002	Yu. L. Pavlov E.A. Loseva
+	The limit distributions of the maximum size of a tree in a random forest	1995	Yu. L. Pavlov
+ PDF Chat	Random minimal directed spanning trees and Dickman-type distributions	2004	Mathew D. Penrose Andrew R. Wade
+ PDF Chat	Random minimal directed spanning trees and Dickman-type distributions	2004	Mathew D. Penrose Andrew R. Wade

Works That Cite This (70)

Action	Title	Year	Authors
+ PDF Chat	The order of the giant component of random hypergraphs	2009	Michael Behrisch Amin Coja‐Oghlan Mihyun Kang
+ PDF Chat	Cross-multiplicative coalescent processes and applications	2020	Yevgeniy Kovchegov Peter T. Otto Anatoly Yambartsev
+	Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes	2024	Shankar Bhamidi Sanchayan Sen
+	Coalescent Random Forests	1999	Jim Pitman
+ PDF Chat	Noise sensitivity of the minimum spanning tree of the complete graph	2024	Omer Israeli Yuval Peled
+ PDF Chat	Minimal Spanning Trees for Graphs with Random Edge Lengths	2002	J. Michael Steele
+	Polynomial representation for the expected length of minimal spanning trees	2015	Jared Nishikawa Peter T. Otto Colin Starr
+	Geometry of the minimal spanning tree of a random $3$-regular graph	2018	Louigi Addario‐Berry Sanchayan Sen
+	On the number of isolated vertices in a growing random graph	2013	Anatolii A. Puhalskii
+ PDF Chat	The central limit theorem for weighted minimal spanning trees on random points	1996	Harry Kesten Sung Chul Lee

Works Cited by This (8)

Action	Title	Year	Authors
+	Multicyclic components in a random graph process	1993	Svante Janson
+	On tree census and the giant component in sparse random graphs	1990	Boris Pittel
+ PDF Chat	Beweis eines Ausdruckes, von welchem die Binomial-Formel ein einzelner Fall ist.	1826	N. H. Abel
+	On the value of a random minimum spanning tree problem	1985	Alan Frieze
+ PDF Chat	Poisson convergence and random graphs	1982	A. D. Barbour
+	The Expected Number of Components Under a Random Mapping Function	1954	Martin D. Kruskal
+ PDF Chat	Convergence of Probability Measures	1999	Patrick Billingsley
+	Convergence of Probability Measures	1969	J. F. C. Kingmán P. Billingsley