The longest edge of the random minimal spanning tree
type: Item
instance of: scholarly article
title: The longest edge of the random minimal spanning tree
zbMATH Open document ID: 0884.60042
author: Mathew D. Penrose
published in: The Annals of Applied Probability
publication date: 1998-01-26T00:00:00Z
review text: Let \(\{\eta_n, n\geq 1\}\) be a sequence of i.i.d. random points uniformly distributed in the \(\nu\)-dimensional cube \((-1/2,1/2]^\nu\). Let \(M_n (k)\) denote the longest edge-length of the \(k\)-nearest neighbor graph and \(M_n'\) denote the longest edge-length of the minimal spanning tree constituted by \(\eta_1,\ldots,\eta_n\). Here the length is either the Euclidean distance or is measured as in the toroidal model where \(d(x,y)=\min_{z \in{\mathbb{R}}^\nu}|x-y-z|\). Let \(c_\nu\) = \(\pi^{\nu/2}/\Gamma(\nu/2 + 1)\). It is shown that \(P(M_n'=M_n(1))\to 1\). It is also shown that \[ P(nc_\nu \{M_n (k+1)\}^{\nu}-\log n-k\log(\log n)+\log k!\leq x)\to \exp(-\exp(-x)) \] for the toroidal model for all \(k\geq 0\) and all \(\nu\), and for the Euclidean model for \(k=0\) and \(\nu \leq 2\). Similar results are shown to hold for \(M_{N_n}(k)\) and \(M_{N_n}'\), where \(N_n\) is a Poisson random variable with mean \(n\) that is independent of the \(\eta_i\)'s.
Mathematics Subject Classification ID: 60G70
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1051767
zbMATH Keywords: extreme values
zbMATH Keywords: nearest neighbor graph
zbMATH Keywords: minimal spanning tree
zbMATH Keywords: Chen-Stein method
reviewed by: H. N. Nagaraja
Wikidata QID: Q104631545
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1034625335
OpenAlex ID: W2169293240
DOI: 10.1214/AOAP/1034625335
description: scientific article; zbMATH DE number 1051767