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, An average case analysis of the minimum spanning tree heuristic for the power assignment problem, Chase–escape in dynamic device-to-device networks, 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, On the law of the iterated logarithm and strong invariance principles in stochastic geometry, Geometry of the minimal spanning tree of a random 3-regular graph, Quantitative two-scale stabilization on the Poisson space, Multiscale functional inequalities in probability: constructive approach, On approximation theorems for the Euler characteristic with applications to the bootstrap, Continuum percolation for Cox point processes, On central limit theorems in stochastic geometry for add-one cost stabilizing functionals, 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