The longest edge of the random minimal spanning tree (Q1364391)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The longest edge of the random minimal spanning tree
scientific article

    Statements

    The longest edge of the random minimal spanning tree (English)
    0 references
    0 references
    26 January 1998
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    extreme values
    0 references
    nearest neighbor graph
    0 references
    minimal spanning tree
    0 references
    Chen-Stein method
    0 references
    0 references
    0 references