The central limit theorem for Euclidean minimal spanning trees. I

DOI10.1214/aoap/1043862422zbMath0892.60034MaRDI QIDQ1379719

Sungchul Lee

Publication date: 9 August 1998

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1043862422

zbMATH Keywords

continuum percolation; CLT; minimal spanning tree

Mathematics Subject Classification ID

60D05: Geometric probability and stochastic geometry

60F05: Central limit and other weak theorems

05C05: Trees

90C27: Combinatorial optimization

60K35: Interacting random processes; statistical mechanics type models; percolation theory

Related Items

Degree Frequencies in the Minimal Spanning Tree and Dimension Identification, Intrinsic dimension identification via graph-theoretic methods, Asymptotic theory for statistics of the Poisson-Voronoi approximation, Normal approximation on Poisson spaces: Mehler's formula, second order Poincaré inequalities and stabilization, Connected spatial networks over random points and a route-length statistic, Rate of convergence of power-weighted Euclidean minimal spanning trees, Tail bound for the minimal spanning tree of a complete graph., Asymptotics for weighted minimal spanning trees on random points, Central limit theorems for \(k\)-nearest neighbour distances, On the multivariate runs test, Gaussian tail for empirical distributions of MST on random graphs, A central limit theorem with applications to percolation, epidemics and Boolean models., Limit theory for random sequential packing and deposition, Navigation on a Poisson point process, The radial spanning tree of a Poisson point process, Extremes on trees, Multivariate spatial central limit theorems with applications to percolation and spatial graphs, The invariance principle for the total length of the nearest-neighbor graph, Monte Carlo methods for sensitivity analysis of Poisson-driven stochastic systems, and applications, A functional central limit theorem for spatial birth and death processes

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• The random minimal spanning tree in high dimensions
• Graph-theoretic measures of multivariate association and prediction
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests
• Asymptotics for Euclidean minimal spanning trees on random points
• Algorithms for updating minimal spanning trees
• Limit theorems and rates of convergence for Euclidean functionals
• The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees
• The central limit theorem for weighted minimal spanning trees on random points
• A sharp deviation inequality for the stochastic traveling salesman problem
• On the worst case of a minimal spanning tree algorithm for euclidean space
• Simultaneous uniqueness of infinite clusters in stationary random labeled graphs
• Dependent central limit theorems and invariance principles
• On the number of leaves of a euclidean minimal spanning tree
• Generalization of the Gap Test for the Detection of Multivariate Outliers
• Storage Reduction Through Minimal Spanning Trees and Spanning Forests
• Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces