The longest edge of the random minimal spanning tree
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.
scientific article; zbMATH DE number 1051767