Growth rates of Euclidean minimal spanning trees with power weighted edges
type: Item
instance of: scholarly article
title: Growth rates of Euclidean minimal spanning trees with power weighted edges
zbMATH Open document ID: 0655.60023
author: J. Michael Steele
published in: The Annals of Probability
publication date: 1988-01-01T00:00:00Z
review text: For \(x_ i\in {\mathbb{R}}^ d\), \(1\leq i\leq n\), the family \({\mathcal G}\) of all connected graphs with vertex-set \(V=\{x_ 1,x_ 2,...,x_ n\}\) and edge-set \(E=\{(x_ i,x_ j):1\leq i<j\leq n\}\) is considered. The length of an edge \(e=(x_ i,x_ j)\in E\) is denoted by \(| e|\), where \(| e| =| x_ i-x_ j|\) equals the Euclidean distance from \(x_ i\) to \(x_ j\). Let \(\Psi\) : [0,\(\infty)\to [0,\infty)\) and \[ M(x_ 1,...,x_ n)=\min_{T\in {\mathcal G}} \sum_{e\in T}\Psi (| e|). \] The main result of this paper is the following limit theorem: Suppose that \(X_ i\), \(1\leq i<\infty\), are independent random variables with distribution \(\mu\) having compact support in \({\mathbb{R}}^ d\), \(d\geq 2\). If the monotone function \(\Psi\) satisfies \(\Psi (x)\sim x^{\alpha}\) as \(x\to 0\) for some \(0<\alpha <d\), then with probability 1 \[ \lim_{n\to \infty}n^{-(d-\alpha)/d} M(X_ 1,...,X_ n)=c(\alpha,d)\int_{{\mathbb{R}}^ d}f(x)^{(d-\alpha)/d} dx. \] Here f denotes the density of the absolutely continuous part of \(\mu\) and c(\(\alpha\),d) denotes a strictly positive constant which depends only on the power \(\alpha\) and the dimension d.
Mathematics Subject Classification ID: 60F15
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4069925
zbMATH Keywords: minimal spanning trees
zbMATH Keywords: connected graphs
reviewed by: Ljuben Mutafchiev
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aop/1176991596
OpenAlex ID: W2029565994
Wikidata QID: Q56454188
DOI: 10.1214/AOP/1176991596
description: scientific article; zbMATH DE number 4069925