The longest edge of the random minimal spanning tree

DOI10.1214/AOAP/1034625335MaRDI QIDQ1364391zbMATH OpenOpenAlexWikidataFDO

Publication date 26 January 1998

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

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

Chen-Stein method extreme values minimal spanning tree nearest neighbor graph

Trees (05C05) Geometric probability and stochastic geometry (60D05) Extreme value theory; extremal stochastic processes (60G70) Combinatorial optimization (90C27)

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.

Recommendations

Cited in

(79)

This page was built for publication: The longest edge of the random minimal spanning tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1364391)