# Euclidean minimum spanning trees with location dependent and power weighted
edges

Ghurumuruhan Ganesan

Institute of Mathematical Sciences, HBNI, Chennai E-Mail<EMAIL_ADDRESS>
###### Abstract

Consider $n$ nodes $\\{X_{i}\\}_{1\leq i\leq n}$ independently distributed in
the unit square $S,$ each according to a distribution $f$ and let $K_{n}$ be
the complete graph formed by joining each pair of nodes by a straight line
segment. For every edge $e$ in $K_{n}$ we associate a weight $w(e)$ that may
depend on the _individual locations_ of the endvertices of $e.$ Denoting
$MST_{n}$ to be the minimum weight of a spanning tree of $K_{n}$ and assuming
an equivalence condition on the weight function $w(.),$ we prove that
$MST_{n}$ appropriately scaled and centred converges to zero a.s. and in mean
as $n\rightarrow\infty.$ We also obtain upper and lower bound deviation
estimates for $MST_{n}.$

Key words: Minimum spanning tree, location dependent edge weights, edge weight
exponent.

AMS 2000 Subject Classification: Primary: 60J10, 60K35; Secondary: 60C05,
62E10, 90B15, 91D30.

##  1 Introduction

The study of the minimum weight spanning trees of a graph is of great
practical importance and many algorithms have been proposed over the years for
various kinds of graphs. For example, the well-known Kruskal’s algorithm
(Cormen et al (2009)) iteratively adds edges to a sequence of increasing
subtree of the original graph until a spanning tree is obtained with the
constraint that no cycle is created in any of the iterations. The spanning
tree with minimum weight so obtained is usually called the _Minimum Spanning
Tree_ (MST).

We are interested in MSTs of Euclidean random graphs whose nodes are randomly
distributed in the unit square and whose edges are assigned weights related to
the Euclidean length. When the weight of an edge equals its Euclidean length
raised to a positive power, we refer to the resulting MSTs as power weighted
Euclidean MSTs.

One of the main objects of interest in the study of power weighted Euclidean
MST is its total weight: How does it scale with the number of nodes and the
power weight exponent and what are its convergence properties? Analytical
results for such MSTs have been studied extensively before (see Steele (1988,
1993), Kesten and Lee (1996), Penrose and Yukich (2003) and references
therein). For example, Steele (1988) uses edge counting techniques to obtain
variance estimates for the MST weight and Kesten and Lee (1996) use martingale
methods to obtain central limit theorems (CLTs) for the MST weight,
appropriately scaled and centred. Penrose and Yukich (2003) use coupling
arguments to obtain weak laws for functionals of point processes thereby
including the MST as a special case. Recently Chatterjee and Sen (2017) used
percolation theoretic arguments to study convergence rate of the CLTs for
Euclidean MSTs.

In this paper, we study MSTs of Euclidean random graphs whose edge weights
depend on the _individual locations_ of the endvertices. Such MSTs frequently
arise in practice and as an example, suppose it is required to establish a
fully connected wireless communication network among the set of nodes randomly
located in a geographical area. An edge between two nodes signifies a
potential communication link with the corresponding weight being proportional
to the cost of physically installing the link. If some areas within the area
are highly populated, it might actually be cost effective to set up links in
such “hotspots”. Thus the edge weights are location dependent and it is of
interest to estimate the minimum cost of setting up such a network. Throughout
we use the unit square for illustrating our results and the analysis holds
analogous for other regular shapes like rectangle or circle.

In the rest of this section, we describe the model under consideration and
describe an important property regarding the maximum vertex degree, that
distinguishes location dependent MSTs from their homogenous (i.e. location
independent) counterparts. We then describe the outline and the main
objectives of the paper towards understanding the properties of location
dependent MSTs.

### Model Description

Let $f$ be any distribution on the unit square $S$ satisfying such that

$\epsilon_{1}\leq\inf_{x\in S}f(x)\leq\sup_{x\in S}f(x)\leq\epsilon_{2}$ (1.1)

for some constants $0<\epsilon_{1}\leq\epsilon_{2}<\infty.$ Throughout all
constants are independent of $n.$

Let $\\{X_{i}\\}_{i\geq 1}$ be independently and identically distributed
(i.i.d.) with the distribution $f(.)$ defined on the probability space
$(\Omega,{\cal F},\mathbb{P}).$ For $n\geq 1,$ let
$K_{n}=K(X_{1},\ldots,X_{n})$ be the complete graph whose edges are obtained
by connecting each pair of nodes $X_{i}$ and $X_{j}$ by the straight line
segment $(X_{i},X_{j})$ with $X_{i}$ and $X_{j}$ as endvertices.

A path ${\cal P}=(Y_{1},\ldots,Y_{t})$ containing $t$ distinct vertices is a
subgraph of $K_{n}$ with vertex set $\\{Y_{j}\\}_{1\leq j\leq t}$ and edge set
$\\{(Y_{j},Y_{{j+1}})\\}_{1\leq j\leq t-1}.$ The nodes $Y_{1}$ and $Y_{t}$ are
said to be _connected_ by edges of the path ${\cal P}.$

A subgraph ${\cal T}$ of $K_{n}$ with vertex set $\\{Y_{i}\\}_{1\leq i\leq t}$
and edge set $E_{\cal T}$ is said to be a _tree_ (Steele (1988)) if the
following two conditions hold:
$(1)$ The graph ${\cal T}$ is connected; i.e., any two nodes in ${\cal T}$ are
connected by a path containing only edges in $E_{\cal T}.$
$(2)$ The graph ${\cal T}$ is acyclic; i.e., no subgraph of ${\cal T}$ is a
cycle.
The tree ${\cal T}$ is said to be a _spanning tree_ of $K_{n}$ if ${\cal T}$
contains all the $n$ nodes
$\\{X_{k}\\}_{1\leq k\leq n}.$

In what follows we assign weights to edges of the graph $K_{n}$ and study
minimum weight spanning trees.

### Minimum spanning trees

For points $x,y\in S,$ we let $d(x,y)$ denote the Euclidean distance between
$x$ and $y$ and let $h:S\times S\rightarrow(0,\infty)$ be a deterministic
measurable function satisfying

$c_{1}d(x,y)\leq h(x,y)=h(y,x)\leq c_{2}d(x,y)$ (1.2)

for some positive constants $c_{1},c_{2}.$ For a constant $\alpha>0$ and for
$1\leq i<j\leq n$ we let $h^{\alpha}(X_{i},X_{j})=h^{\alpha}(e)$ denote the
_weight_ of the edge $e=(X_{i},X_{j})$ with corresponding edge weight exponent
$\alpha.$ We simply refer to $h^{\alpha}(e)$ as the weight of the edge $e$ and
define $d(e)=d(X_{i},X_{j})$ to be the Euclidean length of $e.$ Unless
mentioned otherwise, all weights are with respect to the edge weight exponent
$\alpha$ and all lengths are Euclidean.

For a tree ${\cal T}$ with vertex set $\\{Y_{1},\ldots,Y_{t}\\},$ the weight
of ${\cal T}$ is the sum of the weights of the edges in ${\cal T};$ i.e.,
$W({\cal T}):=\sum_{e\in{\cal T}}h^{\alpha}(e).$ Let ${\cal T}_{n}$ be a
spanning tree of $K_{n}$ containing all the nodes $\\{X_{i}\\}_{1\leq i\leq
n}$ and satisfying

$MST_{n}=W({\cal T}_{n}):=\min_{{\cal T}}W({\cal T}),$ (1.3)

where the minimum is taken over all spanning trees ${\cal T}.$ We denote
${\cal T}_{n}$ to be the _minimum spanning tree_ (MST) with corresponding
weight $MST_{n}.$ If there is more than one choice for ${\cal T}_{n},$ we
choose one according to a deterministic rule.

Let $d(X_{i})=d\left(X_{i},{\cal T}_{n},h\right)$ denote the degree of the
node $X_{i},1\leq i\leq n$ in the MST ${\cal T}_{n}$ with edge weight function
$h$ so that $\sum_{i=1}^{n}d(X_{i})=2(n~{}-~{}1),$ since ${\cal T}_{n}$
contains $n-1$ edges. Taking expectations, we therefore get that
$n\mathbb{E}d(X_{1})=2(n-1)$ and so $\mathbb{E}d(X_{1})\leq 2.$ In case the
edge weight function $h~{}=~{}d,$ the Euclidean length, then the weight of any
edge does not depend on the location of its endvertices and the _maximum_
degree of any node in ${\cal T}_{n}$ is at most $6,$ almost surely. This is
because the angle between any two edges in the MST sharing an endvertex,
cannot be more than 60 degrees (see Aldous and Steele (1992)). This geometric
property frequently occurs in the study of the properties of the random MST
(Kesten and Lee (1996), Yukich (2000)).

For edge weight functions $h$ that are location dependent, it is possible for
the maximum degree of a vertex in the MST to take arbitrary large values with
positive probability as stated in the following result.

######  Proposition 1.

For every integer $K\geq 2$ there exists an edge weight function $h=h_{K}$
satisfying (1.2), a sequence $n_{l}\rightarrow\infty$ as $l\rightarrow\infty$
and a constant $\epsilon_{0}=\epsilon_{0}(K)>0$ such that

$\mathbb{P}\left(\max_{1\leq i\leq n_{l}}d\left(X_{i},{\cal
T}_{n_{l}},h\right)\geq K\right)\geq\epsilon_{0}$ (1.4)

for all $l\geq 1.$

In light of Proposition 1, we are therefore interested to study the effect of
large vertex degrees on the total weight of location dependent MSTs. We
demonstrate via common properties like variance, deviation estimates and
almost sure convergence, that the total weight behaves roughly the same way as
in the location independent case.

### Paper outline

The paper is organized as follows. In Section 2, we prove Proposition 1 and in
Section 3, we state and prove deviation estimates for the weight of location
dependent MSTs and also obtain upper and lower bounds for their expected
value. We use stochastic domination and coupling techniques to obtain the
deviation estimates and provide numerical simulations to illustrate the bounds
obtained. We show that the MST weight $MST_{n}$ defined in (1.3) still remains
of the order of $n^{1-\frac{\alpha}{2}}$ as in the location independent case.

Next in Section 4, we use the deviation estimates obtained in Section 3 to
find upper bounds on the variance of location dependent MSTs. The main tools
we use in this section are one node difference estimates and the martingale
difference method and we also briefly explain using Propostion 1, how the
analysis varies between the location dependent and independent cases. As
before the variance upper bound is of the order of $n^{1-\alpha}$ and the same
order as in the location independent case.

In Section 5, we obtain lower bounds on the variance of MST weight by studying
occurrence of predetermined nice configurations that differ in the location of
at most one node. In particular combining with the variance upper bound
obtained in Section 5, we obtain that the variance _is_ of the order of
$n^{1-\alpha}.$

Finally in Sections 6 and 7, for completeness, we study a.s. convergence for
location dependent MSTs and uniform MSTs using subsequence arguments and the
deviation and variance estimates obtained in the previous sections.

##  2 Proof of Proposition 1

We start with some preliminary computations. For $i\geq 1$ let $n_{i}=D\cdot
i^{3}$ for some constant $D>0$ to be determined later and let
$q_{i}=\frac{2K-1}{\sqrt{n_{i}}}.$ Place disjoint $10q_{i}\times 10q_{i}$
squares $S^{big}_{i}$ along the diagonal of the unit square $S$ as shown in
Figure 1 $(a)$ and choose $D>0$ large enough so that the total sum length of
the diagonals of the squares in $\\{S^{big}_{i}\\}$ is at most the length of
the diagonal of $S;$ i.e., we choose $D$ large enough so that

$\sum_{i\geq 1}10q_{i}\sqrt{2}\leq\sqrt{2}.$

Let $S_{i}$ be the $q_{i}\times q_{i}$ subsquare with the same centre as
$S^{big}_{i}$ as shown in Figure 1 $(b)$ and consider $K$ small subsquares
each of size $\frac{1}{\sqrt{n_{i}}}\times\frac{1}{\sqrt{n_{i}}}$ placed
$x_{i}=\frac{1}{\sqrt{n_{i}}}$ apart on each of the four sides of $S_{i}.$ The
total number of the small subsquares is $4(K-1),$ which we label as
$S_{i}(1),\ldots,S_{i}(4K-4).$ The central small square (labeled $S_{i}(0)$)
has the same centre as the square $S_{i}$ and is also of size
$\frac{1}{\sqrt{n_{i}}}\times\frac{1}{\sqrt{n_{i}}}.$

Let $c_{1}$ and $c_{2}$ be positive constants such that
$c_{1}<\frac{c_{2}}{8K}$ and define the edge weight function $h$ as:

$h(u,v)=\left\\{\begin{array}[]{cc}c_{1}d(u,v)&\text{ if
}u\in\cup_{j}\\{S_{j}(0)\\}\text{ or }v\in\cup_{j}\\{S_{j}(0)\\}\\\ &\\\
c_{2}d(u,v)&\text{ otherwise},\end{array}\right.$ (2.1)

where $d(u,v)$ represents the Euclidean distance between $u$ and $v$ as
before. By choice of $h$ in (2.1), the edge weight containing a node is less
if the node is present in one of the central squares and larger otherwise.

(a)

(b)

Figure 1: $(a)$ The $10q_{i}\times 10q_{i}$ squares placed along the diagonal
of the unit square. $(b)$ The $q_{i}\times q_{i}$ square $S_{i}$ along with
the smaller subsquares.

For $i\geq 1,$ let ${\cal T}_{n_{i}}$ be the MST of the nodes
$\\{X_{k}\\}_{1\leq k\leq n_{i}}$ as defined in (1.3) with edge weight
function $h$ as in (2.1). To identify nodes in ${\cal T}_{n_{i}}$ with large
degree we define $E_{K}(i)$ to be the event that there is exactly one node
$v_{i}\in\\{X_{k}\\}_{1\leq k\leq n_{i}}$ present in $S_{i}(l)$ for each
$0\leq l\leq 4K-4$ and the rest of $S_{i}^{big}$ is empty. We recall from the
first paragraph of this section that $S_{i}^{big}$ is the
$10q_{i}\times 10q_{i}$ square with the same centre as $S_{i}(0).$

The following Lemma implies that the event $E_{K}(i)$ occurs with positive
probability and that if $E_{K}(i)$ occurs, then the node $v_{0}$ present in
the central square $S_{i}(0)$ has large degree.

######  Lemma 1.

There exists a constant $\epsilon_{0}>0$ depending only on $K,\epsilon_{1}$
and $\epsilon_{2}$ such that

$\mathbb{P}(E_{K}(i))\geq\epsilon_{0}.$ (2.2)

If $E_{K}(i)$ occurs and if ${\cal T}_{loc}$ denotes the induced subgraph of
${\cal T}_{n_{i}}$ formed by the nodes in $\\{v_{j}\\}_{0\leq j\leq 4K-4},$
then ${\cal T}_{loc}$ is a tree (more specifically, a star graph) with edge
set $\\{(v_{0},v_{j})\\}_{1\leq j\leq 4K-4}.$

From Lemma 1, we therefore get that the degree of $v_{0}$ in the MST ${\cal
T}_{n_{i}}$ is $4K-4$ if the event $E_{K}(i)$ occurs. From the probability
estimate (2.2), we therefore get Proposition 1.

We now prove Lemma 1 beginning with (2.2).
_Proof of ( 2.2) in Lemma 1_: Any node of $\\{X_{k}\\}_{1\leq k\leq n_{i}}$ is
present within the square $S_{i}(l)$ with probability
$p_{i}(l):=\int_{S_{i}(l)}f(x)dx$ and so

$\mathbb{P}(E_{K}(i))={n_{i}\choose
4K-3}(4K-3)!\prod_{l=0}^{4K-4}p_{i}(l)\left(\int_{S\setminus
S_{i}^{big}}f(x)dx\right)^{n_{i}-4K+3}.$ (2.3)

The area of the square $S_{i}(l)$ equals $\frac{1}{n_{i}}$ and so
$p_{i}(l)\geq\frac{\epsilon_{1}}{n_{i}}$ using the bounds in (1.1). Similarly,
$\int_{S_{i}^{big}}f(x)dx\leq\epsilon_{2}100q_{i}^{2}=\frac{C}{n_{i}}$ where
$C=100\epsilon_{2}(2K-1)^{2}$ and so

$\mathbb{P}(E_{K}(i))\geq{n_{i}\choose
4K-3}(4K-3)!\left(\frac{\epsilon_{1}}{n_{i}}\right)^{4K-3}\left(1-\frac{C}{n_{i}}\right)^{n_{i}}.$
(2.4)

For $a>2b$ we have ${a\choose b}b!\geq(a-b)^{b}\geq\frac{a^{b}}{2^{b}}.$
Therefore choosing $i$ larger if necessary so that $n_{i}\geq 8K-6$ and
setting $a=n_{i}$ and $b=4K-3,$ we get from (2.4) that

$\mathbb{P}(E_{K}(i))\geq\left(\frac{\epsilon_{1}}{2}\right)^{4K-3}\cdot\left(1-\frac{C}{n_{i}}\right)^{n_{i}}.$
(2.5)

To evaluate the final term in (2.5), we use $1-y\geq e^{-2y}$ for all
$0<y<\frac{1}{2}.$ To see this estimate is true we write
$\log(1-y)=-y-\sum_{k\geq 2}\frac{y^{k}}{k}$ and use $y<\frac{1}{2}$ to get
that

$\sum_{k\geq 2}\frac{y^{k}}{k}\leq\frac{1}{2}\sum_{k\geq
2}y^{k}=\frac{y^{2}}{2(1-y)}\leq y^{2}<y.$

Choosing $i$ large enough so that
$y=\frac{(4K-3)\epsilon_{2}}{n_{i}}<\frac{1}{2},$ we then get from (2.5) that

$\mathbb{P}(E_{K}(i))\geq\left(\frac{\epsilon_{1}}{2}\right)^{4K-3}\cdot
e^{-2C},$

proving (2.2).

_Proof of rest of Lemma 1_: Let $S_{i}^{big}$ be the $10q_{i}\times 10q_{i}$
square in Figure 1$(b).$ First we show that ${\cal T}_{loc}$ is a tree by a
contradiction argument. Suppose for example that two nodes in opposite
$\frac{1}{\sqrt{n_{i}}}\times\frac{1}{\sqrt{n_{i}}}$ squares are joined by a
path $P$ in ${\cal T}_{n_{i}}$ containing at least one vertex not in
$\\{v_{i}\\}$ as in Figure 1$(b).$ Since $E_{K}(i)$ occurs, the rest of
$S_{i}^{big}$ not containing $\cup_{l}S_{i}(l)$ is empty and so the path $P$
contains at least two “long” edges $f_{1}=(u_{1},x_{1}),f_{2}=(u_{2},x_{2})$
with endvertices outside $S_{i}^{big}$ as shown in Figure 1$(b).$ The nodes
$u_{1}$ and $u_{2}$ both belong to $\\{v_{i}\\}_{1\leq i\leq 4K-4}$ and the
dotted edge $(u_{1},u_{2})$ is not present in the MST ${\cal T}_{n_{i}}$
because otherwise, we would get a cycle.

The weights of the edges $f_{1}$ and $(u_{1},u_{2})$ equal
$(c_{2}d(u_{1},x_{1}))^{\alpha}$ and
$(c_{2}d(u_{1},u_{2}))^{\alpha},$ respectively, by definition of the edge
weight function in (2.1). The length $d(u_{1},x_{1})$ of the edge
$f_{1}=(u_{1},x_{1})$ is at least $\frac{9q_{i}}{2},$ the width of the annulus
$S_{i}^{big}\setminus S_{i}$ and the length of $(u_{1},u_{2})$ at most
$q_{i}\sqrt{2}.$ This implies that removing the edge $f_{1}$ and adding
$(u_{1},u_{2}),$ we would get an MST with weight strictly larger than ${\cal
T}_{n_{i}},$ a contradiction. This proves that ${\cal T}_{loc}$ is a tree.

Next, to see that ${\cal T}_{loc}$ is a star graph, we use the definition of
the edge weight function (2.1) and obtain that the weight of any edge of the
form $(v_{0},v_{j})$ is at most

$(c_{1}\cdot
d(v_{0},v_{j}))^{\alpha}\leq\left(c_{1}\cdot\left(\frac{q_{i}}{\sqrt{2}}+\frac{\sqrt{2}}{\sqrt{n_{i}}}\right)\right)^{\alpha}\leq\left(\frac{c_{1}\cdot
4K}{\sqrt{n_{i}}}\right)^{\alpha}$ (2.6)

since $q_{i}=\frac{2K-1}{\sqrt{n_{i}}}$ (see first paragraph of this Section).
Similarly, the weight of any edge of the form $(v_{s},v_{t}),s,t\neq 0$ is at
least $\left(\frac{c_{2}}{\sqrt{n_{i}}}\right)^{\alpha}.$ Since
$c_{1}<\frac{c_{2}}{8K}$ (see (2.1)), we get that $(v_{s},v_{t})$ has larger
weight that $(v_{0},v_{j}).$ Thus the minimum weight tree containing all the
nodes $\\{v_{j}\\}_{0\leq j\leq 4K-4}$ is the star graph with vertex set
$\\{(v_{0},v_{j})\\}_{0\leq j\leq 4K-4}.$

##  3 Deviation estimates for the MST

As a first step in the study of properties of location dependent MSTs, we
obtain deviation estimates in this Section. The bounds obtained are of same
order and we also use these estimates in later Sections for the study of
variance and almost sure convergence.

We begin with a couple of preliminary definitions. Let
$\epsilon_{1},\epsilon_{2}$ be as in (1.1) and set
$\delta=\delta(\alpha)=\epsilon_{1}$ if the edge weight exponent $\alpha\leq
1$ and $\delta=\epsilon_{2}$ if $\alpha>1.$ Recalling that $c_{1}$ and $c_{2}$
are the bounds for the edge weights as in (1.2), we define for $A>0$ the terms
$C_{1}(A)=C_{1}(A,c_{1},c_{2},\epsilon_{1},\epsilon_{2},\alpha)$ and
$C_{2}(A)=C_{2}(A,c_{1},c_{2},\epsilon_{1},\epsilon_{2},\alpha)$ as

$\displaystyle C_{1}(A)$ $\displaystyle:=$
$\displaystyle\frac{(c_{1}A)^{\alpha}}{2A^{2}}(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}}\text{
and }$ $\displaystyle C_{2}(A)$ $\displaystyle:=$
$\displaystyle(2c_{2}A)^{\alpha}\left(1+\frac{\mathbb{E}T^{\alpha}}{A^{2}}\right),$
(3.1)

where $T$ is a geometric random variable with success parameter
$p=1-e^{-\delta A^{2}},$ independent of the node locations $\\{X_{i}\\};$
i.e., $\mathbb{P}(T=k)=(1-p)^{k-1}p$ for all integers $k\geq 1.$ Letting
$MST_{n}$ be the MST weight as defined in (1.3), we have the following main
result.

######  Theorem 2.

Let $\alpha>0$ be the edge weight exponent. For every $A>0$ and integer $k\geq
1$ and all $n\geq n_{0}(A,k)$ large,

$\mathbb{P}\left(MST_{n}\geq
C_{1}(A)n^{1-\frac{\alpha}{2}}\left(1-\frac{4\sqrt{A}}{n^{1/4}}\right)\right)\geq
1-e^{-n^{1/3}},$ (3.2) $\mathbb{P}\left(MST_{n}\leq
C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{2}{n^{1/16}}\right)\right)\geq
1-\frac{1}{n^{2k}}$ (3.3)

and

$C^{k}_{1}(A)\left(1-\frac{36k\sqrt{A}}{n^{1/4}}\right)\leq\mathbb{E}\left(\frac{MST^{k}_{n}}{n^{k\left(1-\frac{\alpha}{2}\right)}}\right)\leq
C^{k}_{2}(A)\left(1+\frac{2k}{n^{1/16}}\right).$ (3.4)

### Remarks on Theorem 2

From Theorem 2, we see that the weights of the MST in the location dependent
case, is of the same order $n^{1-\frac{\alpha}{2}}$ as in the location
independent case (see Steele (1988)). In fact, using (3.4) we get that the
normalized MST weight $\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}$ in
fact satisfies

$c_{1}^{\alpha}\cdot\beta_{low}(\alpha)\leq\liminf_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq\limsup_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq
c_{2}^{\alpha}\cdot\beta_{up}(\alpha),$ (3.5)

where

$\beta_{low}(\alpha)=\beta_{low}(\alpha,\epsilon_{1},\epsilon_{2}):=\sup_{A>0}\frac{A^{\alpha}}{2A^{2}}(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}},$
(3.6)
$\beta_{up}(\alpha)=\beta_{up}(\alpha,\epsilon_{1},\epsilon_{2}):=\inf_{A>0}(2A)^{\alpha}\left(1+\frac{\mathbb{E}{T}^{\alpha}}{A^{2}}\right),$
(3.7)

and $T$ is a geometric random variable with success parameter $p=1-e^{-\delta
A^{2}}$ (see (3.1)).

For the case of homogenous distribution $\epsilon_{1}=\epsilon_{2}=1$ we get

$\beta_{low}(\alpha)=\frac{1}{2}\sup_{A>0}A^{\alpha-2}(1-e^{-A^{2}})e^{-8A^{2}}>0$
(3.8)

and

$\beta_{up}(\alpha)=\inf_{A>0}(2A)^{\alpha}\left(1+\frac{\mathbb{E}T^{\alpha}}{A^{2}}\right)<\infty,$
(3.9)

where $T$ is a geometric random variable with success parameter
$p=1-e^{-A^{2}}.$

For illustration, we plot $\beta_{low}(\alpha)$ and $\beta_{up}(\alpha)$ as a
function of $\alpha$ in Figures 3 and 2, respectively. As we see from the
figures $\beta_{up}(\alpha)$ increases with $\alpha$ and $\beta_{low}(\alpha)$
decreases with $\alpha.$ Expressions (3.8) and (3.9) also allow us to
numerically evaluate the bounds in (3.5) for various values of $\alpha.$ For
example, for $\alpha=1,$ we get that

$\beta_{low}(1)=\frac{1}{2}\sup_{A>0}A^{-1}(1-e^{-A^{2}})e^{-8A^{2}}\approx
0.0735633>\frac{1}{20}$

and since $\mathbb{E}T=\frac{1}{p}=\frac{1}{1-e^{-A^{2}}},$ we get that

$\beta_{up}(1)=\inf_{A>0}2A\left(1+\frac{1}{A^{2}(1-e^{-A^{2}})}\right)\approx
4.46256<5.$

Substituting these bounds back in (3.5) we find that

$\frac{c_{1}^{\alpha}}{20}\leq\liminf_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq\limsup_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq
5\cdot c_{2}^{\alpha}$ (3.10)

and this obtains bounds for the scaled MST weights in terms of the edge weight
function parameters $c_{1}$ and $c_{2}.$

Similarly for $\alpha=2,$ we get that

$\beta_{low}(2)=\frac{1}{2}\sup_{A>0}(1-e^{-A^{2}})e^{-8A^{2}}\approx
0.0216525$

and since
$\mathbb{E}T^{2}=\frac{2-p}{p^{2}}=\frac{1+e^{-A^{2}}}{(1-e^{-A^{2}})^{2}},$
we get that

$\beta_{up}(2)=\inf_{A>0}(2A)^{2}\left(1+\frac{1+e^{-A^{2}}}{A^{2}(1-e^{-A^{2}})^{2}}\right)\approx
13.8772$

and we have analogous bounds as in (3.10) in this case as well.

Figure 2: Plot of $\beta_{up}(\alpha)$ as a function of $\alpha$ for the
homogenous case $\epsilon_{1}=\epsilon_{2}=1.$ Figure 3: Plot of
$\beta_{low}(\alpha)$ as a function of $\alpha$ for the homogenous case
$\epsilon_{1}=\epsilon_{2}=1.$

In general, $\beta_{low}(\alpha)$ and $\beta_{up}(\alpha)$ in (3.5) can be
evaluated to get some knowledge of the dependence of the normalized MST weight
on the node distribution parameters $\epsilon_{1},\epsilon_{2}$ (see (1.1))
and the edge weight function parameters $c_{1},c_{2}$ (see (1.2)). For
example, suppose the distribution $f=\frac{1}{2}$ on $[0,0.5]^{2}$ and
$f=\frac{7}{6}$ on the remaining area in $S$ so that $\int f=1.$ In this case
$\epsilon_{1}=\frac{1}{2}$ and $\epsilon_{2}=\frac{7}{6}$ and we directly
evaluate (3.6) and (3.7) to get that $\beta_{low}(1)\approx 0.0346363$ and
$\beta_{up}(1)\approx 4.92912.$

As a final remark, we provide a simple upper bound for $\mathbb{E}T^{\alpha}$
in order to obtain quick evaluations of $\beta_{up}(\alpha)$ in (3.7). Using
$\mathbb{P}(T\geq k)=(1-p)^{k-1}\leq e^{-p(k-1)}$ where $p=1-e^{-\delta
A^{2}},$ we see that relation (7.5) in Appendix is satisfied and so letting
$r$ be the smallest integer greater than or equal $\alpha$ we have from (7.6)
that

$\mathbb{E}T^{\alpha}\leq\mathbb{E}T^{r}\leq\frac{r!}{(1-e^{-p})^{r}}.$

Plugging this estimate into (3.7) provides an upper bound for
$\beta_{up}(\alpha).$

### Proof outline and Poissonization

The rough idea for the proof of Theorem 2 is as follows. We first tile the
unit square into small subsquares and for obtaining the lower bound, we
determine configurations within these subsquares that result in long edges.
For the upper bound, we explicitly construct a spanning tree whose weight is
at most a constant multiple of the weight of the MST, with high probability,
i.e., with probability one as $n\rightarrow\infty.$

To prove the deviation estimates in Theorem 2, we use Poissonization and let
${\cal P}$ be a Poisson process in the unit square $S$ with intensity $nf(.).$
We join each pair of nodes by a straight line segment and denote the resulting
complete graph as $K^{(P)}_{n}.$ As in (1.3), we let $MST_{n}^{(P)}$ be the
weight of the MST of $K^{(P)}_{n}$ and first find deviation estimates for
$MST_{n}^{(P)}.$ We then use dePoissonization to obtain corresponding
deviation estimates for $MST_{n},$ the weight of the MST of the complete graph
$K_{n}$ as defined in (1.3).

For a real number $A>0,$ we tile the unit square $S$ into small
$\frac{A(n)}{\sqrt{n}}\times\frac{A(n)}{\sqrt{n}}$ squares $\\{R_{i}\\}_{1\leq
i\leq\frac{n}{A^{2}(n)}}$ where $A(n)\in\left[A,A+\frac{1}{\log{n}}\right]$ is
chosen such that $\frac{\sqrt{n}}{A(n)}$ is an integer. This is possible since

$\frac{\sqrt{n}}{A}-\frac{\sqrt{n}}{A+(\log{n})^{-1}}=\frac{\sqrt{n}}{\log{n}}\cdot\frac{1}{A(A+(\log{n})^{-1})}\geq\frac{\sqrt{n}}{2A^{2}\log{n}}$
(3.11)

for all $n$ large. For notational simplicity, we denote $A(n)$ as $A$
henceforth and label the squares as in Figure 4 so that $R_{i}$ and $R_{i+1}$
share an edge for $1\leq i\leq\frac{n}{A^{2}}-1.$

Figure 4: Tiling the unit square into $N=\frac{n}{A^{2}}$ smaller
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ squares $\\{R_{l}\\}_{1\leq
l\leq\frac{n}{A^{2}}}.$

### Lower deviation bounds (3.2)

For $1\leq i\leq\frac{n}{A^{2}}$ let $E(R_{i})$ denote the event that the
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ square $R_{i}$ is occupied i.e.,
contains at least one node of ${\cal P},$ and all squares sharing a corner
with $R_{i}$ are empty. If $E(R_{i})$ occurs, then there is at least one edge
in the MST of $K^{(P)}_{n}$ with one endvertex in $R_{i}$ and other endvertex
in a square not sharing a corner with $R_{i}.$ Such an edge has a Euclidean
length of at least $\frac{A}{\sqrt{n}}$ and so a weight of at least
$\left(\frac{c_{1}A}{\sqrt{n}}\right)^{\alpha}$ (see (1.2)). Consequently

$MST^{(P)}_{n}\geq\frac{1}{2}\cdot\sum_{i=1}^{\frac{n}{A^{2}}}\left(\frac{c_{1}A}{\sqrt{n}}\right)^{\alpha}1{1}(E(R_{i}))=\frac{1}{2}\cdot\left(\frac{c_{1}A}{\sqrt{n}}\right)^{\alpha}\cdot
G_{\alpha},$ (3.12)

where $G_{\alpha}:=\sum_{i=1}^{\frac{n}{A^{2}}}1{1}(E(R_{i}))$ and the factor
$\frac{1}{2}$ occurs, since each edge is counted twice in the summation.

To estimate $G_{\alpha},$ we would like to split it into sums of independent
r.v.s using the following construction. For a square $R_{i},$ let ${\cal
N}(R_{i})$ be the set of all squares sharing a corner with $R_{i},$ including
$R_{i}.$ If $R_{i}$ does not intersect the sides of the unit square $S,$ then
there are $9$ squares in ${\cal N}(R_{i})$ and if $R_{j}$ is another square
such that ${\cal N}(R_{i})\cap{\cal N}(R_{j})=\emptyset,$ then the
corresponding events $E(R_{i})$ and $E(R_{j})$ are independent, by Poisson
property. We therefore extract nine disjoint subsets $\\{{\cal
U}_{l}\\}_{1\leq l\leq 9}$ of $\\{R_{i}\\}$ with the following properties:
$(A)$ If $R_{i},R_{j}\in{\cal U}_{l},$ then $\\#{\cal N}(R_{i})=\\#{\cal
N}(R_{j})=9$ and ${\cal N}(R_{i})\cap{\cal N}(R_{j})=\emptyset.$
$(B)$ The number of squares $\\#{\cal
U}_{l}\geq\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}$ for each $1\leq l\leq 9.$
This is possible since there are at most
$\frac{4\sqrt{n}}{A}-4<\frac{4\sqrt{n}}{A}$ squares in $\\{R_{k}\\}$
intersecting the sides of the unit square $S$ and the total number of squares
in $\\{R_{k}\\}$ is $\frac{n}{A^{2}}.$

We now write
$G_{\alpha}=\sum_{i=1}^{\frac{n}{A^{2}}}1{1}(E(R_{i}))\geq\sum_{l=1}^{9}\sum_{R_{i}\in{\cal
U}_{l}}1{1}(E(R_{i})),$ where each inner summation on the right side is a sum
of independent Bernoulli random variables, which we bound via standard
deviation estimates. Indeed for $1\leq l\leq 9$ and $R_{i}\in{\cal U}_{l},$
the number of nodes $N(R_{i})$ is Poisson distributed with mean
$n\int_{R_{i}}f(x)dx\in[\epsilon_{1}A^{2},\epsilon_{2}A^{2}]$ (see (1.1)) and
so $R_{i}$ is occupied with probability at least $1-e^{-\epsilon_{1}A^{2}}.$
Also each of the eight squares sharing a corner with $R_{i}$ is empty with
probability at least $e^{-\epsilon_{2}A^{2}},$ implying that
$\mathbb{P}(E(R_{i}))\geq(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}}.$
Using the standard deviation estimate (7.2) of Lemma 13 in Appendix with
$\mu_{1}=(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}},m=\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}$
and $\epsilon=\frac{1}{m^{1/4}}$ we then get that

$\mathbb{P}_{0}\left(\sum_{R_{i}\in{\cal
U}_{l}}1{1}(E(R_{i}))\geq(1-\epsilon)\left(\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}\right)(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}}\right)\geq
1-e^{-D_{1}\epsilon^{2}n}$ (3.13)

for some constant $D_{1}>0$ not depending on $l.$ Since
$m^{1/4}<\left(\frac{n}{9A^{2}}\right)^{1/4},$ we get that
$D_{1}\epsilon^{2}n\geq 2D_{2}\sqrt{n}$ for some constant $D_{2}>0$ and since
$m^{1/4}>\left(\frac{n}{10A^{2}}\right)^{1/4}$ for all $n$ large, we have

$(1-\epsilon)\left(\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}\right)\geq\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}-\frac{n}{A^{2}m^{1/4}}\geq\frac{n}{9A^{2}}\left(1-\frac{36\sqrt{A}}{n^{1/4}}\right)$

for all $n$ large.

Letting

$E_{low}:=\left\\{G_{\alpha}\geq(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}}\frac{n}{A^{2}}\left(1-\frac{36\sqrt{A}}{n^{1/4}}\right)\right\\},$

we get from (3.13) that $\mathbb{P}_{0}(E_{low})\geq 1-9e^{-2D_{2}\sqrt{n}}$
and moreover, from (3.12) we also get that

$MST^{(P)}_{n}1{1}(E_{low})\geq\Delta_{n}:=C_{1}(A)n^{1-\frac{\alpha}{2}}\left(1-\frac{36\sqrt{A}}{n^{1/4}}\right),$

where $C_{1}(A)$ is as defined in (3.1). From the estimate for the probability
of the event $E_{low}$ above we therefore get
$\mathbb{P}_{0}\left(MST_{n}^{(P)}\geq\Delta_{n}\right)\geq
1-9e^{-2D_{2}\sqrt{n}}$ for all $n$ large. To convert the estimate from
Poisson to the Binomial process, we let
$E_{P}:=\left\\{MST_{n}^{(P)}\geq\Delta_{n}\right\\},E:=\left\\{MST_{n}\geq\Delta_{n}\right\\}$
and use the dePoissonization formula (Bradonjic et al. (2010))

$\mathbb{P}(E)\geq 1-D\sqrt{n}\mathbb{P}(E^{c}_{P})$ (3.14)

for some constant $D>0$ to get that $\mathbb{P}(E)\geq
1-D\sqrt{n}e^{-2D_{2}\sqrt{n}}\geq 1~{}-~{}e^{-D_{2}\sqrt{n}}$ for all $n$
large. This proves (3.2) and so using

$\mathbb{E}MST^{k}_{n}\geq\mathbb{E}MST^{k}_{n}1{1}\left(MST_{n}\geq\Delta_{n}\right)\geq\Delta^{k}_{n}\left(1-e^{-D_{2}\sqrt{n}}\right)$

and

$\left(1-\frac{36\sqrt{A}}{n^{1/4}}\right)^{k}(1-e^{-D_{2}\sqrt{n}})\geq\left(1-\frac{36k\sqrt{A}}{n^{1/4}}\right)(1-e^{-D_{2}\sqrt{n}})\geq
1-\frac{37k\sqrt{A}}{n^{1/4}}$

for all $n$ large, we also obtain the lower bound on the expectation in (3.4).

To see that (3.14) is true, we let $N_{P}$ denote the random number of nodes
of ${\cal P}$ in all the squares $\\{S_{j}\\}$ so that $\mathbb{E}_{0}N_{P}=n$
and $\mathbb{P}_{0}(N_{P}=n)=e^{-n}\frac{n^{n}}{n!}\geq\frac{D_{1}}{\sqrt{n}}$
for some constant $D_{1}>0,$ using the Stirling formula. Given $N_{P}=n,$ the
nodes of ${\cal P}$ are i.i.d. with distribution $f(.)$ as defined in (1.1);
i.e., $\mathbb{P}_{0}(E_{P}^{c}|N_{P}=n)=\mathbb{P}(E^{c})$ and so

$\mathbb{P}_{0}(E_{P}^{c})\geq\mathbb{P}_{0}(E_{P}^{c}|N_{P}=n)\mathbb{P}_{0}(N_{P}=n)=\mathbb{P}(E^{c})\mathbb{P}_{0}(N_{P}=n)\geq\mathbb{P}(E^{c})\frac{D_{1}}{\sqrt{n}},$

proving (3.14).

### Upper deviation bounds (3.3)

As before, we first obtain upper bounds for the Poissonized MST
$MST^{(P)}_{n}.$ The idea is to first connect all the nodes within each square
$R_{j}$ to get a collection of subtrees and then join all these subtrees
together to get an overall spanning tree. Suppose there is at least one node
of the Poisson process ${\cal P}$ in the unit square $S$ and let
$R_{i_{1}},R_{i_{2}},\ldots,R_{i_{Q}},1\leq
i_{1}<i_{2}<\ldots<i_{Q}\leq\frac{n}{A^{2}},Q\leq\frac{n}{A^{2}}$ be the
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ squares containing all the nodes
of ${\cal P}.$ For $1\leq j\leq Q,$ let ${\cal T}_{i_{j}}$ be any spanning
tree containing all the nodes of $R_{i_{j}}$ and for $1\leq j\leq Q-1$ let
$e_{j+1}$ be any edge joining some node in $R_{i_{j}}$ and some node in
$R_{i_{j+1}}$ so that the union ${\cal T}_{uni}:=\cup_{1\leq j\leq Q}{\cal
T}_{i_{j}}\cup\cup_{2\leq l\leq Q}\\{e_{l}\\}$ is a spanning tree of the
complete graph $K^{(P)}_{n}.$ The weight $W({\cal T}_{uni})\geq MST_{n}^{(P)}$
and so it suffices to upper bound $W({\cal T}_{uni}).$

For $1\leq j\leq Q,$ there are $N(R_{i_{j}})$ nodes of the Poisson process in
the square $R_{i_{j}}$ and any two such nodes are connected by an edge of
length at most $\frac{A\sqrt{2}}{\sqrt{n}}.$ Therefore the spanning tree
${\cal T}_{i_{j}}$ has a total weight of at most
$N(R_{i_{j}})\cdot\left(\frac{c_{2}A\sqrt{2}}{\sqrt{n}}\right)^{\alpha},$
using the bounds for the function $h$ in (1.2). The edge $e_{j+1}$ that
connects some node in $R_{i_{j}}$ with some node of $R_{i_{j+1}}$ has a
Euclidean length of at most $\frac{2T_{j+1}A}{\sqrt{n}}$ where
$T_{j+1}:=i_{j+1}-i_{j}$ and therefore has a weight of at most
$\left(\frac{2c_{2}T_{j+1}A}{\sqrt{n}}\right)^{\alpha},$ by (1.2). In effect,

$\displaystyle W\left({\cal T}_{uni}\right)$ $\displaystyle\leq$
$\displaystyle\sum_{j=1}^{Q}N(R_{i_{j}})\cdot\left(\frac{c_{2}A\sqrt{2}}{\sqrt{n}}\right)^{\alpha}+\sum_{j=1}^{Q-1}\left(\frac{2c_{2}T_{j+1}A}{\sqrt{n}}\right)^{\alpha}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{\frac{n}{A^{2}}}N(R_{i})\cdot\left(\frac{c_{2}A\sqrt{2}}{\sqrt{n}}\right)^{\alpha}+\sum_{j=2}^{Q}\left(\frac{2c_{2}T_{j}A}{\sqrt{n}}\right)^{\alpha}.$

Setting $T_{1}:=i_{1}-1,T_{Q+1}:=\frac{n}{A^{2}}-i_{Q}$ and
$S_{\alpha}:=\sum_{j=1}^{Q+1}T_{j}^{\alpha}$ we then get

$\displaystyle MST_{n}^{(P)}\leq W\left({\cal
T}_{uni}\right)\leq\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(\sum_{i=1}^{\frac{n}{A^{2}}}N(R_{i})+S_{\alpha}\right).$
(3.15)

The first sum $\sum_{i=1}^{\frac{n}{A^{2}}}N(R_{i})$ in the right side of
(3.15) is a Poisson random variable with mean $n$ since this denotes the total
number of nodes of the Poisson process in the unit square. Using the deviation
estimate (7.1) in Appendix with $m=1,\mu_{2}=n$ and
$\epsilon=\frac{\log{n}}{\sqrt{n}},$ we have that

$\mathbb{P}_{0}\left(\sum_{i=1}^{\frac{n}{A^{2}}}N(R_{i})\leq
n\left(1+\frac{\log{n}}{\sqrt{n}}\right)\right)\geq 1-e^{-D(\log{n})^{2}}$
(3.16)

for some constant $D>0.$ Setting
$E_{node}:=\left\\{\sum_{i=1}^{\frac{n}{A^{2}}}N(R_{i})\leq
n\left(1+\frac{\log{n}}{\sqrt{n}}\right)\right\\},$ we get from (3.15) that

$MST_{n}^{(P)}1{1}(E_{node})\leq\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(n\left(1+\frac{\log{n}}{\sqrt{n}}\right)+S_{\alpha}\right).$
(3.17)

The second term $S_{\alpha}$ in (3.17) is well-defined for any configuration
$\omega$ of the Poisson process provided we set
$S_{\alpha}(\omega_{0})=\left(\frac{n}{A^{2}}-1\right)^{\alpha}$ where
$\omega_{0}$ is the configuration containing no node of the Poisson process in
the unit square $S.$ The following Lemma obtains an estimate on $S_{\alpha}.$

######  Lemma 3.

Let $T$ be a geometric random variable with success parameter
$p=1-e^{-A^{2}\delta}$ independent of the node locations $\\{X_{i}\\}.$ For
every even integer $m\geq 1$ and every $A>0$ and for all $n\geq n_{0}(m,A)$
large, we have

$\mathbb{P}_{0}\left(S_{\alpha}\leq\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}\mathbb{E}T^{\alpha}\right)\geq
1-\frac{D}{n^{7m/16}},$ (3.18)

where $D>0$ is a constant.

Since $S_{\alpha}$ is not an i.i.d. sum, we use coupling techniques to
estimate $S_{\alpha}$ and prove Lemma 3 at the end of this section.

We continue with the proof of the deviation upper bound. Let $m\geq 2$ be an
even integer to be determined later. Letting $E_{S}$ be the event on the left
side of (3.18) we have from the previously computed upper bound on
$MST_{n}^{(P)}$ (see (3.17)) that

$\displaystyle MST_{n}^{(P)}1{1}(E_{node}\cap E_{S})$ $\displaystyle\leq$
$\displaystyle\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(n\left(1+\frac{\log{n}}{\sqrt{n}}\right)+\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}\mathbb{E}T^{\alpha}\right)$
(3.19) $\displaystyle\leq$ $\displaystyle
C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{1}{n^{1/16}}\right)$

where $C_{2}(A)$ is as in (3.1) and the final estimate in (3.19) is obtained
using $\frac{2\log{n}}{\sqrt{n}}\leq\frac{1}{n^{1/16}}$ for all $n$ large.
From (3.19) and the estimates for the events
$E_{node}$ and $E_{S}$ from (3.16) and (3.18), respectively, we have

$\displaystyle\mathbb{P}_{0}\left(MST_{n}^{(P)}\leq
C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{1}{n^{1/16}}\right)\right)$
$\displaystyle\geq$ $\displaystyle 1-e^{-D(\log{n})^{2}}-\frac{D}{n^{7m/16}}$
(3.20) $\displaystyle\geq$ $\displaystyle 1-\frac{2D}{n^{7m/16}}$

for all $n$ large and some constant $D>0.$

From (3.20) and the dePoissonization formula (3.14), we obtain

$\mathbb{P}\left(MST_{n}\leq
C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{1}{n^{1/16}}\right)\right)\geq
1-\frac{2D\sqrt{n}}{n^{7m/16}}.$ (3.21)

Choosing $m$ large enough such that $\frac{7m}{16}-\frac{1}{2}\geq k,$ we
obtain the estimate in (3.3).

For bounding the expectation of $MST_{n}^{k},$ we let
$\Delta_{n}=C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{1}{n^{1/16}}\right)$
and write

$\displaystyle\mathbb{E}MST^{k}_{n}$ $\displaystyle=$
$\displaystyle\mathbb{E}MST^{k}_{n}1{1}(MST_{n}\leq\Delta_{n})+\mathbb{E}MST^{k}_{n}1{1}(MST_{n}>\Delta_{n})$
(3.22) $\displaystyle\leq$
$\displaystyle\Delta^{k}_{n}+\mathbb{E}MST^{k}_{n}1{1}(MST_{n}>\Delta_{n})$

To estimate $\Delta_{n}^{k},$ we use
$\left(1+\frac{1}{n^{1/16}}\right)^{k}\leq e^{k/n^{1/16}}\leq
1+\frac{2k}{n^{1/16}}$ for all $n$ large and get that $\Delta_{n}^{k}\leq
C_{2}^{k}(A)n^{k\left(1-\frac{\alpha}{2}\right)}\left(1+\frac{2k}{n^{1/16}}\right)$
for all $n$ large. For the second term in (3.22), we use the estimate
$MST_{n}\leq n\cdot\left(c_{2}\sqrt{2}\right)^{\alpha}$ since there are $n$
edges in the spanning tree, each such edge has an Euclidean length of at most
$\sqrt{2}$ and so the weight of any edge is at most
$(c_{2}\sqrt{2})^{\alpha},$ using (1.2). Letting
$\theta_{m}=\frac{7m}{16}-\frac{1}{2}-\frac{\alpha k}{2}$ and using the
probability estimate (3.21) we then get that

$\mathbb{E}MST^{k}_{n}\leq\Delta^{k}_{n}+\frac{3D_{2}n^{k}\sqrt{n}}{n^{7m/16}}\leq
C^{k}_{2}(A)n^{k\left(1-\frac{\alpha}{2}\right)}\left(1+\frac{2k}{n^{1/16}}+\frac{D_{3}}{n^{\theta_{m}}}\right)$

for all $n$ large and some constant $D_{3}>0.$ Choosing $m$ larger if
necessary so that $\theta_{m}\geq 1>\frac{1}{16},$ we obtain the expectation
upper bound in (3.4).

_Proof of Lemma 3_: We show that $S_{\alpha}(\omega)$ is monotonic in $\omega$
in the sense that adding more nodes increases $S_{\alpha}$ if $\alpha\leq 1$
and decreases $S_{\alpha}$ if $\alpha>1.$ This then allows us to use coupling
and upper bound $S_{\alpha}$ by simply considering homogenous Poisson
processes.

_Monotonicity of $S_{\alpha}$_: We recall that $\omega_{0}$ is the
configuration containing no node of the Poisson process in the unit square.
For a configuration $\omega\neq\omega_{0}$ let $1\leq
i_{1}(\omega)<\ldots<i_{Q}(\omega)\leq\frac{n}{A^{2}}$ be the indices of the
squares in $\\{R_{j}\\}$ containing at least one node of the Poisson process
${\cal P}.$ Letting $i_{0}(\omega)=1$ and $i_{Q+1}(\omega)=\frac{n}{A^{2}}$ we
have
$S_{\alpha}(\omega)=\sum_{j=0}^{Q}(i_{j+1}(\omega)-i_{j}(\omega))^{\alpha}.$
Suppose $\omega^{\prime}=\omega\cup\\{x\\}$ is obtained by adding a single
extra node at $x\in R_{j_{0}}$ for some $1\leq j_{0}\leq\frac{n}{A^{2}}.$ If
$j_{0}\in\\{i_{k}(\omega)\\}_{0\leq k\leq Q+1},$ then
$S_{\alpha}(\omega^{\prime})=S_{\alpha}(\omega).$ Else there exists $0\leq
a\leq Q$ such that $i_{a}(\omega)<j_{0}<i_{a+1}(\omega)$ and so

$S_{\alpha}(\omega^{\prime})=S_{\alpha}(\omega)+(i_{a+1}(\omega)-j_{0})^{\alpha}+(j_{0}-i_{a}(\omega))^{\alpha}-(i_{a+1}(\omega)-i_{a}(\omega))^{\alpha}.$

If $\alpha\leq 1$ then using $a^{\alpha}+b^{\alpha}\geq(a+b)^{\alpha}$ for
positive numbers $a,b$ we get that $S_{\alpha}(\omega^{\prime})\geq
S_{\alpha}(\omega).$ If $\alpha>1$ then
$a^{\alpha}+b^{\alpha}\leq(a+b)^{\alpha}$ and so
$S_{\alpha}(\omega^{\prime})\leq S_{\alpha}(\omega).$ This monotonicity
property together with coupling allows us to upper bound $S_{\alpha}$ as
follows. Letting $\delta=\epsilon_{2}$ if $\alpha\leq 1$ and
$\delta=\epsilon_{1}$ if $\alpha>1,$ we let ${\cal P}_{\delta}$ be a
homogenous Poisson process of intensity $\delta n$ on the unit square $S,$
defined on the probability space $(\Omega_{\delta},{\cal
F}_{\delta},\mathbb{P}_{\delta}).$

Let $F_{\delta}$ denote the event that there is at least node of ${\cal
P}_{\delta}$ in the unit square $S$ and set
$S^{(\delta)}_{\alpha}:=\left(\frac{n}{A^{2}}-1\right)^{\alpha}$ if
$F_{\delta}$ does not occur. If $F_{\delta}$ occurs, then as before let
$\\{i^{(\delta)}_{j}\\}_{1\leq j\leq Q_{\delta}}$ be the indices of the
squares in $\\{R_{j}\\}$ containing at least one node of ${\cal P}_{\delta}.$
Moreover, let $T^{(\delta)}_{j+1}:=i^{(\delta)}_{j+1}-i^{(\delta)}_{j}$ for
$1\leq j\leq Q_{\delta}$ and set $T^{(\delta)}_{1}:=i^{(\delta)}_{1}-1$ and
$T^{(\delta)}_{Q_{\delta}+1}:=\frac{n}{A^{2}}-i^{(\delta)}_{Q_{\delta}}.$
Defining
$S^{(\delta)}_{\alpha}:=\sum_{j=1}^{Q_{\delta}+1}\left(T^{(\delta)}_{j}\right)^{\alpha}$
in this case, we have for any $x>0$ that

$\mathbb{P}_{\delta}\left(S^{(\delta)}_{\alpha}<x\right)\leq\mathbb{P}_{0}\left(S_{\alpha}<x\right).$
(3.23)

The proof of (3.23) follows from standard coupling arguments and for
completeness, we provide a proof in Appendix.

To estimate $S^{(\delta)}_{\alpha}$ we let $N^{(\delta)}(R_{i}),1\leq
i\leq\frac{n}{A^{2}},$ be the random number of nodes of ${\cal P}_{\delta}$ in
the square $R_{i}.$ The random variables $\\{N^{(\delta)}(R_{i})\\}$ are
i.i.d. Poisson distributed each with mean $A^{2}\delta.$ For
$i\geq\frac{n}{A^{2}}+1,$ we define $N^{(\delta)}(R_{i})$ to be i.i.d. Poisson
random variables with mean $A^{2}\delta,$ that are also independent of
$\\{N^{(\delta)}(R_{i})\\}_{1\leq i\leq\frac{n}{A^{2}}}.$ Without loss of
generality, we associate the probability measure $\mathbb{P}_{\delta}$ for the
random variables $\\{N^{(\delta)}(R_{i})\\}_{i\geq\frac{n}{A^{2}}+1}$ as well.

Let $\tilde{T}_{1}:=\min\\{j\geq 1:N^{(\delta)}(R_{j})\geq 1\\}$ and for
$j\geq 2,$ let

$\tilde{T}_{j}:=\min\\{k\geq\tilde{T}_{j-1}+1:N^{(\delta)}(R_{k})\geq
1\\}-\tilde{T}_{j-1}.$

The random variables $\\{\tilde{T}_{i}\\}$ are nearly the same as
$\\{T^{(\delta)}_{i}\\}$ in the following sense: Suppose the event
$F_{\delta}$ occurs so that there is at least one node of ${\cal P}_{\delta}$
in the unit square. This means that $1\leq Q_{\delta}\leq\frac{n}{A^{2}}$ and
so $T^{(\delta)}_{1}=i_{1}-1=\tilde{T}_{1}-1,T^{(\delta)}_{j}=\tilde{T}_{j}$
for $2\leq j\leq Q_{\delta}$ and
$T^{(\delta)}_{Q_{\delta}+1}\leq\tilde{T}_{Q_{\delta}+1}.$ Consequently

$S_{\alpha}^{(\delta)}1{1}(F_{\delta})\leq\sum_{i=1}^{Q_{\delta}+1}\tilde{T}^{\alpha}_{i}1{1}(F_{\delta})\leq\sum_{i=1}^{\frac{n}{A^{2}}+1}\tilde{T}^{\alpha}_{i}1{1}(F_{\delta})\leq\sum_{i=1}^{\frac{n}{A^{2}}+1}\tilde{T}^{\alpha}_{i},$
(3.24)

since $Q_{\delta}\leq\frac{n}{A^{2}}.$

From (3.24), it suffices to estimate the sum on the right side to find an
upper bound for $S^{(\delta)}_{\alpha}.$ The advantage of (3.24) is that
$\\{\tilde{T}_{i}\\}$ are i.i.d. geometric random variables with success
parameter $p=1-e^{-A^{2}\delta}$ and so all moments of
$\tilde{T}_{i}^{\alpha}$ exist. Letting
$\beta_{i}=\left(\tilde{T}_{i}^{\alpha}-\mathbb{E}_{\delta}\tilde{T}_{i}^{\alpha}\right)$
and $\beta_{tot}=\sum_{i=1}^{\frac{n}{A^{2}}+1}\beta_{i}$ we obtain for an
even integer constant $m$ that

$\mathbb{E}_{\delta}\beta_{tot}^{m}=\mathbb{E}_{\delta}\sum_{(i_{1},\ldots,i_{m})}\beta_{i_{1}}\ldots\beta_{i_{m}}.$
(3.25)

For a tuple $(i_{1},\ldots,i_{m})$ let $\\{j_{1},\ldots,j_{w}\\}$ be the
distinct integers in $\\{i_{1},\ldots,i_{m}\\}$ with corresponding
multiplicities $l_{1},\ldots,l_{w}$ so that

$\mathbb{E}_{\delta}\beta_{i_{1}}\ldots\beta_{i_{m}}=\mathbb{E}_{\delta}\beta_{j_{1}}^{l_{1}}\ldots\beta_{j_{w}}^{l_{w}}=\prod_{k=1}^{w}\mathbb{E}_{\delta}\beta_{j_{k}}^{l_{k}}.$

If $l_{k}=1$ for some $1\leq k\leq w,$ then
$\mathbb{E}_{\delta}\beta_{i_{1}}\ldots\beta_{i_{m}}=0$ and so for any non
zero term in the summation in (3.25), there are at most $\frac{m}{2}$ distinct
terms in $\\{i_{1},\ldots,i_{m}\\}.$ This implies that

$\mathbb{E}_{\delta}\beta_{tot}^{m}\leq D(m){n\choose m/2}\leq D(m)n^{m/2}$

for some constant $D(m)>0.$ For $\epsilon>0$ we therefore get from Chebychev’s
inequality that

$\mathbb{P}_{\delta}\left(|\beta_{tot}|>\epsilon\left(\frac{n}{A^{2}}+1\right)\mathbb{E}_{\delta}\tilde{T}_{1}^{\alpha}\right)\leq
D_{1}\frac{\mathbb{E}_{\delta}(\beta_{tot}^{m})}{n^{m}\epsilon^{m}}\leq\frac{D_{2}}{n^{m/2}\epsilon^{m}}$

for some constants $D_{1},D_{2}>0.$ Setting $\epsilon=\frac{1}{n^{1/16}}$ and
using
$\epsilon\left(\frac{n}{A^{2}}+1\right)\leq\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}$
for all $n$ large, we then get

$\mathbb{P}_{\delta}\left(\sum_{i=1}^{\frac{n}{A^{2}}+1}\tilde{T}^{\alpha}_{i}\leq\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}\mathbb{E}\tilde{T}_{1}^{\alpha}\right)\geq
1-\frac{D_{2}}{n^{7m/16}}.$ (3.26)

From the upper bound for $S^{(\delta)}_{\alpha}$ in (3.24) and the fact that
there is at least one node of ${\cal P}_{\delta}$ in the unit square $S$ with
probability $1-e^{-\delta n}$ we further get

$\mathbb{P}_{\delta}\left(S^{(\delta)}_{\alpha}\leq\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}\mathbb{E}\tilde{T}_{1}^{\alpha}\right)\geq
1-\frac{D_{2}}{n^{7m/16}}-e^{-\delta n}\geq 1-\frac{2D_{2}}{n^{7m/16}}$

for all $n$ large. Using the coupling relation (3.23) we finally get (3.18)
proving Lemma 3.

##  4 Variance upper bound for the MST

In this section, we study variance upper bound estimates for MSTs with
location dependent edge weights. Recalling the distribution parameters
$\epsilon_{1},\epsilon_{2}$ (see (1.1)) and the edge weight distribution
parameters $c_{1},c_{2}$ (see (1.2), we have the following result regarding
the variance of $MST_{n}$ as defined in (1.3).

######  Theorem 4.

There is a constant
$D_{1}=D_{1}(\alpha,c_{1},c_{2},\epsilon_{1},\epsilon_{2})>0$ such that the
variance $var(MST_{n})\leq D_{1}n^{1-\alpha}$ for all $n$ large.

As before, we have that the variance upper bound in the location dependent
case is of the same order as that of the location independent case (Kesten and
Lee (1996)).

_Remarks_ : We derive the variance estimate in Theorem 4 using the standard
procedure (see Steele (1988), Kesten and Lee (1996)) of first obtaining one
node difference estimates and then using the martingale difference method.
Because of the large degree property described in Proposition 1, we use a
slightly different method in obtaining one node difference estimates in the
location dependent case. We explain this in more detail in the paragraph
following Lemma 5 below.

### One node difference estimates

As in (1.3), let $MST_{n+1}=W({\cal T}_{n+1})$ be the weight of the MST ${\cal
T}_{n+1}$ formed by the nodes $\\{X_{k}\\}_{1\leq k\leq n+1}$ and for $1\leq
j\leq n+1,$ let $MST_{n}(j)=W({\cal T}_{n}(j))$ be the weight of the MST
${\cal T}_{n}(j)$ formed by the nodes $\\{X_{k}\\}_{1\leq k\neq j\leq n+1}.$
We are interested in estimates for $|MST_{n+1}-MST_{n}(j)|,$ the change in the
weight of the MST upon adding or removing a single node.

Consider the MST ${\cal T}_{n}(j)$ with vertex set $\\{X_{i}\\}_{1\leq i\neq
j\leq n+1}$ and suppose $X_{i_{0}},$
$1\leq i_{0}\neq j\leq n+1$ is the node closest to $X_{j}$ in terms of the
Euclidean distance. The union ${\cal T}_{n}(j)\cup\\{(X_{j},X_{i_{0}})\\}$ is
a spanning tree containing all the nodes $\\{X_{k}\\}_{1\leq k\leq n+1}$ and
has weight $MST_{n}(j)+h^{\alpha}(X_{j},X_{i_{0}}).$ Therefore
$MST_{n+1}\leq MST_{n}(j)+h^{\alpha}(X_{j},X_{i_{0}})$ and using the bounds
for the weight function $h(.)$ in (1.2), we have

$h(X_{j},X_{i_{0}})\leq
c_{2}d(X_{j},X_{i_{0}})=c_{2}d\left(X_{j},\\{X_{k}\\}_{1\leq k\neq j\leq
n+1}\right),$

where $d(X_{j},\\{X_{k}\\}_{1\leq k\neq j\leq n+1})$ denotes the minimum
distance between $X_{j}$ and the rest of the nodes. Thus

$MST_{n+1}\leq
MST_{n}(j)+c_{2}^{\alpha}d^{\alpha}\left(X_{j},\\{X_{k}\\}_{1\leq k\neq j\leq
n+1}\right).$ (4.1)

For getting an estimate in the reverse direction, we let $d_{j}$ be the degree
of the node $X_{j}$ in the MST ${\cal T}_{n+1}$ and let ${\cal N}(X_{j},{\cal
T}_{n+1})=\\{v_{1},\ldots,v_{d_{j}}\\}$ be the set of neighbours of $X_{j}$ in
${\cal T}_{n+1}.$ We remove the node $X_{j}$ and add the edges
$(v_{i},v_{i+1}),1\leq i\leq d_{j}-1$ to get a spanning tree containing all
the nodes $\\{X_{k}\\}_{1\leq k\neq j\leq n+1}.$ Again using
$h(v_{i},v_{i+1})\leq c_{2}d(v_{i},v_{i+1})$ from (1.2), we get

$MST_{n}(j)\leq MST_{n+1}+\sum_{i=1}^{d_{j}-1}h^{\alpha}(v_{i},v_{i+1})\leq
MST_{n+1}+c_{2}^{\alpha}\sum_{i=1}^{d_{j}-1}d^{\alpha}(v_{i},v_{i+1})$ (4.2)

For $1\leq i\leq d_{j}-1,$ we have by triangle inequality that
$d(v_{i},v_{i+1})\leq d(X_{j},v_{i})+d(X_{j},v_{i+1})$ and so using
$(a+b)^{\alpha}\leq 2^{\alpha}(a^{\alpha}+b^{\alpha})$ for all $a,b,\alpha>0$
we get that $d^{\alpha}(v_{i},v_{i+1})\leq
2^{\alpha}\left(d^{\alpha}(X_{j},v_{i})+d^{\alpha}(X_{j},v_{i+1})\right).$
Using this estimate in (4.2), we get

$\displaystyle MST_{n}(j)$ $\displaystyle\leq$ $\displaystyle
MST_{n+1}+(2c_{2})^{\alpha}\sum_{i=1}^{d_{j}}d^{\alpha}(X_{j},v_{i})$ (4.3)
$\displaystyle=$ $\displaystyle MST_{n+1}+(2c_{2})^{\alpha}\sum_{v\in{\cal
N}(X_{j},{\cal T}_{n+1})}d^{\alpha}(X_{j},v).$

Summarizing we get from (4.1) and (4.3) that

$|MST_{n+1}-MST_{n}(j)|\leq f_{1}(X_{j})+f_{2}(X_{j}),$ (4.4)

where

$f_{1}(X_{j}):=c_{2}^{\alpha}d^{\alpha}\left(X_{j},\\{X_{k}\\}_{1\leq k\neq
j\leq n+1}\right)$

and

$f_{2}(X_{j}):=(2c_{2})^{\alpha}\sum_{v\in{\cal N}(X_{j},{\cal
T}_{n+1})}d^{\alpha}(X_{j},v).$ (4.5)

For future use, we prove the following Lemma.

######  Lemma 5.

There is a constant $D>0$ such that for all $n$ large and any $1\leq j\leq
n+1$ we have

$\displaystyle\left(\mathbb{E}f_{1}(X_{j})\right)^{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}f_{1}^{2}(X_{j})\leq\frac{D}{n^{\alpha}},$
$\displaystyle\sum_{j=1}^{n+1}\mathbb{E}f_{1}^{2}(X_{j})$ $\displaystyle=$
$\displaystyle(n+1)\mathbb{E}f_{1}^{2}(X_{1})\leq 2Dn^{1-\alpha},$ (4.6)
$\displaystyle f_{2}^{2}(X_{j})$ $\displaystyle\leq$ $\displaystyle
D\sum_{v\in{\cal N}(X_{j},{\cal T}_{n+1})}d^{2\alpha}(X_{j},v),$
$\displaystyle\sum_{j=1}^{n+1}\mathbb{E}f_{2}^{2}(X_{j})$ $\displaystyle=$
$\displaystyle(n+1)\mathbb{E}f_{2}^{2}(X_{1})\leq 2Dn^{1-\alpha}$ (4.7)

and

$\mathbb{E}|MST_{n+1}-MST_{n}|\leq\mathbb{E}f_{1}(X_{n})+\mathbb{E}f_{2}(X_{n})\leq\left(\frac{D}{\sqrt{n}}\right)^{\alpha}.$
(4.8)

The proof of (4.8) follows from (5) and (5). Estimate (5) is standard and does
not depend on the structure of the MST since it requires estimating the
minimum distance between $X_{j}$ and the rest of the nodes. In case the edge
weights are location independent, estimate (5) is true (see Kesten and Lee
(1996)) since the maximum degree of any node of MST is at most $6$ (see Aldous
and Steele (1992) for example) and so the first estimate in (5) follows from
the definition of $f_{2}$ in (4.5) and the identity
$\left(\sum_{i=1}^{6}a_{i}\right)^{2}\leq 6\sum_{i=1}^{6}a_{i}^{2}.$ The
second estimate in (5) then follows from the $\alpha-$invariance property of
MST (Kesten and Lee (1996)) which states that the MST remains the same
whatever the value of the edge weight exponent $\alpha.$ This invariance
property is also a consequence of the Kruskal’s construction of the minimum
spanning tree.

In our case where the edge weights are location dependent, we directly
estimate the sum $f_{2}(X_{j})$ by showing that the ratio of length of closely
spaced edges having a common vertex is bounded above by a constant strictly
less than one. Splitting the plane into sectors then allows us to estimate the
sum of weighted length of edges within each sector and then use the
$\alpha-$invariance property as described above to obtain (5) (see proof of
(5) below) .

For completeness we begin with the proof of (5).
_Proof of ( 5) in Lemma 5_: Letting
$d_{min}(X_{j})=d\left(X_{j},\\{X_{k}\\}_{1\leq k\neq j\leq n+1}\right)$ we
condition on $X_{j}~{}=~{}x$ and get from Fubini’s theorem that

$\mathbb{E}f_{1}^{2}(X_{j})=c_{2}^{2\alpha}\mathbb{E}d^{2\alpha}_{min}(X_{j})=c_{2}^{2\alpha}\int\mathbb{E}d^{2\alpha}_{min}(x)f(x)dx,$
(4.9)

where

$\mathbb{E}d^{2\alpha}_{min}(x)=2\alpha\int
y^{2\alpha-1}\mathbb{P}\left(d_{min}(x)>y\right)dy.$ (4.10)

The minimum distance from $x$ to $\\{X_{k}\\}_{1\leq k\neq j\leq n+1}$ is at
least $y$ if and only if $B(x,y)\cap S$ contains no node of
$\\{X_{k}\\}_{1\leq k\neq j\leq n+1},$ where $B(x,y)$ is the ball of radius
$y$ centred at $x$ and we recall that $S$ is the unit square. The area of
$B(x,y)\cap S$ is at least $\frac{\pi y^{2}}{4}$ no matter the location of $x$
and so using $f(x)\geq\epsilon_{1}$ from (1.1), we get

$\mathbb{P}(d_{min}(x)>y)=\left(1-\int_{B(x,y)\cap
S}f(x)dx\right)^{n}\leq\left(1-\frac{\epsilon_{1}\pi y^{2}}{4}\right)^{n}\leq
e^{-\frac{n\epsilon_{1}\pi y^{2}}{4}}.$

For integer $l\geq 0$ we therefore have that $\mathbb{P}(\sqrt{n}\cdot
d_{min}(x)>l)\leq e^{-C\cdot l^{2}}$ for some constant $C>0$ not depending on
$X.$ Thus

$\mathbb{E}\left(\sqrt{n}\cdot d_{min}(x)\right)^{\alpha}\leq\sum_{l\geq
0}\mathbb{P}\left(\sqrt{n}\cdot d_{min}(x)\geq
l^{\frac{1}{\alpha}}\right)\leq\sum_{l\geq 0}e^{-C\cdot
l^{\frac{2}{\alpha}}},$ (4.11)

where the final summation in (4.11) does not depend on $x.$ Substituting
(4.11) into (4.9) completes the proof of (5).

_Proof of ( 5) in Lemma 5_: To prove the first estimate in (5), we let $K$ be
a large integer satisfying

$\left(2-2\cos\left(\frac{2\pi}{K}\right)\right)^{\frac{1}{2}}<\frac{c_{1}}{c_{2}}<1,$

where $c_{1}$ and $c_{2}$ are the bounds for the weight function $h$ as in
(1.2). Defining

$g(x):=\left(1+x^{2}-2\cdot
x\cdot\cos\left(\frac{2\pi}{K}\right)\right)^{\frac{1}{2}},0\leq x\leq 1$

we have that $g(0)=1$ and since $g$ is continuous in $[0,1],$ there exists a
positive number $r_{0}<1$ such that $g(x)\geq\frac{c_{1}}{c_{2}}$ for $0<x\leq
r_{0}$ and $g(x)<\frac{c_{1}}{c_{2}}$ for
$r_{0}<x\leq 1.$

Draw $K$ rays starting from $X_{j}$ equally spaced at an angle of
$\frac{2\pi}{K}$ apart; i.e., let $l_{1},\ldots,l_{K}$ be $K$ rays starting
from $X_{j}$ encountered in the clockwise order such that the angle between
$l_{i}$ and $l_{i+1}$ is $\frac{2\pi}{K}.$ Let $v_{i_{1}},\ldots,v_{i_{w}}$ be
the neighbours of $X_{j}$ present in the $i^{th}$ sector formed by the rays
$l_{i}$ and $l_{i+1}$ and suppose that
$d(X_{j},v_{i_{1}})>d(X_{j},v_{i_{2}})>\ldots>d(X_{j},v_{i_{w}}).$ We first
show that the edge length ratio
$r:=\frac{d(X_{j},v_{i_{k+1}})}{d(X_{j},v_{i_{k}})}\leq r_{0}$ for $1\leq
k\leq w-1$ where $r_{0}$ is as in the previous paragraph.

If $\theta$ denotes the angle between the edges $(X_{j},v_{i_{k}})$ and
$(X_{j},v_{i_{k+1}}),$ then
$\theta<\frac{2\pi}{K}$ and so

$\displaystyle d^{2}(v_{i_{k}},v_{i_{k+1}})$ $\displaystyle=$ $\displaystyle
d^{2}(X_{j},v_{i_{k}})+d^{2}(X_{j},v_{i_{k+1}})-2d(X_{j},v_{i_{k}})\cdot
d(X_{j},v_{i_{k+1}})\cdot\cos(\theta)$ $\displaystyle=$ $\displaystyle
d^{2}(X_{j},v_{i_{k}})(1+r^{2}-2r\cos(\theta))$ $\displaystyle\leq$
$\displaystyle
d^{2}(X_{j},v_{i_{k}})\left(1+r^{2}-2r\cos\left(\frac{2\pi}{K}\right)\right).$

Thus $d(v_{i_{k}},v_{i_{k+1}})\leq d(X_{j},v_{i_{k}})g(r)$ and if $r_{0}<r\leq
1,$ then using (1.2) we have

$h(v_{i_{k}},v_{i_{k+1}})\leq c_{2}d(v_{i_{k}},v_{i_{k+1}})\leq
c_{2}d(X_{j},v_{i_{k}})g(r)<c_{1}d(X_{j},v_{i_{k}})\leq h(X_{j},v_{i_{k}}),$

by our choice of $r_{0}$ in the first paragraph. This is a contradiction
because removing the edge $(X_{j},v_{i_{k}})$ from the tree ${\cal T}_{n+1}$
and adding the edge $(v_{i_{k}},v_{i_{k+1}}),$ we get a spanning tree with
weight less than $MST_{n+1}.$

Using the ratio property iteratively, we get $d(X_{j},v_{i_{k}})\leq
r_{0}^{k-1}d(X_{j},v_{i_{1}})$ and so
$\sum_{k=1}^{w}d^{\alpha}(X_{j},v_{i_{k}})\leq Cd^{\alpha}(X_{j},v_{i_{1}}),$
where $C=\sum_{k\geq 1}r_{0}^{\alpha(k-1)}.$ This estimate holds for each of
the $K$ sectors and so

$\sum_{v\in{\cal N}_{n+1}(X_{j},{\cal
T}_{n+1})}d^{\alpha}(X_{j},v)\leq\sum_{i=1}^{K}\sum_{v}d^{\alpha}(X_{j},v)\leq
C\sum_{i=1}^{K}d^{\alpha}(X_{j},u_{i}),$

where the middle summation is over all nodes $v$ present in sector $i$ and
$u_{i}$ in the final summation is the node farthest in Euclidean distance from
$X_{j}$ in the $i^{th}$ sector. Therefore using $(\sum_{i=1}^{K}b_{i})^{2}\leq
K\sum_{i=1}^{K}b_{i}^{2}$ for positive numbers $\\{b_{i}\\}$ we get

$\displaystyle\left(\sum_{v\in{\cal N}_{n+1}(X_{j},{\cal
T}_{n+1})}d^{\alpha}(X_{j},v)\right)^{2}$ $\displaystyle\leq$ $\displaystyle
C^{2}\left(\sum_{i=1}^{K}d^{\alpha}(X_{j},u_{i})\right)^{2}$
$\displaystyle\leq$ $\displaystyle
C^{2}K\sum_{i=1}^{K}d^{2\alpha}(X_{j},u_{i})$ $\displaystyle\leq$
$\displaystyle C^{2}K\sum_{v\in{\cal N}_{n+1}(X_{j},{\cal
T}_{n+1})}d^{2\alpha}(X_{j},v),$

proving the first estimate in (5).

Consequently

$\displaystyle\sum_{j=1}^{n+1}\mathbb{E}f_{2}^{2}(X_{j})$ $\displaystyle\leq$
$\displaystyle C\mathbb{E}\sum_{j=1}^{n+1}\sum_{v\in{\cal N}(X_{j},{\cal
T}_{n+1})}d^{2\alpha}(X_{j},v)$ (4.12) $\displaystyle\leq$
$\displaystyle\frac{C}{c_{1}^{2\alpha}}\mathbb{E}\sum_{j=1}^{n+1}\sum_{v\in{\cal
N}(X_{j},{\cal T}_{n+1})}h^{2\alpha}(X_{j},v),$

again using (1.2). The double summation in the final term is simply twice the
weight of the MST with edge weight exponent $2\alpha.$ This is because, given
the location of the nodes $\\{X_{i}\\}_{1\leq i\leq n+1},$ the edge weights
$h(X_{i},X_{j})$ are fixed and so the Kruskal’s algorithm gives the same MST
irrespective of the value of the edge weight exponent $\alpha$ (Kesten and Lee
(1996), Yukich (2000)); i.e., if we denote ${\cal T}_{n+1}(\beta)$ to be the
MST for edge weight exponent $\beta>0$ as in (1.3) so that

$W({\cal T}_{n+1}(\beta))=\sum_{e\in{\cal
T}_{n+1}(\beta)}h^{\beta}(e)=\min_{\cal T}W({\cal T})=\min_{\cal
T}\sum_{f\in{\cal T}}h^{\beta}(f),$

where the minimum is taken over all spanning trees ${\cal T}$ containing all
the $n~{}+~{}1$ nodes $\\{X_{i}\\}_{1\leq i\leq n+1},$ then ${\cal
T}_{n+1}(\beta)={\cal T}_{n+1}(1)$ for any $\beta>0.$ Therefore using (4.12)
and the expectation upper bound (3.4) with $2\alpha$ instead of $\alpha,$ we
also get the second estimate in (5).

### Proof of Theorem 4

We use one node difference estimate (4.4) together with the martingale
difference method to obtain a bound for the variance. For $1\leq j\leq
n~{}+~{}1,$ let ${\cal F}_{j}=\sigma\left(\\{X_{k}\\}_{1\leq k\leq j}\right)$
denote the sigma field generated by the node positions $\\{X_{k}\\}_{1\leq
k\leq j}.$ Defining the martingale difference

$H_{j}=\mathbb{E}(MST_{n+1}|{\cal F}_{j})-\mathbb{E}(MST_{n+1}|{\cal
F}_{j-1}),$ (4.13)

we then have that $MST_{n+1}-\mathbb{E}MST_{n+1}=\sum_{j=1}^{n+1}H_{j}$ and so
by the martingale property

$var(MST_{n+1})=\mathbb{E}\left(\sum_{j=1}^{n+1}H_{j}\right)^{2}=\sum_{j=1}^{n+1}\mathbb{E}H_{j}^{2}.$
(4.14)

To evaluate $\mathbb{E}H_{j}^{2}$ we rewrite the martingale difference $H_{j}$
in a more convenient form. Letting $X^{\prime}_{j}$ be independent copy of
$X_{j}$ which is also independent of $\\{X_{k}\\}_{1\leq k\neq j\leq n+1}$ we
rewrite

$H_{j}=\mathbb{E}(MST_{n+1}(X_{j})-MST_{n+1}(X^{\prime}_{j})|{\cal F}_{j}),$
(4.15)

where $MST_{n+1}(X_{j})$ is the weight of the MST formed by the nodes
$\\{X_{i}\\}_{1\leq i\leq n+1}$ and $MST_{n+1}(X^{\prime}_{j})$ is the weight
of the MST formed by the nodes
$\\{X_{i}\\}_{1\leq i\neq j\leq n+1}~{}\cup~{}\\{X^{\prime}_{j}\\}.$ Using the
triangle inequality and the one node difference estimate (4.4), we have that
$|MST_{n+1}(X_{j})-MST_{n+1}(X^{\prime}_{j})|$ is bounded above as

$\displaystyle|MST_{n+1}(X_{j})-MST_{n}(j)|+|MST_{n+1}(X^{\prime}_{j})-MST_{n}(j)|$
$\displaystyle\;\;\;\leq\;\;f_{1}(X_{j})+f_{2}(X_{j})+f_{1}(X^{\prime}_{j})+f_{2}(X^{\prime}_{j}),$

where $f_{1}$ and $f_{2}$ are as in (4.4) and we recall that $MST_{n}(j)$ is
the weight of the MST formed by the nodes $\\{X_{k}\\}_{1\leq k\neq j\leq
n+1}.$ Thus

$\displaystyle|H_{j}|$ $\displaystyle\leq$
$\displaystyle\mathbb{E}(|MST_{n+1}(X_{j})-MST_{n+1}(X^{\prime}_{j})||{\cal
F}_{j})$ $\displaystyle\leq$ $\displaystyle\mathbb{E}(f_{1}(X_{j})|{\cal
F}_{j})+\mathbb{E}(f_{2}(X_{j})|{\cal
F}_{j})+\mathbb{E}(f_{1}(X^{\prime}_{j})|{\cal
F}_{j})+\mathbb{E}(f_{2}(X^{\prime}_{j})|{\cal F}_{j})$ $\displaystyle=$
$\displaystyle\mathbb{E}(f_{1}|{\cal F}_{j})+\mathbb{E}(f_{2}|{\cal
F}_{j})+\mathbb{E}(f_{1}|{\cal F}_{j-1})+\mathbb{E}(f_{2}|{\cal F}_{j-1}).$

Using $(a_{1}+a_{2}+a_{3}+a_{4})^{2}\leq
4(a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+a_{4}^{2}),$ we then get

$\displaystyle H_{j}^{2}$ $\displaystyle\leq$ $\displaystyle
4\left(\left(\mathbb{E}(f_{1}|{\cal
F}_{j})\right)^{2}+\left(\mathbb{E}(f_{2}|{\cal
F}_{j})\right)^{2}+\left(\mathbb{E}(f_{1}|{\cal
F}_{j-1})\right)^{2}+\left(\mathbb{E}(f_{2}|{\cal F}_{j-1})\right)^{2}\right)$
$\displaystyle\leq$ $\displaystyle 4\left(\mathbb{E}(f^{2}_{1}|{\cal
F}_{j})+\mathbb{E}(f^{2}_{2}|{\cal F}_{j})+\mathbb{E}(f^{2}_{1}|{\cal
F}_{j-1})+\mathbb{E}(f^{2}_{2}|{\cal F}_{j-1})\right)$

since $(\mathbb{E}(X|{\cal F}))^{2}\leq\mathbb{E}(X^{2}|{\cal F}).$ Thus
$\mathbb{E}H_{j}^{2}\leq
8\left(\mathbb{E}f_{1}^{2}(X_{j})+\mathbb{E}f_{2}^{2}(X_{j})\right)$ and
plugging this in (4.14), we have

$var(MST_{n+1})=\sum_{j=1}^{n+1}\mathbb{E}H_{j}^{2}\leq
8\left(\sum_{j=1}^{n+1}\mathbb{E}f_{1}^{2}(X_{j})+\sum_{j=1}^{n+1}\mathbb{E}f_{2}^{2}(X_{j})\right),$

which in turn is at most a constant multiple of $n^{1-\alpha}$ using the
estimates in (5) and (5).

##  5 Variance lower bound for MST

Regarding the variance lower bound for $MST_{n}$ as defined in (1.3), we have
the following result.

######  Theorem 6.

Suppose there is a square $S_{0}\subseteq S$ with constant side length $s_{0}$
such that the weight function $h(u,v)=d(u,v)$ if either $u$ or $v$ is in
$S_{0}.$ There is a constant
$D_{2}=D_{2}(\alpha,c_{1},c_{2},\epsilon_{1},\epsilon_{2})>0$ such that
$var(MST_{n})\geq D_{2}n^{1-\alpha}$ for all $n$ large.

Combining with Theorem 4, we then find that $var(MST_{n})$ is of the _order_
of $n^{1-\alpha}$ even in the location dependent case. As before, the
behaviour is analogous as in the location independent case and in this aspect
we refer to Kesten and Lee (1996) who use martingale methods to study central
limit theorems for $MST_{n},$ appropriately scaled and centred. The technical
assumption of weight function being equal to the Euclidean length in a small
subsquare within the unit square allows us to bound probabilities of
predetermined nice configurations via martingale difference estimates (see
proof of Theorem 6 below).

We begin with some preliminary definitions and computations. Suppose that
$s_{0}$ is the side length of the square $S_{0}.$ As in the proof of the
deviation estimates in Section 3, we divide $S_{0}$ into small
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ squares $\\{R_{i}\\}_{1\leq
i\leq\frac{s^{2}_{0}n}{A^{2}}}$ where
$A=A(n)\in\left[1,1+\frac{1}{\log{n}}\right]$ is chosen such that
$\frac{s_{0}\sqrt{n}}{A}$ is an integer. This is possible by the argument
preceding (3.11).

For a square $R_{i}$ we let ${\cal N}_{1}(R_{i})$ be the squares in
$\\{R_{k}\\}$ sharing a corner with $R_{i}$ and for $l\geq 2$ we let ${\cal
N}_{l}(R_{j})$ be the set of all squares in $\\{R_{k}\\}$ sharing a corner
with ${\cal N}_{l-1}(R_{j}).$ Thus ${\cal N}_{l}(R_{i})$ contains $(2l+1)^{2}$
of $\\{R_{k}\\}$ including the square $R_{i}.$ For an integer $g\geq 5,$ we
depict ${\cal N}_{3g}(R_{i})$ and ${\cal N}_{15g}(R_{i})$ in Figure 5 $(a)$ as
the $(6g+1)\times(6g+1)$ square and $(30g+1)\times(30g+1)$ square,
respectively. In all the figures in this subsection, the dimensions are to be
multiplied by the scaling factor $\frac{A}{\sqrt{n}}.$ The central square
labelled $E$ is the $\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ square
$R_{i}$ and the twelve $\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ squares
numbered $1,2,\ldots,12$ are all spaced $(2g-1)\frac{A}{\sqrt{n}}$ apart.

######  Definition 1.

For $1\leq j\leq n+1$ we say that the square $R_{i}$ is a $(g,j)-$_good
square_ if each of the $\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ squares
numbered one to twelve in Figure 5 $(a)$ contain exactly one node of
$\\{X_{k}\\}_{1\leq k\neq j\leq n+1}$ and the rest of the big square $ABCD$
(containing all the $\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ squares of
${\cal N}_{15}(R_{i})$) contains no node of $\\{X_{k}\\}_{1\leq k\neq j\leq
n+1}.$

(a)

(b)

Figure 5: $(a)$ The square $E$ is a $g-$good square. $(b)$ The edge $e$ has
longer Euclidean length than the edge $(v,v_{3}).$ All dimensions are to be
multiplied by $\frac{A}{\sqrt{n}}$ to get the actual length.

The advantage of defining the $(g,j)-$good square as above is that we can
determine exactly the change in the MST length when the node $X_{j}$ is
“added” to the $(g,j)-$good square $R_{i}.$ Indeed, suppose that$R_{i}$ is a
$(g,j)-$good square and the node $X_{j}\in R_{i}.$ For $1\leq l\leq 12,$ let
$v_{l}$ be the node present in the
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ square numbered $l$ in Figure 5
and let $v_{min}\in\\{v_{l}\\}_{1\leq l\leq 12}$ be the node closest to
$X_{j}$ in terms of Euclidean length. As before we denote ${\cal T}_{n}(j)$
and ${\cal T}_{n+1}$ to be the MSTs formed by the nodes $\\{X_{i}\\}_{1\leq
i\neq j\leq n+1}$ and $\\{X_{i}\\}_{1\leq i\leq n+1},$ respectively, with edge
weight function $h(.,.)$ and edge weight exponent $\alpha>0.$ Letting
$MST_{n}(j)$ denote the weight of ${\cal T}_{n}(j),$ we have the following
result.

######  Lemma 7.

If the event $\\{R_{i}\text{ is }(g,j)-\text{good}\\}\cap\\{X_{j}\in R_{i}\\}$
occurs then

${\cal T}_{n+1}={\cal T}_{n}(j)\cup\\{(X_{j},v_{min})\\}=:{\cal T}_{new}.$
(5.1)

and

$(3g-1)^{\alpha}\cdot\left(\frac{A}{\sqrt{n}}\right)^{\alpha}\leq
MST_{n+1}-MST_{n}(j)\leq(5g-1)^{\alpha}\cdot\left(\frac{A}{\sqrt{n}}\right)^{\alpha}.$
(5.2)

In words, the new MST ${\cal T}_{n+1}$ is simply obtained by adding the edge
$(X_{j},v_{min})$ to the old MST ${\cal T}_{n}(j).$ Estimate (5.2) obtains
explicit bounds on the difference of MST weight upon adding or removing the
node $X_{j}.$ This allows us to use martingale difference estimates and obtain
a lower bound on the variance in the proof of Theorem 6 below.

Before we do so, we state the following companion Lemma that shows that the
event mentioned in the statement of Lemma 7 occurs with positive probability.
For $1\leq j\leq n+1$ let $X^{\prime}_{j}$ be an independent copy of $X_{j}$
that is also independent of $\\{X_{k}\\}_{1\leq k\neq j\leq n+1}$ and let
$F_{j}(g)$ and $F^{\prime}_{j}(g)$ respectively denote the events that the
nodes $X_{j}$ and $X^{\prime}_{j}$ belong to a $(g,j)-$good square in
$\\{R_{k}\\}$ and let $F^{tot}_{j}(g)=F_{j}(2g)\cap F^{\prime}_{j}(g).$

######  Lemma 8.

For every $g\geq 5,$ there is a constant
$\theta=\theta(g,s_{0},\epsilon_{1},\epsilon_{2})>0$ such that

$\min_{1\leq j\leq n+1}\mathbb{P}(F^{tot}_{j}(g))\geq\theta.$

Assuming Lemmas 7 and 8, we prove Theorem 6 below. We then prove Lemmas 7 and
8 separately.

_Proof of Theorem 6 (assuming Lemmas 7 and 8)_: Letting $F^{tot}_{j}(g)$ be
the event defined prior to Lemma 8, we get from Lemma 7 that if
$F^{tot}_{j}(g)$ occurs, then

$\displaystyle MST_{n+1}(X_{j})$ $\displaystyle\geq$ $\displaystyle
MST_{n}(j)+\left(\frac{A}{\sqrt{n}}\right)^{\alpha}(6g-1)^{\alpha}$
$\displaystyle\geq$ $\displaystyle
MST_{n+1}(X^{\prime}_{j})+\left(\frac{A}{\sqrt{n}}\right)^{\alpha}((6g-1)^{\alpha}-(5g-1)^{\alpha})$

Letting $\Delta_{\alpha}:=(6g-1)^{\alpha}-(5g-1)^{\alpha}>0$ and recalling the
martingale difference $H_{j}$ in (4.15), we get

$\mathbb{E}|H_{j}|\geq\mathbb{E}|H_{j}|1{1}(F^{tot}_{j}(g))=\mathbb{E}H_{j}1{1}(F^{tot}_{j}(g))\geq\Delta_{\alpha}n^{-\frac{\alpha}{2}}\mathbb{P}(F^{tot}_{j}(g))\geq
c\Delta_{\alpha}n^{-\frac{\alpha}{2}},$

where $c>0$ is the constant in Lemma 8. Consequently from (4.14), we get

$var(MST_{n+1})=\sum_{j=1}^{n+1}\mathbb{E}H_{j}^{2}\geq\sum_{j=1}^{n+1}\left(\mathbb{E}|H_{j}|\right)^{2}\geq
c^{2}\Delta_{\alpha}^{2}n^{1-\alpha},$

proving the desired lower bound.

In the rest of this section, we prove Lemmas 7 and 8 starting with the former.

### Proof of Lemma 7

To prove Lemma 7, we denote the edges in $\\{(v_{i},v_{i+1})\\}_{1\leq i\leq
11}\cup\\{(v_{12},v_{1})\\}$ to be _short edges_ and collect the following
properties, assuming that the event defined in Lemma 7 holds.
$(p1)$ The length of any short edge is at most
$(2g+5)\cdot\frac{A}{\sqrt{n}}.$ The subgraph ${\cal T}_{loc}$ of ${\cal
T}_{n}(j)$ induced by the vertices $\\{v_{i}\\}_{1\leq i\leq 12}$ is a tree
consisting of exactly eleven short edges.
$(p2)$ Let $v$ be any point outside the square $ABCD$ as in Figure 5$(b)$ so
that the perpendicular $vZ$ from $v$ to the line containing $XY$ crosses the
line segment $XY.$ The Euclidean distance $d(X_{j},v)\geq
15g\cdot\frac{A}{\sqrt{n}}$ and $d(X_{j},v)>d(v,v_{3}),$ strictly.

_Proof of $(p1)$_: To prove that ${\cal T}_{loc}\subset{\cal T}_{n}(j)$ is a
tree we assume otherwise and suppose for example that nodes $v_{4}$ and
$v_{10}$ are joined by a path $P_{4,10}$ in ${\cal T}_{old}$ containing at
least one vertex not in $\\{v_{i}\\}_{1\leq i\leq 12}$ as in Figure 5$(a).$
This means that $P_{4,10}$ contains at least two “long” edges $f_{1},f_{2}$
containing endvertices outside ${\cal N}_{15g}(R_{u_{1}}).$

The short edges and the edges $\\{f_{1},f_{2}\\}$ all have an endvertex in the
square $S_{0}$ and so the weights of these edges are simply their Euclidean
lengths raised to the power $\alpha.$ The length of the edge $f_{1}$ is at
least $12g\cdot\frac{A}{\sqrt{n}},$ the width of the annulus between the big
squares (see Figure 5$(a)$) but the length of the edge $(v_{4},v_{10})$ is at
most $(6g+1)\sqrt{2}\cdot\frac{A}{\sqrt{n}}.$ Since $g\geq 2$ we have
$(6g+1)\sqrt{2}<10g$ and so removing the edge $f_{1}$ and adding the edge
$(v_{4},v_{10}),$ we get an MST formed by the nodes $\\{X_{i}\\}_{1\leq i\neq
j\leq n+1}$ with weight strictly that ${\cal T}_{n}(j),$ a contradiction. This
proves that ${\cal T}_{loc}$ is a tree and the edge set of ${\cal T}_{loc}$
must contain only short edges, since any other edge with both endvertices in
$\\{v_{i}\\}_{1\leq i\leq 12}$ has length strictly larger than longest short
edge.

_Proof of $(p2)$_: From Figure 5$(b),$ we have $d(X_{j},v)\geq
15g\cdot\frac{A}{\sqrt{n}}.$ We show below that the angle $\theta$ between the
edges $(X_{j},v)$ and $(v,v_{3})$ is less than $60$ degrees and so the
Euclidean length $d(X_{j},v)<d(v,v_{3}),$ strictly. To estimate $\theta$ we
let $d(v,Z)$ be the length of the perpendicular segment $vZ$ so that the area
of the triangle formed by the vertices $v,X$ and $Y$ is

$\frac{1}{2}\cdot d(v,Z)\cdot d(X,Y)=\frac{1}{2}d(v,X)\cdot
d(v,Y)\cdot\sin(\theta_{0}),$

where $\theta_{0}>\theta$ is the angle between the edges $(v,X)$ and $(v,Y).$
Thus $\sin(\theta_{0})=\frac{d(v,Z)\cdot d(X,Y)}{d(v,X)\cdot d(v,Y)}$ and
using $\min(d(v,X),d(v,Y))\geq d(v,Z)$ we further get
$\sin(\theta_{0})\leq\frac{d(X,Y)}{d(v,Z)}.$ But $d(v,Z)\geq
12g\cdot\frac{A}{\sqrt{n}}$ and from Figure 5$(a),$ we have
$d(X,Y)\leq(2g+1)\cdot\frac{A}{\sqrt{n}}$ and so
$\sin(\theta_{0})\leq\frac{2g+1}{12g}\leq\frac{1}{4},$ since $g\geq 1.$

_Proof of ( 5.1) in Lemma 7_: To prove (5.1), we first identify for every edge
$e=(u,v)\notin{\cal T}_{new},$ the unique path $P(e)\subseteq{\cal T}_{new}$
with endvertices $u,v.$ By Lemma $1$ of Kesten and Lee (1996), we then have
that ${\cal T}_{new}$ is the MST of the nodes $\\{X_{i}\\}_{1\leq i\leq n+1}$
if and only if for every edge $e\notin{\cal T}_{new}$ the following holds:

for every edge $f\in P(e),$ the weight $h(f)<h(e)$ (5.3)

where we recall that $h(e)=h(x,y)$ is the weight of the edge $e$ with
endvertices $x$ and $y.$ The condition (5.3) does not depend on the value of
the edge weight exponent $\alpha$ and as mentioned before, this obtains that
the MST is the same irrespective of the value of $\alpha.$

We now prove that (5.3) holds for each edge $e\notin{\cal T}_{new}.$ For
notational convenience, we refer to ${\cal T}_{n}(j)$ as ${\cal T}_{old}.$
Suppose first that $e=(u,v)\notin{\cal T}_{new}$ does not contain $X_{j}$ as
an endvertex. There is a unique path $P(u,v)\subseteq{\cal T}_{new}$ with
endvertices $u$ and $v$ and since $X_{j}$ is a leaf of ${\cal T}_{new},$ no
edge of $P(u,v)$ contains $X_{j}$ as an endvertex. Thus $P(u,v)\subseteq{\cal
T}_{old}$ and so applying (5.3) to the MST ${\cal T}_{old},$ we get that the
weight of every edge in $P(u,v)$ is no more than the weight of $e,$ proving
(5.3) for $e\in{\cal T}_{new}.$

Suppose now that $e=(v,X_{j})$ for some vertex $v$ as in Figure 5$(b).$ The
MST ${\cal T}_{old}$ does not contain both the edges $(v,v_{3})$ and
$(v,v_{4})$ since ${\cal T}_{old}$ has eleven of the twelve short edges
(property $(p1)$) and so if both $(v,v_{3})$ and $(v,v_{4})$ were to belong to
${\cal T}_{old},$ this would create a cycle. Suppose $(v,v_{3})\notin{\cal
T}_{old}$ so that there is a unique path $P(v,v_{3})\subseteq{\cal
T}_{old}\subset{\cal T}_{new}$ satisfying (5.3). Also let
$P(v_{3},v_{min})\subseteq{\cal T}_{old}\subset{\cal T}_{new}$ be the unique
path formed by the short edges with endvertices $(v_{3},v_{min})$ so that
$P(v,v_{3})\cup P(v_{3},v_{min})\cup\\{(v_{min},X_{j})\\}\subseteq{\cal
T}_{new}$ contains the unique path $P(v,X_{j})$ in ${\cal T}_{new}$ with
endvertices $v$ and $X_{j}.$

Applying (5.3) to the path $P(v,v_{3})\subseteq{\cal T}_{old}$ we have that
every edge in $P(v,v_{3})$ has weight less than

$h(v,v_{3})=d(v,v_{3})<d(v,X_{j})=h(v,X_{j})$ (5.4)

where the first and the last equalities in (5.4) follow from the fact that
$v_{3},X_{j}$ belong to the square $S_{0}.$ The middle inequality in (5.4) is
true by property $(p2).$ Also, every short edge has Euclidean length at most
$(2g+5)\cdot\frac{A}{\sqrt{n}}$ (property $(p1)$) and $d(v,X_{j})\geq
15g\cdot\frac{A}{\sqrt{n}}$ (property $(p2)$) and so the weight of every edge
in $P(v_{3},v_{min})$ is also less than the weight of $(X_{j},v).$ Finally,
the length of $(X_{j},v_{min})$ is at most the length of the diagonal of the
inner big square in Figure 5 $(a)$ and so
$h(X_{j},v_{min})=d(X_{j},v_{min})<(6g+1)\sqrt{2}\cdot\frac{A}{\sqrt{n}}<15g\cdot\frac{A}{\sqrt{n}}\leq
d(v,X_{j})=h(v,X_{j})$ by property $(p2).$ Thus the weight of
$(X_{j},v_{min})$ is also less than that of $(v,X_{j})$ and so (5.3) is true
for $e=(v,X_{j}).$

_Proof of ( 5.2) in Lemma 7_: From (5.1), we get that if the event mentioned
in the statement of the Lemma occurs, then the weight

$W({\cal
T}_{n+1})=MST_{n+1}=MST_{n}(j)+h^{\alpha}(X_{j},v_{min})=MST_{n}(j)+d^{\alpha}(X_{j},v_{min})$

since $X_{j}\in S_{0}.$ The vertex $v_{min}$ is necessarily one of the eight
vertices in
$\\{v_{i}\\}_{1\leq i\leq 12}\setminus\\{v_{1},v_{4},v_{7},v_{10}\\}.$ By
construction, the distance between any node within the square $R_{i}$
(labelled $E$ in Figure 5) and any node within the square labelled $3,$ for
example, is at least $(3g-1)\frac{A}{\sqrt{n}}$ and at most
$(5g-1)\frac{A}{\sqrt{n}}.$

### Proof of Lemma 8

For a constant $\theta>0$ let $E_{j}(g,\theta)$ be the event that the number
of $(g,j)-$good squares in $\\{R_{k}\\}$ is at least $\theta\cdot n.$
Recalling the node distribution parameters $\epsilon_{1}$ and $\epsilon_{2}$
from (1.1), we first show that there are positive constants
$\theta_{1}=\theta_{1}(g,s_{0},\epsilon_{1},\epsilon_{2})$ and
$\theta_{2}=\theta_{2}(g,s_{0},\epsilon_{1},\epsilon_{2})$ such that for any
$1\leq j\leq n+1,$

$\mathbb{P}\left(E_{j}(g,\theta_{1})\right)\geq 1-e^{-\theta_{2}n}.$ (5.5)

We then let

$\theta_{0}:=\min(\theta_{1}(2g,s_{0},\epsilon_{1},\epsilon_{2}),\theta_{1}(g,s_{0},\epsilon_{1},\epsilon_{2}))$
(5.6)

and define

$E_{tot}(j):=E_{j}(2g,\theta_{0})\cap F_{j}(2g)\cap E_{j}(g,\theta_{0})\cap
F^{\prime}_{j}(g),$

where we recall that $F_{j}(2g)$ denotes the event that the node $X_{j}$
belongs to a $(2g,j)-$good square in $\\{R_{i}\\}$ and an analogous definition
holds for $F^{\prime}_{j}(g)$ with the node $X^{\prime}_{j}.$ We show that
there exists a constant $D=D(g,s_{0},\epsilon_{1},\epsilon_{2})>0$ such that
for any $1\leq j\leq n+1$

$\mathbb{P}(E_{tot}(j))\geq D,$ (5.7)

completing the proof of Lemma 8.

We prove (5.5) and (5.7) in that order below.
_Proof of ( 5.5)_: We use Poissonization and let ${\cal P}$ be a Poisson
process of intensity $nf(.)$ in the unit square, with corresponding
probability measure $\mathbb{P}_{0}.$ Analogous to the definition of
$(g,j)-$good square, we define $R_{i}$ to be $g-$good square if the twelve
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ squares as in Figure 5$(a)$ each
contain exactly one node of ${\cal P}$ and the rest of big square of size
$\frac{(30g+1)A}{\sqrt{n}}\times\frac{(30g+1)A}{\sqrt{n}}$ is empty. The
number of nodes $N(R_{i})$ of ${\cal P}$ in the square $R_{i}$ is Poisson
distributed with mean
$n\int_{R_{i}}f(x)dx\in[\epsilon_{1}A^{2},\epsilon_{2}A^{2}]$ (see the bounds
for $f(.)$ in (1.1)) and so $\mathbb{P}_{0}(R_{i}\text{ is }g-\text{good})\geq
p_{0}$ for some constant $p_{0}=p_{0}(\epsilon_{1},\epsilon_{2},g)>0$ not
depending on $i.$

If $R_{i}$ and $R_{k}$ are two squares such that the corresponding
neighbourhoods ${\cal N}_{15g}(R_{i})\cap{\cal N}_{15g}(R_{k})=\emptyset,$
then the events $\\{R_{i}\text{ is }g-\text{good}\\}$ and $\\{R_{k}\text{ is
}g-\text{good}\\}$ are independent since the Poisson process is independent on
disjoint sets. We therefore pick a maximal set of squares
$\\{R_{l}\\}_{l\in{\cal Q}}$ whose
$15g-$neighbourhoods are empty. Since the area of the square $S_{0}$ is
$s_{0}^{2},$ a constant and ${\cal N}_{15}(R_{i})$ contains $(30g+1)^{2}$
squares in $\\{R_{l}\\},$ each of area $\frac{A^{2}}{n},$ we have that
$\\#{\cal
Q}\geq\frac{1}{2}\cdot\frac{s_{0}^{2}n}{A^{2}(30g+1)^{2}}\geq\frac{s_{0}^{2}n}{8(30g+1)^{2}}$
using $A\leq 1+\frac{1}{\log{n}}\leq 2.$

If $N_{good}:=\sum_{i\in{\cal Q}}1{1}(R_{i}\text{ is }g-\text{good})$ denotes
the number of $g-$good squares in the collection ${\cal Q},$ then $N_{good}$
is a sum of independent Bernoulli random variables, each with mean at least
$p_{0}.$ Therefore
$\mathbb{E}_{0}(N_{good})\geq\frac{s_{0}^{2}p_{0}n}{8(30g+1)^{2}}=:2\theta_{1}n$
and using the standard deviation estimate (7.2) (see Appendix) with
$m=\\#{\cal Q},\mu_{1}=p_{0}$ and $\epsilon=\frac{1}{2},$ we get

$\mathbb{P}_{0}\left(N_{good}\geq\theta_{1}n\right)\geq 1-e^{-2\theta_{2}n}$

for some positive constant
$\theta_{2}=\theta_{2}(g,s_{0},\epsilon_{1},\epsilon_{2}).$ Using the
dePoissonization formula (3.14), there exists a constant $D>0$ not depending
on $j$ such that

$\mathbb{P}(E_{j}(g,\theta_{1}))\geq 1-D\sqrt{n}\cdot e^{-2\theta_{2}n}\geq
1-e^{-\theta_{2}n}$

for all $n$ large.

_Proof of ( 5.7)_: We let ${\cal S}_{good}(2g)$ and ${\cal S}_{good}(g)$
respectively denote the random set of all $(2g,j)-$good squares and the random
set of all $(g,j)-$good squares in $\\{R_{i}\\}.$ If $E_{j}(2g,\theta_{0})\cap
E_{j}(g,\theta_{0})$ occurs where $\theta_{0}$ is as defined prior to (5.7),
then $\\#{\cal S}_{good}(2g)\geq\theta_{0}\cdot n$ and $\\#{\cal
S}_{good}(g)\geq\theta_{0}\cdot n.$ The event $E_{j}(2g,\theta_{0})\cap
E_{j}(g,\theta_{0})$ is independent of $X_{j}$ and $X^{\prime}_{j}$ and so

$\displaystyle\mathbb{P}(E_{tot}(j))$ $\displaystyle=$
$\displaystyle\sum_{{\cal S}_{1}:\\#{\cal S}_{1}\geq\theta_{0}n}\sum_{{\cal
S}_{2}:\\#{\cal S}_{2}\geq\theta_{0}n}\mathbb{P}\left(\\{X_{j}\in{\cal
S}_{1}\\}\cap\\{X^{\prime}_{j}\in{\cal S}_{2}\\}\right.$ (5.8)
$\displaystyle\;\;\;\;\;\left.\cap\\{{\cal S}_{good}(2g)={\cal
S}_{1}\\}\cap\\{{\cal S}_{good}(g)={\cal S}_{2}\\}\right)$ $\displaystyle=$
$\displaystyle\sum_{{\cal S}_{1}:\\#{\cal S}_{1}\geq\theta_{0}n}\sum_{{\cal
S}_{2}:\\#{\cal S}_{2}\geq\theta_{0}n}\mathbb{P}(X_{j}\in{\cal
S}_{1})\mathbb{P}(X^{\prime}_{j}\in{\cal S}_{2})$
$\displaystyle\;\;\;\;\;\mathbb{P}\left(\\{{\cal S}_{good}(2g)={\cal
S}_{1}\\}\cap\\{{\cal S}_{good}(g)={\cal S}_{2}\\}\right).$

For any collection ${\cal S}_{1}$ containing ${\cal S}_{1}\geq\theta_{0}n$
squares from $\\{R_{i}\\},$ we have that

$\mathbb{P}(X_{j}\in{\cal S}_{1})\geq\int_{{\cal
S}_{1}}f(x)dx\geq\epsilon_{1}\cdot\frac{A^{2}}{n}\cdot\theta_{0}n\geq\epsilon_{1}\theta_{0},$

since $A\geq 1.$ Similarly $\mathbb{P}(X^{\prime}_{j}\in{\cal
S}_{2})\geq\epsilon_{1}\theta_{0}$ and so from (5.8) we get that

$\displaystyle\mathbb{P}(E_{tot}(j))$ $\displaystyle\geq$
$\displaystyle(\epsilon_{1}\theta_{0})^{2}\sum_{{\cal S}_{1}:\\#{\cal
S}_{1}\geq\theta_{0}n}\sum_{{\cal S}_{2}:\\#{\cal
S}_{2}\geq\theta_{0}n}\mathbb{P}\left(\\{{\cal S}_{good}(2g)={\cal
S}_{1}\\}\cap\\{{\cal S}_{good}(g)={\cal S}_{2}\\}\right)$ $\displaystyle=$
$\displaystyle(\epsilon_{1}\theta_{0})^{2}\mathbb{P}\left(E_{j}(2g,\theta_{0})\cap
E_{j}(g,\theta_{0})\right)$ $\displaystyle\geq$
$\displaystyle(\epsilon_{1}\theta_{0})^{2}(1-e^{-n\cdot\theta_{2}(2g,s_{0},\epsilon_{1},\epsilon_{2})}-e^{-n\cdot\theta_{2}(g,s_{0},\epsilon_{1},\epsilon_{2})})$

using (5.5) and the definition of $\theta_{0}$ in (5.6).

##  6 Convergence properties for MST

In this section, we study convergence properties for the MST weight $MST_{n}$
as defined in (1.3), appropriately scaled and centred. The following is the
main result of this section.

######  Theorem 9.

For every $\alpha>0$ we have that

$\frac{1}{n^{1-\frac{\alpha}{2}}}(MST_{n}-\mathbb{E}MST_{n})\longrightarrow
0\text{ a.s.\ }$

as $n\rightarrow\infty.$

The proof is standard and follows from subsequence arguments (Steele (1988)).
For completeness we provide a proof below.

_Proof of Theorem 9_: We prove the almost sure convergence via a subsequence
argument using the variance upper bound for $MST_{n}$ obtained in Theorem 4.
Indeed, from Theorem 4 we have that

$var\left(\frac{MST_{n}}{n^{1-\frac{\alpha}{2}}}\right)\leq\frac{C}{n}$

and so an application of the Borel-Cantelli Lemma gives us that

$\frac{1}{n^{2-\alpha}}(MST_{n^{2}}-\mathbb{E}MST_{n^{2}})\longrightarrow
0\text{ a.s.\ }$

as $n\rightarrow\infty.$ To prove convergence along the subsequence $a_{n}=n,$
we let

$D_{n}:=\max_{n^{2}\leq k<(n+1)^{2}}\left|MST_{k}-MST_{n^{2}}\right|$ (6.1)

and show that $\mathbb{E}D^{2}_{n}\leq Cn^{2-2\alpha}$ for some constant
$C>0.$ This would then imply that
$\left(\frac{\mathbb{E}D_{n}}{n^{2-\alpha}}\right)^{2}\leq\frac{\mathbb{E}D^{2}_{n}}{n^{4-2\alpha}}\leq\frac{C}{n^{2}}\longrightarrow
0$ as $n\rightarrow\infty$ and we also get from Borel-Cantelli Lemma that
$\frac{D_{n}}{n^{2-\alpha}}\longrightarrow 0$ a.s. as $n\rightarrow\infty.$
For $n^{2}\leq k<(n+1)^{2}$ we then write

$\displaystyle\frac{|MST_{k}-\mathbb{E}MST_{k}|}{k^{1-\frac{\alpha}{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{|MST_{k}-MST_{n^{2}}|}{k^{1-\frac{\alpha}{2}}}+\frac{\mathbb{E}|MST_{k}-MST_{n^{2}}|}{k^{1-\frac{\alpha}{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{D_{n}}{k^{1-\frac{\alpha}{2}}}+\frac{\mathbb{E}D_{n}}{k^{1-\frac{\alpha}{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{D_{n}}{n^{2-\alpha}}+\frac{\mathbb{E}D_{n}}{n^{2-\alpha}}$

and get that
$\frac{MST_{k}-\mathbb{E}MST_{k}}{k^{1-\frac{\alpha}{2}}}\longrightarrow 0$
a.s. as $n\rightarrow\infty.$

To estimate $D_{n}$ we use the one node difference estimate (4.4) to get that
$|MST_{k+1}-MST_{k}|\leq f_{1,k}+f_{2,k}$ where $f_{1,k}$ and $f_{2,k}$ are
such that

$\left(\mathbb{E}f_{1,k}\right)^{2}\leq\mathbb{E}f^{2}_{1,k}\leq\frac{C}{k^{\alpha}}\text{
and
}\left(\mathbb{E}f_{2,k}\right)^{2}\leq\mathbb{E}f^{2}_{2,k}\leq\frac{C}{k^{\alpha}}$
(6.2)

for some constant $C>0$ (see (5) and (5)). Thus telescoping we get

$|MST_{k}-MST_{n^{2}}|\leq\sum_{l=n^{2}}^{k}f_{1,l}+f_{2,l}$

and so

$D_{n}=\max_{n^{2}\leq
k<(n+1)^{2}}|MST_{k}-MST_{n^{2}}|\leq\sum_{l=n^{2}}^{(n+1)^{2}}f_{1,l}+f_{2,l}.$

Using $(\sum_{i=1}^{t}a_{i})^{2}\leq t\sum_{i=1}^{t}a_{i}^{2}$ we get that
$\mathbb{E}D_{n}^{2}$ is bounded above by

$((n+1)^{2}-n^{2})\sum_{l=n^{2}}^{(n+1)^{2}}\mathbb{E}(f_{1,l}+f_{2,l})^{2}\leq
2((n+1)^{2}-n^{2})\sum_{l=n^{2}}^{(n+1)^{2}}(\mathbb{E}f^{2}_{1,l}+\mathbb{E}f^{2}_{2,l})$

and plugging the estimates from (6.2) we finally get

$\mathbb{E}D_{n}^{2}\leq
2((n+1)^{2}-n^{2})\sum_{l=n^{2}}^{(n+1)^{2}}\frac{2C}{l^{\alpha}}\leq
2((n+1)^{2}-n^{2})^{2}\frac{2C}{n^{2\alpha}}\leq 8Cn^{2-2\alpha},$ (6.3)

proving the desired estimate for $\mathbb{E}D_{n}^{2}.$

##  7 Uniform MSTs

In this Section, we assume that the nodes $\\{X_{i}\\}_{1\leq i\leq n}$ are
uniformly distributed in the unit square and obtain bounds on the asymptotic
values of the expected weight, appropriately scaled and centred. We assume
that the positive edge weight function
$h:\mathbb{R}^{2}\times\mathbb{R}^{2}\rightarrow\mathbb{R}$ satisfies (1.2)
along with the following two properties:
$(b1)$ For every $a>0$ we have

$h(au,av)=a\cdot h(u,v)\text{ for all }u,v\in\mathbb{R}^{2}$

$(b2)$ There exists a constant $h_{0}>0$ such that for all
$b\in\mathbb{R}^{2}$ we have

$h(b+u,b+v)\leq h_{0}\cdot h(u,v).$ (7.1)

For example, recalling that $d(u,v)$ denotes the Euclidean distance between
$u$ and $v,$ we have that the function

$h(u,v)=d(u,v)+\frac{1}{2}|d(u,0)-d(v,0)|$ (7.2)

is a metric since

$d(u,0)\leq d(0,v)+d(v,u)\text{ and }d(v,0)\leq d(0,u)+d(u,v)$

by triangle inequality and so

$d(u,v)\leq h(u,v)\leq d(u,v)+\frac{1}{2}d(u,v).$

This implies that $h(u,v)$ satisfies (1.2) and by definition $h$ also
satisfies $(b1).$ Moreover using the triangle inequality we have

$\displaystyle h(b+u,b+v)$ $\displaystyle=$ $\displaystyle
d(b+u,b+v)+\frac{1}{2}|d(u+b,0)-d(v+b,0)|$ $\displaystyle=$ $\displaystyle
d(u,v)+\frac{1}{2}|d(u+b,0)-d(v+b,0)|$ $\displaystyle\leq$ $\displaystyle
d(u,v)+\frac{1}{2}d(u+b,v+b)$ $\displaystyle=$ $\displaystyle
d(u,v)+\frac{1}{2}d(u,v)$ $\displaystyle\leq$ $\displaystyle\frac{3}{2}h(u,v)$

by definition of $h$ in (7.2). Thus $(b2)$ is also satisfied with
$h_{0}=\frac{3}{2}.$

We have the following result.

######  Theorem 10.

Suppose the distribution function $f(.)$ is uniform, i.e.,
$\epsilon_{1}=\epsilon_{2}=1$ in (1.1) and the edge weight function $h(u,v)$
satisfies (1.2) and properties $(b1)-(b2)$ above. We then have

$0<\liminf_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq\limsup_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq
h_{0}^{\alpha}\cdot\liminf_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}<\infty.$
(7.3)

Thus the scaled weight of the minimum spanning tree remains bounded within a
factor of $h_{0}^{\alpha}.$

We begin with the following Lemma.

######  Lemma 11.

There is a constant $D>0$ such that for any positive integers $n_{1},n_{2}\geq
1$ we have

$\displaystyle\mathbb{E}MST_{n_{1}+n_{2}}\leq\mathbb{E}MST_{n_{1}}+n_{2}\left(\frac{D}{n_{1}}\right)^{\frac{\alpha}{2}}.$
(7.4)

Moreover, for any fixed integer $m\geq 1$ we have

$\limsup_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq\limsup_{k}\frac{\mathbb{E}MST_{km}}{(km)^{1-\frac{\alpha}{2}}}.$
(7.5)

_Proof of ( 7.4) in Lemma 11_: Let ${\cal T}_{1}$ be the MST formed by the
$n_{1}$ nodes $\\{X_{i}\\}_{1\leq i\leq n_{1}}.$ We join each
$X_{i},n_{1}+1\leq i\leq n_{1}+n_{2}$ to the node in $\\{X_{j}\\}_{1\leq j\leq
n_{1}}$ closest to $X_{i}$ in Euclidean distance by an edge $e_{i},$ whose
length is $d^{\alpha}(X_{i},\\{X_{j}\\}_{1\leq j\leq n_{1}}),$ where we recall
that $d(X_{i},\\{X_{j}\\}_{1\leq j\leq n_{1}})$ is the minimum distance
between $X_{i}$ and the nodes in $\\{X_{j}\\}_{1\leq j\leq n_{1}}.$ From
(1.2), we have that the weight of $e_{i}$ is at most
$c_{2}^{\alpha}d^{\alpha}(X_{i},\\{X_{j}\\}_{1\leq j\leq n_{1}}).$

The tree ${\cal T}_{1}\cup\\{e_{i}\\}_{n_{1}+1\leq i\leq n_{1}+n_{2}}$
contains all the $n_{1}+n_{2}$ nodes and so we have

$\displaystyle\mathbb{E}MST_{n_{1}+n_{2}}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}MST_{n_{1}}+c_{2}^{\alpha}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}\mathbb{E}d^{\alpha}(X_{i},\\{X_{j}\\}_{1\leq
j\leq n_{1}})$ $\displaystyle=$ $\displaystyle\mathbb{E}MST_{n_{1}}+n_{2}\cdot
c_{2}^{\alpha}\cdot\mathbb{E}d^{\alpha}(X_{n_{1}+1},\\{X_{j}\\}_{1\leq j\leq
n_{1}}).$

From the estimate (5), we have that
$\mathbb{E}d^{\alpha}(X_{n_{1}+1},\\{X_{j}\\}_{1\leq j\leq
n_{1}})\leq\left(\frac{D_{1}}{n_{1}}\right)^{\frac{\alpha}{2}}$ for some
constant $D_{1}>0$ not depending on $n_{1}$ or $n_{2}$ and this proves (7.4).

_Proof of ( 7.5) in Lemma 11_: Fix an integer $m\geq 1$ and write $n=qm+s$
where $q=q(n)\geq 1$ and $0\leq s=s(n)\leq m-1$ are integers. As
$n\rightarrow\infty,$

$q(n)\longrightarrow\infty\text{ and }\frac{n}{q(n)}\longrightarrow m.$ (7.6)

Using property $(t1)$ with $n_{1}=qm$ and $n_{2}=s$ to get that

$\mathbb{E}MST_{n}=\mathbb{E}MST_{qm+s}\leq\mathbb{E}MST_{qm}+s\left(\frac{D}{qm}\right)^{\frac{\alpha}{2}}\leq\mathbb{E}MST_{qm}+m\left(\frac{D}{qm}\right)^{\frac{\alpha}{2}},$

since $s<m$ and so

$\limsup_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq\limsup_{n}\left(\frac{qm}{n}\right)^{1-\frac{\alpha}{2}}\frac{\mathbb{E}MST_{qm}}{(qm)^{1-\frac{\alpha}{2}}}+\limsup_{n}\frac{m}{n^{1-\frac{\alpha}{2}}}\left(\frac{D}{qm}\right)^{\frac{\alpha}{2}}.$
(7.7)

Since $\frac{n}{q(n)}\longrightarrow m,q(n)\longrightarrow\infty$ as
$n\rightarrow\infty,$ (see (7.6)) and $m$ is fixed, we have that

$\frac{m}{n^{1-\frac{\alpha}{2}}}\left(\frac{D}{qm}\right)^{\frac{\alpha}{2}}=\frac{m^{1-\frac{\alpha}{2}}D^{\frac{\alpha}{2}}}{n}\cdot\left(\frac{n}{q}\right)^{\frac{\alpha}{2}}\longrightarrow
0$

as $n\rightarrow\infty.$ Thus the second term in the right side of (7.7) is
zero and the first term in the right side of (7.7) equals
$\limsup_{n}\frac{\mathbb{E}MST_{qm}}{(qm)^{1-\frac{\alpha}{2}}}.$

But since $q(n)\geq\frac{n-m}{m}\geq\frac{l-m}{m}$ for $n\geq l,$ we have that

$\sup_{n\geq
l}\frac{\mathbb{E}MST_{qm}}{(qm)^{1-\frac{\alpha}{2}}}=\sup_{n\geq
l}\frac{\mathbb{E}MST_{q(n)m}}{(q(n)m)^{1-\frac{\alpha}{2}}}\leq\sup_{k\geq\frac{l-m}{m}}\frac{\mathbb{E}MST_{km}}{(km)^{1-\frac{\alpha}{2}}}$
(7.8)

and as $l\uparrow\infty,$ the final term in (7.8) converges to the second term
in (7.5).

If $\lambda:=\liminf_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}$ then
from (3.4), we have that $\lambda>0.$ We show below that for every
$\epsilon>0,$ there exists $m$ sufficiently large such that

$\limsup_{k}\frac{\mathbb{E}MST_{km}}{(km)^{1-\frac{\alpha}{2}}}\leq
h_{0}^{\alpha}\cdot\lambda+\epsilon,$ (7.9)

where $h_{0}$ is as in (7.1). Since $\epsilon>0$ is arbitrary, Theorem 10 then
follows from (7.9) and (7.5). To prove (7.9), let $k$ and $m$ be positive
integers and distribute $km$ nodes $\\{X_{i}\\}_{1\leq i\leq km}$
independently and uniformly in the unit square $S.$ Also divide $S$ into $k$
disjoint squares $\\{W_{j}\\}_{1\leq j\leq\frac{k}{A_{k}^{2}}}$ each of size
$\frac{A_{k}}{\sqrt{k}}\times\frac{A_{k}}{\sqrt{k}}$ where
$A_{k}\in\left[1,1+\frac{1}{\log{k}}\right]$ is such that
$\frac{\sqrt{k}}{A_{k}}$ is an integer for all large $k\geq K_{0},$ not
depending on $m.$ This is possible by an analogous argument as in (3.11).
Further, we label the squares $\\{W_{j}\\}$ as in Figure 4 so that the top
left most square is labelled $W_{1},$ the square below $W_{1}$ is $W_{2}$ and
so on.

For $1\leq j\leq\frac{k}{A_{k}^{2}},$ let $N(j)$ be the number of nodes of
$\\{X_{i}\\}_{1\leq i\leq km}$ present in the square $W_{j}$ and let ${\cal
T}(N(j))$ be the MST containing all the $N(j)$ nodes with corresponding length
$MST_{j}(N(j)).$ Also, for $1\leq j\leq\frac{k}{A_{k}^{2}}-1,$ we let
$j~{}+~{}T^{next}_{j}:=\min\\{i\geq j+1:W_{i}\text{ is not empty}\\}$ be the
next nonempty square after $W_{j}$ and let $e_{j}$ be the edge with one
endvertex in $W_{j}$ and the other endvertex in $W_{j+T^{next}_{j}},$ having
the smallest Euclidean length. We denote the Euclidean length of $e_{j}$ to be
$d(e_{j})$ and set $MST_{j}(N(j))=d(e_{j})=0$ if $W_{j}$ is empty. The union
$\cup_{1\leq j\leq\frac{k}{A_{k}^{2}}}{\cal T}(j)\cup\cup_{1\leq
j\leq\frac{k}{A_{k}^{2}}-1}\\{e_{j}\\}$ is a spanning tree containing all the
$km$ nodes and so

$\displaystyle
MST_{km}\leq\sum_{j=1}^{\frac{k}{A_{k}^{2}}}MST_{j}(N(j))+c_{2}^{\alpha}\sum_{j=1}^{\frac{k}{A_{k}^{2}}-1}d^{\alpha}(e_{j}),$
(7.10)

using (1.2). In Appendix, we use the translation property $(b2)$ to get that

$MST_{j}(N(j))\leq h_{0}^{\alpha}\cdot MST(N(j)),$

where $MST(N(j))$ is the MST weight of the configuration of nodes present in
$W_{j}$ with the centre of the square $W_{j}$ shifted to the origin: i.e., if
$u_{1},\ldots,u_{w}$ are the nodes of $\\{X_{i}\\}$ present in the square
$W_{j}$ whose centre is $s_{j},$ then $MST(N(j))$ is the MST weight of
complete graph formed by the nodes $u_{1}-s_{j},\ldots,u_{w}-s_{j}.$

Taking expectations we get

$\displaystyle\mathbb{E}MST_{km}$ $\displaystyle\leq$ $\displaystyle
h_{0}^{\alpha}\sum_{j=1}^{\frac{k}{A_{k}^{2}}}\mathbb{E}MST(N(j))+c_{2}^{\alpha}\cdot\frac{k}{A_{k}^{2}}\max_{1\leq
j\leq\frac{k}{A_{k}^{2}}-1}\mathbb{E}d^{\alpha}(e_{j})$ (7.11)
$\displaystyle=$ $\displaystyle
h_{0}^{\alpha}\cdot\frac{k}{A_{k}^{2}}\mathbb{E}MST(N(1))+c_{2}^{\alpha}\cdot\frac{k}{A_{k}^{2}}\max_{1\leq
j\leq\frac{k}{A_{k}^{2}}-1}\mathbb{E}d^{\alpha}(e_{j})$

and for convenience we write

$\mathbb{E}MST(N(1))=I_{1}+I_{2},$

where

$I_{1}=\mathbb{E}MST(N(1))1{1}(F_{1}),I_{2}=\mathbb{E}MST(N(1))1{1}(F_{1}^{c})$

and

$F_{1}:=\\{mA_{k}^{2}-\sqrt{m}\log{m}\leq N_{1}\leq
mA_{k}^{2}+\sqrt{m}\log{m}\\}$

to get

$\displaystyle\mathbb{E}MST_{km}\leq
h_{0}^{\alpha}\cdot\frac{k}{A_{k}^{2}}(I_{1}+I_{2})+c_{2}^{\alpha}\cdot\frac{k}{A_{k}^{2}}\max_{1\leq
j\leq\frac{k}{A_{k}^{2}}-1}\mathbb{E}d^{\alpha}(e_{j})$ (7.12)

The following Lemma estimates each sum in (7.12) starting with the second
term.

######  Lemma 12.

There are positive constants $D_{1},D_{2}$ not depending on $k$ or $m$ such
that

$\max_{1\leq j\leq\frac{k}{A_{k}^{2}}-1}\mathbb{E}d^{\alpha}(e_{j})\leq
D_{1}\left(\frac{A_{k}}{\sqrt{k}}\right)^{\alpha}\left(\left(\frac{\log{m}}{\sqrt{m}}\right)^{\alpha}+e^{-2\sqrt{m}\log{m}}\right),$
(7.13)
$I_{1}\leq\left(\frac{A_{k}}{\sqrt{k}}\right)^{\alpha}\left(\mathbb{E}MST_{m}+\frac{D_{1}\cdot
m^{1-\frac{\alpha}{2}}}{\log{k}}+D_{1}\cdot
m^{\frac{1-\alpha}{2}}(\log{m})\right)$ (7.14)

and

$I_{2}\leq D_{1}\left(\frac{A_{k}}{\sqrt{k}}\right)^{\alpha}\left(e^{-m\cdot
D_{2}}+m^{1-\frac{\alpha}{2}}\cdot\frac{1}{(\log{m})^{2}}\right).$ (7.15)

Substituting the estimates (7.13), (7.14) and (7.15) of Lemma 12 into (7.12),
we get that

$\mathbb{E}MST_{km}\leq
k^{1-\frac{\alpha}{2}}A_{k}^{\alpha-2}\left(h_{0}^{\alpha}\cdot\mathbb{E}MST_{m}+D_{1}\cdot
R_{m}(k)\right)$

where $R_{m}(k)$ equals

$\left(\frac{m^{1-\frac{\alpha}{2}}}{\log{k}}+m^{\frac{1-\alpha}{2}}(\log{m})\right)+\left(\frac{m^{1-\frac{\alpha}{2}}}{(\log{m})^{2}}+e^{-D_{2}\cdot
m}\right)+\left(\left(\frac{\log{m}}{\sqrt{m}}\right)^{\alpha}+e^{-\sqrt{m}\log{m}}\right).$

Using $1\leq A_{k}\leq 1+\frac{1}{\log{k}}\longrightarrow 1$ as
$k\rightarrow\infty$ and absorbing $e^{-D_{2}\cdot m}$ into
$e^{-\sqrt{m}\log{m}},$ we then get that

$\limsup_{k}\frac{\mathbb{E}MST_{km}}{(km)^{1-\frac{\alpha}{2}}}\leq
h_{0}^{\alpha}\cdot\frac{\mathbb{E}MST_{m}}{m^{1-\frac{\alpha}{2}}}+2D_{1}\cdot
R^{\prime}_{m}$ (7.16)

where

$R^{\prime}_{m}:=\frac{\log{m}}{\sqrt{m}}+\frac{1}{(\log{m})^{2}}+\frac{(\log{m})^{\alpha}}{m}+m^{\frac{\alpha}{2}-1}e^{-\sqrt{m}\log{m}}\leq\epsilon$

for any $\epsilon>0$ and all $m$ large. Letting $\\{m_{j}\\}$ be any sequence
such that
$\frac{\mathbb{E}MST_{m_{j}}}{m_{j}^{1-\frac{\alpha}{2}}}\longrightarrow\lambda=\liminf_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}$
and allowing $m\rightarrow\infty$ through the sequence $\\{m_{j}\\}$ we get
from (7.5), (7.16) and the above discussion that

$\limsup_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq
h_{0}^{\alpha}\cdot\lambda+2D_{1}\epsilon.$

Since $\epsilon>0$ is arbitrary, we get (7.9).

_Proof of ( 7.13) in Lemma 12_: We let $1\leq j\leq\frac{k}{A_{k}^{2}}-1$ and
suppose that the right edge of $W_{j}$ is the left edge of $W_{j+1}.$ Let $L$
be the largest integer less than or equal to $\sqrt{m}$ and for $1\leq i\leq
L$ let $W^{small}_{j}(i)$ and $W^{small}_{j+1}(i)$ be disjoint
$\frac{4A_{k}\log{m}}{\sqrt{km}}\times\frac{A_{k}}{\sqrt{km}}$ rectangles
contained in $W_{j}$ and $W_{j+1}$ respectively, and sharing a common edge as
shown in Figure 6. Here the two $a\times a$ squares represent $W_{j}$ and
$W_{j+1}$ with $a=\frac{A_{k}}{\sqrt{k}},b=\frac{A_{k}}{\sqrt{km}}$ and
$c=\frac{4A_{k}\log{m}}{\sqrt{km}}.$ The $c\times b$ rectangle labelled $i$
represents $W^{small}_{j}(i)$ for $1\leq i\leq L$ and represents
$W^{small}_{j+1}(i-L)$ for $L+1\leq i\leq 2L.$

Figure 6: Determining the length of the edge $e_{j}$ with one endvertex in the
left $a\times a$ square $W_{j}$ and other endvertex in right $a\times a$
square $W_{j+1}.$ Here $a=\frac{A_{k}}{\sqrt{k}},b=\frac{A_{k}}{\sqrt{km}}$
and $c=\frac{4A_{k}\log{m}}{\sqrt{km}}.$

Let $E_{nice}(j)$ be the event that there exists a pair of rectangles
$W^{small}_{j}(i)$ and $W^{small}_{j+1}(i)$ both of which contain at least one
of the nodes of $\\{X_{u}\\}_{1\leq u\leq km}.$ If $E_{nice}(j)$ occurs, then
the minimum length of an edge with one endvertex in $W_{j}$ and other
endvertex in $W_{j+1}$ is at most $2c+2b\leq
4c=\frac{16A_{k}\log{m}}{\sqrt{km}}.$ If $E_{nice}(j)$ does not occur, we use
the upper bound $d(e_{j})\leq\frac{2A_{k}T^{next}_{j}}{\sqrt{k}}$ and so

$d(e_{j})\leq\frac{16A_{k}\log{m}}{\sqrt{km}}1{1}(E_{nice}(j))+\frac{2A_{k}T^{next}_{j}}{\sqrt{k}}1{1}(E^{c}_{nice}(j)).$

Using $(a+b)^{\alpha}\leq 2^{\alpha}(a^{\alpha}+b^{\alpha})$ for all
$a,b,\alpha>0$ we therefore get that

$\mathbb{E}d^{\alpha}(e_{j})\leq\left(\frac{4A_{k}}{\sqrt{k}}\right)^{\alpha}\left(\left(\frac{8\log{m}}{\sqrt{m}}\right)^{\alpha}\mathbb{P}(E_{nice}(j))+\mathbb{E}\left(T^{next}_{j}\right)^{\alpha}1{1}(E^{c}_{nice}(j))\right).$
(7.17)

To estimate the second term within the brackets in (7.17), we first use
Cauchy-Schwarz inequality and write

$\mathbb{E}\left(T^{next}_{j}\right)^{\alpha}1{1}(E^{c}_{nice}(j))\leq\left(\mathbb{E}\left(T^{next}_{j}\right)^{2\alpha}\right)^{\frac{1}{2}}\left(\mathbb{P}(E_{nice}^{c}(j))\right)^{\frac{1}{2}}.$
(7.18)

For any $l\geq 1$ we have $T^{next}_{j}>l$ if and only if
$W_{j+1},\ldots,W_{j+l}$ are empty, which happens with probability
$(1-l\cdot\frac{A^{2}_{k}}{k})^{km}\leq e^{-lA_{k}m}\leq e^{-lm}$ since
$A_{k}\geq 1.$ Letting $\alpha_{0}$ be the smallest integer greater than or
equal to $\alpha$ we use the moment estimate (7.6) with $\theta=m\geq 1$ and
$r=2\alpha_{0}$ to get

$\mathbb{E}(T^{next}_{j})^{2\alpha}\leq\mathbb{E}(T^{next}_{j})^{2\alpha_{0}}\leq\frac{(2\alpha_{0})!}{(1-e^{-m})^{2\alpha_{0}}}\leq\frac{(2\alpha_{0})!}{(1-e^{-1})^{2\alpha_{0}}}.$
(7.19)

Next, if the event $E^{c}_{nice}(j)$ occurs, then in each pair
$\\{W^{small}_{j}(i),W^{small}_{j+1}(i)\\}$
$1\leq i\leq L$ at least one rectangle is empty. If there are $l\geq L$ such
empty rectangles in total, the area formed by these rectangles is
$l\frac{4A_{k}^{2}\log{m}}{km}$ and since there are $2L$ rectangles to choose
from, this happens with probability at most

${2L\choose
l}\left(1-l\cdot\frac{4A_{k}^{2}\log{m}}{km}\right)^{km}\leq(2L)^{l}e^{-4lA_{k}^{2}\log{m}}\leq(2L)^{l}e^{-4l\log{m}}$

since $A_{k}\geq 1.$ Using $L\leq\sqrt{m},$ we further have

$(2L)^{l}e^{-4l\log{m}}\leq(2\sqrt{m})^{l}e^{-4l\log{m}}\leq e^{-3l\log{m}}$

since $2\sqrt{m}e^{-4\log{m}}=\frac{2\sqrt{m}}{m^{4}}\leq\frac{1}{m^{3}}$ for
all $m\geq 4.$

Therefore

$\mathbb{P}(E^{c}_{nice}(j))\leq\sum_{l\geq L}e^{-3l\log{m}}\leq
De^{-3L\log{m}}\leq De^{-2\sqrt{m}\log{m}},$

for some constant $D>0$ not depending on $j,k$ or $m,$ since
$L\geq\frac{\sqrt{m}}{2}.$ Combining this and the estimate (7.19) for
$T^{next}_{j}$ from the previous paragraph, we have from (7.18) that
$\mathbb{E}\left(T^{next}_{j}\right)^{\alpha}1{1}(E^{c}_{dense}(j))\leq
D_{3}e^{-2\sqrt{m}\log{m}}$ for some constant $D_{3}>0$ not depending on $j,k$
or $m.$ Plugging this into (7.17), we get (7.13).

_Proof of ( 7.14) in Lemma 12_: We write

$I_{1}=\sum_{j=j_{low}}^{j_{up}}\mathbb{E}MST(N(1))1{1}(N(1)=j),$

where $j_{low}:=mA_{k}^{2}-\sqrt{m}\log{m}\leq
mA_{k}^{2}+\sqrt{m}\log{m}=:j_{up}.$ Given $N(1)=j,$ the nodes in $W_{1}$ are
independently and uniformly distributed in $W_{1}$ and we define
$\mathbb{E}MST\left(j;\frac{A_{k}}{\sqrt{k}}\right)$ to be the expected length
of the shifted MST of the $j$ nodes independently and uniformly distributed in
the $\frac{A_{k}}{\sqrt{k}}\times\frac{1}{k}$ square $W_{1}.$ From the scaling
relation (7.4) in Appendix we have that

$I_{1}=\sum_{j=j_{low}}^{j_{up}}\mathbb{E}MST\left(j;\frac{1}{k}\right)\mathbb{P}(N(1)=j)=\left(\frac{A_{k}}{\sqrt{k}}\right)^{\frac{\alpha}{2}}\sum_{j=j_{low}}^{j_{up}}\left(\mathbb{E}MST_{j}\right)\mathbb{P}(N(1)=j),$
(7.20)

by (7.4).

From the one node difference estimate (4.8), we have for $j_{low}\leq u\leq
j_{up}$ that
$\mathbb{E}|MST_{u+1}-MST_{u}|\leq\left(\frac{D}{u}\right)^{\frac{\alpha}{2}}$
for some constant $D>0$ not depending on $u,k$ or $m.$ Since $u\geq
j_{low}=mA_{k}^{2}-\sqrt{m}\log{m}\geq m-\sqrt{m}\log{m}$ using $A_{k}\geq 1$
we have for any $j_{low}\leq j_{1},j_{2}\leq j_{up}$ that
$\mathbb{E}|MST_{j_{2}}-MST_{j_{1}}|\leq\sum_{u=j_{low}}^{j_{up}-1}\mathbb{E}|MST_{u+1}-MST_{u}|$
is bounded above by

$\sum_{u=j_{low}}^{j_{up}-1}\left(\frac{D}{u}\right)^{\frac{\alpha}{2}}\leq(j_{up}-j_{low})\left(\frac{D_{1}}{m}\right)^{\frac{\alpha}{2}}\leq
D_{2}(\log{m})m^{\frac{1-\alpha}{2}},$ (7.21)

where $D_{1},D_{2}>0$ are constants not depending on $j_{1},j_{2},k$ or $m.$
Setting $j_{1}=mA_{k}^{2}$ and $j_{2}=j$ and using (7.21) we get $MST_{j}\leq
MST_{mA_{k}^{2}}+D_{2}m^{\frac{1-\alpha}{2}}(\log{m})$ for all $j_{low}\leq
j\leq j_{up}.$ From the expression for $I_{1}$ in (7.20) we therefore have
that

$I_{1}\leq\left(\frac{A_{k}}{\sqrt{k}}\right)^{\alpha}\left(\mathbb{E}MST_{mA_{k}^{2}}+D_{2}m^{\frac{1-\alpha}{2}}(\log{m})\right).$
(7.22)

Since $A_{k}\leq 1+\frac{1}{\log{k}},$ we have that
$mA_{k}^{2}-m\leq\frac{3m}{\log{k}}$ for all $k\geq 4$ and so using the
estimate (7.4) with $n_{1}=m,n_{2}=m(A_{k}^{2}-1)\leq\frac{3m}{\log{k}},$ we
get that
$\mathbb{E}MST_{mA_{k}^{2}}\leq\mathbb{E}MST_{m}+\frac{D_{3}m^{1-\frac{\alpha}{2}}}{\log{k}}$
for some constant $D_{3}>0$ not depending on $m$ or $k$ and this obtains
(7.14).

_Proof of ( 7.15) in Lemma 12_: There are $N(1)$ nodes in the square $W_{1}$
and given $N(1)=l,$ the $l$ nodes are uniformly distributed within $W_{1}$ and
so arguing as in the previous two paragraphs and using the scaling relation
(7.4) in Appendix, we have

$\displaystyle\mathbb{E}\left(MST(N(1))|N(1)=l\right)$ $\displaystyle=$
$\displaystyle\mathbb{E}MST\left(l;\frac{A_{k}}{\sqrt{k}}\right)$ (7.23)
$\displaystyle=$
$\displaystyle\left(\frac{A_{k}}{\sqrt{k}}\right)^{\alpha}\mathbb{E}MST_{l}$
$\displaystyle\leq$ $\displaystyle
D_{1}\left(\frac{A_{k}}{\sqrt{k}}\right)^{\alpha}\cdot l^{1-\frac{\alpha}{2}}$

for some constant $D_{1}>0$ using the expectation upper bound in (3.4). Thus

$\displaystyle\mathbb{E}MST(N(1))1{1}(N(1)=l)$ $\displaystyle=$
$\displaystyle\mathbb{E}(MST(N(1))|N(1)=l)\mathbb{P}(N(1)=l)$
$\displaystyle\leq$ $\displaystyle
D_{1}\left(\frac{A_{k}}{\sqrt{k}}\right)^{\alpha}\cdot
l^{1-\frac{\alpha}{2}}\mathbb{P}(N(1)=l)$

and consequently $I_{2}=\mathbb{E}MST(N(1))1{1}(F_{1}^{c})$ equals

$\displaystyle\sum_{l\leq mA_{k}^{2}-\sqrt{m}\log{m}}+\sum_{l\geq
mA_{k}^{2}+\sqrt{m}\log{m}}\mathbb{E}MST(N(1))1{1}(N(1)=l)$
$\displaystyle\leq\;\;\;\sum_{l\leq mA_{k}^{2}-\sqrt{m}\log{m}}+\sum_{l\geq
mA_{k}^{2}+\sqrt{m}\log{m}}D_{1}\left(\frac{A_{k}}{\sqrt{k}}\right)^{\alpha}\cdot
l^{1-\frac{\alpha}{2}}\mathbb{P}(N(1)=l)$
$\displaystyle=\;\;\;D_{1}\left(\frac{A_{k}}{\sqrt{k}}\right)^{\alpha}\mathbb{E}(N(1))^{1-\frac{\alpha}{2}}1{1}(F_{1}^{c}).$
(7.24)

Each node $X_{i},1\leq i\leq km$ has a probability $\frac{A^{2}_{k}}{k}$ of
being present in the $\frac{A_{k}}{\sqrt{k}}\times\frac{A_{k}}{\sqrt{k}}$
square $W_{1}.$ Therefore the number of nodes $N(1)$ in the square $W_{1}$ is
binomially distributed with

$m\leq\mathbb{E}N(1)=mA_{k}^{2}\leq 4m\;\;\text{ and }\;\;var(N(1))\leq
km\cdot\frac{A_{k}^{2}}{k}=mA_{k}^{2}\leq 4m,$ (7.25)

since $1\leq A_{k}\leq 1+\frac{1}{\log{k}}\leq 2.$ We recall from discussion
prior to (7.12) that $F_{1}^{c}=\\{N(1)\leq
mA_{k}^{2}-\sqrt{m}\log{m}\\}\cup\\{N(1)\geq mA_{k}^{2}+\sqrt{m}\log{m}\\}$
and so from Chebychev’s inequality we get that
$\mathbb{P}(F^{c}_{1})\leq\frac{var(N(1))}{(\sqrt{m}\log{m})^{2}}\leq\frac{4}{(\log{m})^{2}}.$
We show below that

$\mathbb{E}(N(1))^{1-\frac{\alpha}{2}}1{1}(F_{1}^{c})\leq
D_{2}e^{-D_{3}m}+m^{1-\frac{\alpha}{2}}\mathbb{P}(F_{1}^{c})\leq
D_{2}e^{-D_{3}m}+m^{1-\frac{\alpha}{2}}\frac{4}{(\log{m})^{2}}$ (7.26)

for some constants $D_{2},D_{3}$ not depending on $k$ or $m$ and substituting
(7.26) into (7.24), we then get (7.15).

To prove (7.26) we use $1\leq A_{k}\leq 2$ to get that

$\frac{m}{2}\leq mA_{k}^{2}-\sqrt{m}\log{m}\leq mA_{k}^{2}+\sqrt{m}\log{m}\leq
4m+\sqrt{m}\log{m}\leq 5m$

and so $1{1}(F_{1}^{c})\leq 1{1}(H_{1})+1{1}(H_{2})+1{1}(H_{3})+1{1}(H_{4}),$
where

$H_{1}:=\left\\{N(1)\leq\frac{m}{2}\right\\},H_{2}:=\left\\{\frac{m}{2}\leq
N(1)\leq mA_{k}^{2}-\sqrt{m}\log{m}\right\\},$
$H_{3}:=\left\\{mA_{k}^{2}+\sqrt{m}\log{m}\leq N(1)\leq 5m\right\\}\text{ and
}H_{4}:=\\{N(1)\geq 5m\\}.$

Using the bounds $m\leq\mathbb{E}N(1)\leq 4m$ from (7.25) and the standard
deviation estimates (7.1) and (7.2) in Appendix we have that
$\max\left(\mathbb{P}(H_{1}),\mathbb{P}(H_{4})\right)\leq e^{-2Dm}$ for some
constant $D>0$ not depending on $k$ or $m$ and so

$\mathbb{E}N(1)^{1-\frac{\alpha}{2}}1{1}(H_{1})\leq\mathbb{E}N(1)1{1}(H_{1})\leq\frac{m}{2}\mathbb{P}(H_{1})\leq
me^{-2Dm}.$ (7.27)

Using Cauchy-Schwarz inequality and the bound
$\mathbb{E}N^{2}(1)=var(N(1))+(\mathbb{E}N(1))^{2}\leq 4m+(4m)^{2}\leq
20m^{2}$ (see (7.25)) we also get

$\mathbb{E}N(1)^{1-\frac{\alpha}{2}}1{1}(H_{4})\leq\mathbb{E}N(1)1{1}(H_{4})\leq\left(\mathbb{E}N^{2}(1)\right)^{\frac{1}{2}}\left(\mathbb{P}(H_{4})\right)^{\frac{1}{2}}\leq
m\sqrt{20}e^{-Dm}.$ (7.28)

Finally, for the range of $N(1)$ in the events $H_{2}$ and $H_{3}$ we have

$\mathbb{E}N(1)^{1-\frac{\alpha}{2}}1{1}(H_{2}\cup H_{3})\leq
D_{1}m^{1-\frac{\alpha}{2}}\mathbb{P}(H_{2}\cup H_{3})$ (7.29)

for some constant $D_{1}>0$ not depending on $k$ or $m.$ Adding (7.27), (7.28)
and (7.29) and using the fact that $H_{2}\cup H_{3}\subseteq F_{1}^{c},$ we
get (7.26).

## Appendix : Miscellaneous results

### Standard deviation estimates

We use the following standard deviation estimates for sums of independent
Poisson and Bernoulli random variables (see Alon and Spencer (2008)).

######  Lemma 13.

Suppose $W_{i},1\leq i\leq m$ are independent Bernoulli random variables
satisfying
$\mu_{1}\leq\mathbb{P}(W_{1}=1)=1-\mathbb{P}(W_{1}~{}=~{}0)\leq\mu_{2}.$ For
any $0<\epsilon<\frac{1}{2},$

$\mathbb{P}\left(\sum_{i=1}^{m}W_{i}>m\mu_{2}(1+\epsilon)\right)\leq\exp\left(-\frac{\epsilon^{2}}{4}m\mu_{2}\right)$
(7.1)

and

$\mathbb{P}\left(\sum_{i=1}^{m}W_{i}<m\mu_{1}(1-\epsilon)\right)\leq\exp\left(-\frac{\epsilon^{2}}{4}m\mu_{1}\right)$
(7.2)

Estimates (7.1) and (7.2) also hold if $\\{W_{i}\\}$ are independent Poisson
random variables with $\mu_{1}\leq\mathbb{E}W_{1}\leq\mu_{2}.$

### Proof of the monotonicity property (3.23)

For $\alpha\leq 1$ we couple the original Poisson process ${\cal P}$ and the
homogenous process ${\cal P}_{\delta}$ in the following way. Let $V_{i},i\geq
1$ be i.i.d. random variables each with density $f(.)$ and let $N_{V}$ be a
Poisson random variable with mean $n,$ independent of $\\{V_{i}\\}.$ The nodes
$\\{V_{i}\\}_{1\leq i\leq N_{V}}$ form a Poisson process with intensity
$nf(.)$ which we denote as ${\cal P}$ and colour green.

Let $U_{i},i\geq 1$ be i.i.d. random variables each with density
$\epsilon_{2}-f(.)$ where $\epsilon_{2}\geq 1$ is as in (1.1) and let $N_{U}$
be a Poisson random variable with mean $n(\epsilon_{2}-1).$ The random
variables $(\\{U_{i}\\},N_{U})$ are independent of $(\\{V_{i}\\},N_{V})$ and
the nodes $\\{U_{i}\\}_{1\leq i\leq N_{U}}$ form a Poisson process with
intensity $n(\epsilon_{2}-f(.))$ which we denote as ${\cal P}_{ext}$ and
colour red. The nodes of ${\cal P}$ and ${\cal P}_{ext}$ together form a
homogenous Poisson process with intensity $n\epsilon_{2},$ which we denote as
${\cal P}_{\delta}$ and define it on the probability space
$(\Omega_{\delta},{\cal F}_{\delta},\mathbb{P}_{\delta}).$

Let $\omega_{\delta}\in\Omega_{\delta}$ be any configuration and as above let
$\\{i^{(\delta)}_{j}\\}_{1\leq j\leq Q_{\delta}}$ be the indices of the
squares in $\\{R_{j}\\}$ containing at least one node of ${\cal P}_{\delta}$
and let $\\{i_{j}\\}_{1\leq j\leq Q}$ be the indices of the squares in
$\\{R_{j}\\}$ containing at least one node of ${\cal P}.$ The indices in
$\\{i^{(\delta)}_{j}\\}$ and $\\{i_{j}\\}$ depend on $\omega_{\delta}.$
Defining $S_{\alpha}=S_{\alpha}(\omega_{\delta})$ and
$S^{(\delta)}_{\alpha}=S_{\alpha}^{(\delta)}(\omega_{\delta})$ as before, we
have that $S_{\alpha}$ is determined only by the green nodes of
$\omega_{\delta}$ while $S^{(\delta)}_{\alpha}$ is determined by both green
and red nodes of $\omega_{\delta}.$

From the monotonicity property, we therefore have that
$S_{\alpha}(\omega_{\delta})\leq S^{(\delta)}_{\alpha}(\omega_{\delta})$ and
so for any $x>0$ we have

$\mathbb{P}_{\delta}(S^{(\delta)}_{\alpha}<x)\leq\mathbb{P}_{\delta}(S_{\alpha}<x)=\mathbb{P}_{0}(S_{\alpha}<x),$
(7.3)

proving (3.23).

If $\alpha>1,$ we perform a slightly different analysis. Letting
$\epsilon_{1}\leq 1$ be as in (1.1), we construct a Poisson process ${\cal
P}_{ext}$ with intensity $n(f(.)-\epsilon_{1})$ and colour nodes of ${\cal
P}_{ext}$ red. Letting ${\cal P}_{\delta}$ be another independent Poisson
process with intensity $n\epsilon_{1},$ we colour nodes of ${\cal P}_{\delta}$
green. The superposition of ${\cal P}_{ext}$ and ${\cal P}_{\delta}$ is a
Poisson process with intensity $nf(.),$ which we define on the probability
space $(\Omega_{\delta},{\cal F}_{\delta},\mathbb{P}_{\delta}).$ In this case,
the sum $S_{\alpha}$ is determined by both green and red nodes while
$S^{(\delta)}_{\alpha}$ is determined only by the green nodes. Again using the
monotonicity property of $S_{\alpha},$ we get (7.3).

### Scaling and translation property of MSTs

For a set of nodes $\\{x_{1},\ldots,x_{n}\\}$ in the unit square $S,$ recall
from Section 1 that $K_{n}(x_{1},\ldots,x_{n})$ is the complete graph formed
by joining all the nodes by straight line segments and the edge
$(x_{i},x_{j})$ is assigned a weight of $h^{\alpha}(x_{i},x_{j}),$ where
$h(x_{i},x_{j})$ is the weight of the edge $(x_{i},x_{j})$ satisfying (1.2)
and properties $(b1)-(b2).$ We denote $MST(x_{1},\ldots,x_{n})$ to be the
length of the minimum spanning tree of $K_{n}(x_{1},\ldots,x_{n})$ with edge
weights obtained as in (1.3).

_Scaling_ : For any $a>0,$ consider the graph $K_{n}(ax_{1},\ldots,ax_{n}).$
Using the scaling property $(b1),$ the weight $h(ax_{1},ax_{2})$ of the edge
between the vertices $ax_{1}$ and $ax_{2}$ is simply $a\cdot h(x_{1},x_{2}),$
where $h(x_{1},x_{2})$ is the weight of the edge between $x_{1}$ and $x_{2}.$
Using the definition of MST in (1.3) we therefore have
$MST(ax_{1},\ldots,ax_{n})=a^{\alpha}MST(x_{1},\ldots,x_{n})$ and so if
$Y_{1},\ldots,Y_{n}$ are $n$ nodes uniformly distributed in the square $aS$ of
side length $a,$ then

$MST(n;a):=MST(Y_{1},\ldots,Y_{n})=a^{\alpha}MST(X_{1},\ldots,X_{n}),$

where $X_{i}=\frac{Y_{i}}{a},1\leq i\leq n$ are i.i.d. uniformly distributed
in $S.$ Recalling the notation $MST_{n}=MST(X_{1},\ldots,X_{n})$ from (1.3) we
therefore get

$\mathbb{E}MST(n;a)=a^{\alpha}\mathbb{E}MST_{n}.$ (7.4)

_Translation_ : For $b\in\mathbb{R}^{2}$ consider the graph
$K_{n}(x_{1}+b,\ldots,x_{n}+b).$ Using the translation property $(b2),$ the
weight $h(x_{1}+b,x_{2}+b)\leq h_{0}\cdot h(x_{1},x_{2}),$ the weight of the
edge between $x_{1}$ and $x_{2}.$ Using the definition of MST in (1.3) we
therefore have $MST(x_{1}+b,\ldots,x_{n}+b)\leq h_{0}^{\alpha}\cdot
MST(x_{1},\ldots,x_{n}).$

### Moments of random variables

Let $X\geq 1$ be any integer valued random variable such that

$\mathbb{P}(X\geq l)\leq e^{-\theta(l-1)}$ (7.5)

for all integers $l\geq 1$ and some constant $\theta>0$ not depending on $l.$
For every integer $r\geq 1,$

$\mathbb{E}X^{r}\leq r\sum_{l\geq 1}l^{r-1}\mathbb{P}(X\geq l)\leq
r\sum_{l\geq 1}l^{r-1}e^{-\theta(l-1)}\leq\frac{r!}{(1-e^{-\theta})^{r}}$
(7.6)

_Proof of ( 7.6)_: For $r\geq 1$ we have

$\mathbb{E}X^{r}=\sum_{l\geq 1}l^{r}\mathbb{P}(X=l)=\sum_{l\geq
1}l^{r}\mathbb{P}(X\geq l)-l^{r}\mathbb{P}(X\geq l+1)$ (7.7)

and substituting the $l^{r}$ in the final term of (7.7) with
$(l+1)^{r}-((l+1)^{r}-l^{r})$ we get

$\displaystyle\mathbb{E}X^{r}$ $\displaystyle=$ $\displaystyle\sum_{l\geq
1}\left(l^{r}\mathbb{P}(X\geq l)-(l+1)^{r}\mathbb{P}(X\geq l+1)\right)$ (7.8)
$\displaystyle\;\;\;\;\;\;\;\;+\;\;\;\sum_{l\geq
1}((l+1)^{r}-l^{r})\mathbb{P}(X\geq l+1)$ $\displaystyle=$ $\displaystyle
1+\sum_{l\geq 1}((l+1)^{r}-l^{r})\mathbb{P}(X\geq l+1)$ $\displaystyle=$
$\displaystyle\sum_{l\geq 0}((l+1)^{r}-l^{r})\mathbb{P}(X\geq l+1)$

where the second equality is true since $l^{r}\mathbb{P}(X\geq l)\leq
l^{r}e^{-\theta(l-1)}\longrightarrow 0$ as $l~{}\rightarrow~{}\infty.$ Using
$(l+1)^{r}-l^{r}\leq r\cdot(l+1)^{r-1}$ in (7.8), we get the first relation in
(7.6).

We prove the second relation in (7.6) by induction as follows. Let
$\gamma=e^{-\theta}<1$ and $J_{r}:=\sum_{l\geq 1}l^{r-1}\gamma^{l-1}$ so that

$J_{r+1}(1-\gamma)=\sum_{l\geq 1}l^{r}\gamma^{l-1}-\sum_{l\geq
1}l^{r}\gamma^{l}=\sum_{l\geq 1}\left(l^{r}-(l-1)^{r}\right)\gamma^{l-1}.$

Using $l^{r}-(l-1)^{r}\leq r\cdot l^{r-1}$ for $l\geq 1$ we therefore get that

$J_{r+1}(1-\gamma)\leq r\sum_{l\geq 1}l^{r-1}\gamma^{l-1}=rJ_{r}$

and so the second relation in (7.6) follows from induction.

### Acknowledgement

I thank Professors Rahul Roy, C. R. Subramanian and Federico Camia for crucial
comments that led to an improvement of the paper. I also thank Professors
Rahul Roy, C. R. Subramanian, Federico Camia and IMSc for my fellowships.

## References

  * [1] D. Aldous and J. M. Steele. (1992).  Asymptotics for Euclidean minimal spanning trees on random points.  Probability Theory and Related Fields, 92, pp. 247–258.
  * [2] N. Alon and J. Spencer. (2008).  The probabilisitic method.  Wiley Interscience.
  * [3] M. Bradonjic, R. Elsasser, T. Friedrich, T. Sauerwald and A. Stauffer. (2010).  Efficient Broadcast on Random Geometric Graphs.  SODA 2010, pp. 1412–1421.
  * [4] S. Chatterjee and S. Sen. (2017).  Minimal spanning trees and Stein’s method.  Annals Applied Probability, 27, pp. 1588–1645.
  * [5] T. Cormen, C. E. Leiserson, R. R. Rivest and C. Stein. (2009).  Introduction to Algorithms.  MIT Press and McGraw-Hill.
  * [6] M. Penrose and J. Yukich. (2003).  Weak laws of large numbers in geometric probability.  Annals of Applied Probability, 13, pp. 277–303.
  * [7] J. M. Steele. (1988).  Growth rates of Euclidean minimal spanning trees with power weighted edges.  Annals of Probability, 16, pp. 1767–1787.
  * [8] J. M. Steele. (1993).  Probability and Problems in Euclidean Combinatorial Optimization.  Statistical Science, 8, pp. 48–56.
  * [9] H. Kesten and S. Lee. (1996).  The central limit theorem for weighted minimal spanning trees on random points.  Annals of Applied Probability, 6, pp. 495–527.
  * [10] J. Yukich. (2000).  Asymptotics for weighted minimal spanning trees on random points.  Stochastic Processes and Applications, 85, pp. 123-138.