Minimum spanning trees of random geometric graphs with location dependent weights (Q1983618)

This paper analyzes the weight of a minimum spanning tree (MST) of an edge-weighted random geometric graph (RGG) above the connectivity regime. The author considers the following model of non-uniform RGG on the unit square \(S=[0,1]^2\). An RGG \(G_n\) has vertex set \(\{X_1,\ldots, X_n\}\), where the vertices \(X_i\) are i.i.d.\ points chosen at random from \(S\) with probability density \(f\). Here, \(f\) is assumed to be bounded on \(S\); that is, \(0 < \epsilon_1\le f(X)\le \epsilon_2\) for all \(X\in S\). Any two vertices \(X_i\), \(X_j\) of \(G_n\) are joined by an edge iff \(d(X_i,X_j)<r\), where \(d(\cdot,\cdot)\) denotes the Euclidean distance and \(r\) is a parameter of the model. As it is customary in the field, \(r\) is a function of \(n\) and all statements are asymptotic as \(n\to\infty\). The article analyzes an edge-weighted version of this model, in which each edge \(X_iX_j\) of \(G_n\) is assigned a weight \[ w(X_i,X_j) = d^\alpha(X_i,X_j) \xi(X_i,X_j), \] where \(\alpha>0\) is constant and \(\xi\) is a function \(\xi: S\times S \to (0,\infty)\) satisfying \(\xi(X,Y)=\xi(Y,X)\) and \(0<\xi_1\le\xi(X,Y)\le\xi_2\) for all \(X,Y\in S\). In simpler words, the weight of an edge mainly depends on the distance between its endpoints times, an additional but bounded factor. The weight of a tree \(T\) in \(G_n\) is the sum of the weights of the edges of \(T\). With some abuse of notation, let \(MST_n\) denote the sum over all connected components \(C\) of \(G_n\) of the minimum weight of a spanning tree of \(C\). Note that if \(G_n\) is connected, then \(MST_n\) is simply the minimum weight of a spanning tree of \(G_n\). The goal of the paper is to asymptotically characterize \(MST_n\) for \(r\ge \sqrt{\frac{M\log n}{n}}\), where \(M>0\) is a sufficiently large constant. Note that in this regime the RGG \(G_n\) is known to be asymptotically almost surely (a.a.s.) connected. The author proves the following claims for such range of \(r\): \par i) \(\mathrm{Var} ( MST_n/n^{1-\alpha/2} ) = O(r^{2+2\alpha} n^\alpha)\), \par ii) \(MST_n = \Theta(n^{1-\alpha/2})\) a.a.s. and \par iii) \(\mathbb E ( MST_n) = \Theta(n^{1-\alpha/2})\). In particular, if \(r = o(n^{-\alpha/(2+2\alpha)})\) then we get that \(\frac{MST_n - \mathbb E ( MST_n)}{n^{1-\alpha/2}} \to 0\) in \(L^2\). The results include explicit (but not optimal) error bounds for the asymptotic statements above. The variance bound is obtained via the martingale-difference method together with one-vertex-difference estimates that measure the change in MST lengths after adding or removing a single vertex. To prove the deviation estimates, the author uses for convenience a Poissonized version of the model, in which the vertices of \(G_n\) are obtained from an inhomogeneous Poisson point process on \(S\), and then transfers the results back to the original model. The Poissonized model facilitates calculations, since the number of points in two disjoint Borel subsets of \(S\) are independent random variables.