# On Minimum Spanning Trees for Random Euclidean Bipartite Graphs

Mario Correddu  M.C.: Dipartimento di Matematica, Università degli Studi di
Pisa, 56125 Pisa, Italy<EMAIL_ADDRESS>and  Dario Trevisan
D.T.: Dipartimento di Matematica, Università degli Studi di Pisa, 56125 Pisa,
Italy<EMAIL_ADDRESS>
###### Abstract.

We consider the minimum spanning tree problem on a weighted complete bipartite
graph $K_{n_{R},n_{B}}$ whose $n=n_{R}+n_{B}$ vertices are random, i.i.d.
uniformly distributed points in the unit cube in $d$ dimensions and edge
weights are the $p$-th power of their Euclidean distance, with $p>0$. In the
large $n$ limit with $n_{R}/n\to\alpha_{R}$ and $0<\alpha_{R}<1$, we show that
the maximum vertex degree of the tree grows logarithmically, in contrast with
the classical, non-bipartite, case, where a uniform bound holds depending on
$d$ only. Despite this difference, for $p<d$, we are able to prove that the
total edge costs normalized by the rate $n^{1-p/d}$ converge to a limiting
constant that can be represented as a series of integrals, thus extending a
classical result of Avram and Bertsimas to the bipartite case and confirming a
conjecture of Riva, Caracciolo and Malatesta.

###### Key words and phrases:

Euclidean functionals, minimum spanning tree, geometric probability

D.T. was partially supported by Gnampa project 2020 “Problemi di
ottimizzazione con vincoli via trasporto ottimo e incertezza”.

##  1\. Introduction

The minimum spanning tree (MST) problem ranks among the simplest Combinatorial
Optimization problems, with many applications, well beyond its historical
introduction for network design [1] including approximation algorithms for
more complex problems [2, 3] and cluster analysis [4].

Its formulation is straightforward: given a weighted undirected graph
$G=(V,E,w)$ with $w:E\to(0,\infty)$, find a sub-graph $T\subseteq E$ that
connects all nodes $V$ and has a minimal total edge cost

$\sum_{e\in T}w(e),$

thus defining the MST cost functional $\mathcal{C}_{MST}(G)$. Minimality
yields that redundant connections can be discarded, so that the resulting sub-
graph $T$ turns out to be a tree, i.e., connected and without cycles. Several
algorithms have been proposed for its solution, from classical greedy to more
efficient ones [5], possibly randomized [6].

Despite its apparent simplicity, a probabilistic analysis of the problem,
i.e., assuming that weights are random variables with a given joint law and
studying the resulting random costs and MST’s yields interesting results.
Moreover, it may suggest mathematical tools to deal with more complex
problems, such as the Steiner tree problem or the travelling salesperson
problem, where one searches instead for a cycle connecting all points having
minimum total edge weight.

The most investigated random model is surely that of i.i.d. weights with a
regular density, as first studied by Frieze [7], who showed in particular the
following law of large numbers: if $G^{n}=(V^{n},E^{n},w^{n})$, with
$(V^{n},E^{n})=K_{n}$ the complete graph over $n$ nodes and
$w^{n}=\left(w_{ij}\right)_{i,j=1}^{n}$ are independent and uniformly
distributed on $[0,1]$, then almost surely

$\lim_{n\to\infty}\mathcal{C}_{MST}(G^{n})=\zeta(3)=\sum_{k=1}^{\infty}\frac{1}{k^{3}}.$
(1.1)

Another well studied setting is provided by Euclidean models, where nodes are
i.i.d. sampled points in a region (say uniformly on a cube
$[0,1]^{d}\subseteq\mathbb{R}^{d}$, for simplicity) and edge weights are
functions of their distance, e.g. $w(x,y)=|x-y|^{p}$ for some parameter $p>0$.
This setting dates back at least to the seminal paper by Beardwood, Halton and
Hammersley [8] where they focused on the travelling salesperson problem, but
stated that other problems may be as well considered, including the MST one. A
full analysis was later performed by Steele [9] who proved that, if the
Euclidean graph consists of $n$ nodes, then for every $0<p<d$, almost sure
convergence holds

$\lim_{n\to\infty}\frac{\mathcal{C}_{MST}(G^{n})}{n^{1-p/d}}=\beta_{MST}(p,d),$
(1.2)

where $\beta_{MST}(p,d)\in(0,\infty)$ is a constant. The rate $n^{1-p/d}$ is
intuitively clear due to the fact that there are $n-1$ edges a tree over $n$
points and the typical distance between two adjacent points is expected to be
of order $n^{-1/d}$. The constraint $p<d$ was removed by Aldous and Steele
[10] and Yukich [11], so that convergence holds in fact for any $p>0$. This
result can be seen as an application of a general Euclidean additive
functional theory [12, 13]. However, such general methods that work for other
combinatorial optimization problems give not much insight on the precise value
of the limit constant $\beta_{MST}(p,d)$. The MST problem is known to be
exceptional, for a (sort of) explicit series representation, analogue to
(1.1), was obtained by Avram and Bertismas [14], although only in the range
$0<p<d$. The latter was used by Penrose [15], in connection with continuum
percolation, to study, among other things, the MST in the high dimensional
regime $d\to\infty$. An alternative approach towards explicit formulas was
proposed by Steele [16], but limited to the case of i.i.d. weights, based on
Tutte polynomials.

Aim of this paper is to investigate analogous results for _bipartite_
Euclidean random models, i.e., when nodes correspond to two distinct families
of sampled points (e.g., visually rendered by red/blue colourings) and
weights, still given by a power of the distance, are only defined between
points with different colours. Formally, we replace the underlying complete
graph $K_{n}$ with a complete bipartite graph $K_{n_{R},n_{B}}$ with
$n_{R}+n_{B}=n$.

A similar question was formulated and essentially solved in the model with
independent weights by Frieze and McDiarmid [17]. In Euclidean models,
however, it is known that such innocent looking variant may in fact cause
quantitative differences in the corresponding asymptotic results. For example,
in the Euclidean bipartite travelling salesperson problem with $d=1$ and
$d=2$, the correct asymptotic rates (for $p=1$) are known to be respectively
$\sqrt{n}$ [18] and $\sqrt{n\log n}$ [19], larger than the natural $n^{1-1/d}$
for the non-bipartite problem. Similar results are known for other problems,
such as the minimum matching problem [12] and its bipartite counterpart, also
related to the optimal transport problem [20, 21, 22, 23, 24]. Barthe and
Bordenave proposed a bipartite extension of the Euclidean additive functional
theory [25] that allows to recover an analogue of (1.2) for many relevant
combinatorial optimization problems on bipartite Euclidean random models,
although its range of applicability is restricted to $0<p<d/2$ (the cases
$p=1$, $d\in\left\\{1,2\right\\}$ are indeed outside this range) and anyway
the MST problem does not fit in the theory. The main reason for the latter
limitation is that there is no uniform bound on the maximum degree of a MST on
a bipartite Euclidean random graph – their theory instead applies to a variant
of the problem where a uniform bound on the maximum degree is imposed, which
is in fact algorithmically more complex (if the bound is two it recovers
essentially the travelling salesperson problem).

### Main results

Our first main result describes precisely the asymptotic maximum degree of a
MST on a bipartite Euclidean random graph, showing that it grows
logarithmically in the total number of nodes, in the asymptotic regime where a
fraction of points $\alpha_{R}\in(0,1)$ is red and the remaining
$\alpha_{B}=1-\alpha_{R}$ is blue.

######  Theorem 1.1.

Let $d\geq 1$, let $n\geq 1$ and $R^{n}=\left(X_{i}\right)_{i=1}^{n_{R}}$,
$B^{n}=\left(Y_{i}\right)_{i=1}^{n_{B}}$ be (jointly) i.i.d. uniformly
distributed on $[0,1]^{d}$ with $n_{R}+n_{B}=n$ and

$\lim_{n\to\infty}\frac{n_{R}}{n}=\alpha_{R}\in(0,1),\quad\lim_{n\to\infty}\frac{n_{B}}{n}=\alpha_{B}=1-\alpha_{R}.$

Let $T^{n}$ denote the MST over the complete bipartite graph with independent
sets $R^{n}$, $B^{n}$ and weights $w(X_{i},Y_{j})=|X_{i}-Y_{j}|$, and let
$\Delta(T^{n})$ denote its maximum vertex degree. Then, there exists a
constant $C=C(d,\alpha_{R})>0$ such that

$\lim_{n\to\infty}P\left(C^{-1}<\frac{\Delta(T^{n})}{\log(n)}<C\right)=1.$

(Indeed, the structure of the MST does not depend on the specific choice of
the exponent $p>0$, so we simply let $p=1$ above). The proof is detailed in
Section 3.

Our second main result shows that, although the general theory of Barthe and
Bordenave does not apply and the maximum degree indeed grows, the total weight
cost for the bipartite Euclidean MST problem turns out to be much closer to
the non-bipartite one, since no exceptional rates appear in low dimensions.
Before we give the complete statement, let us introduce the following
quantity, for $d\geq 1$, $k_{R}$, $k_{B}\geq 1$, $\alpha_{R}\in(0,1)$,

$\begin{split}E(k_{R},k_{B},\alpha_{R})=&\int_{\Theta(k_{R},k_{B})}\left(\alpha_{R}|D(\left\\{b_{j}\right\\}_{j=1}^{k_{B}})|+\alpha_{B}|D(\left\\{r_{i}\right\\}_{i=1}^{k_{R}})|\right)^{-(k_{R}+k_{B})/d}\cdot\\\
&\quad\cdot\left(\frac{k_{R}}{\alpha_{R}}\delta_{0}(r_{1})db_{1}+\frac{k_{B}}{\alpha_{B}}dr_{1}\delta_{0}(b_{1})\right)dr_{2}\ldots
dr_{k_{R}}db_{2}\ldots db_{k_{B}},\end{split}$

where $\alpha_{B}=1-\alpha_{R}$ and we write

$\Theta(k_{R},k_{B})\subseteq(\mathbb{R}^{d})^{k_{R}}\times(\mathbb{R}^{d})^{k_{B}},$
(1.3)

for the set of (ordered) points
$(\left(r_{i}\right)_{i=1}^{k_{R}},\left(b_{j}\right)_{j=1}^{k_{B}})$ such
that, in the associated Euclidean bipartite graph with weights
$\left(|r_{i}-b_{j}|\right)_{i,j}$, the subgraph with all edges having weight
less than $1$ is connected (or equivalently, there exists a bipartite
Euclidean spanning tree having all edges with length weight less than $1$),
and for a set $A\subseteq\mathbb{R}^{d}$, we write

$D(A)=\left\\{x\in\mathbb{R}^{d}\,:\,\operatorname{dist}(A,x)\leq 1\right\\},$
(1.4)

and $|D(A)|$ for its Lebesgue measure. Notice also that the overall
integration is performed with respect to Lebesgue measure over $k_{R}+k_{B}-1$
variables in $\mathbb{R}^{d}$ and one (either $r_{1}$ or $b_{1}$) is instead
with respect to a Dirac measure at $0$.

These quantities enter in the explicit formula for the limit constant in the
bipartite analogue of (1.2), as our second main result shows.

######  Theorem 1.2.

Let $d\geq 1$, let $n\geq 1$ and $R^{n}=\left(X_{i}\right)_{i=1}^{n_{R}}$,
$B^{n}=\left(Y_{i}\right)_{i=1}^{n_{B}}$ be (jointly) i.i.d. uniformly
distributed on $[0,1]^{d}$ with $n_{R}+n_{B}=n$ and

$\lim_{n\to\infty}\frac{n_{R}}{n}=\alpha_{R}\in(0,1),\quad\lim_{n\to\infty}\frac{n_{B}}{n}=\alpha_{B}=1-\alpha_{R}.$

Let $T^{n}$ denote the MST over the complete bipartite graph with independent
sets $R^{n}$, $B^{n}$ and weights $w(X_{i},Y_{j})=|X_{i}-Y_{j}|$. Then, for
every $p\in(0,d)$, the following convergence holds

$\lim_{n\to\infty}\frac{\mathbb{E}\left[\sum_{\left\\{X_{i},Y_{j}\right\\}\in
T^{n}}|X_{i}-Y_{j}|^{p}\right]}{n^{1-p/d}}=\beta_{bMST}(d,p),$ (1.5)

and the constant $\beta_{bMST}(d,p)\in(0,\infty)$ is given by the series

$\beta_{bMST}(d,p)=\frac{p}{d}\sum_{k_{R},k_{B}=1}^{\infty}\frac{\alpha_{R}^{k_{R}}}{k_{R}!}\frac{\alpha_{B}^{k_{B}}}{k_{B}!}\frac{\Gamma((k_{R}+k_{B})/d)}{k_{B}+k_{R}}E(k_{R},k_{B},\alpha_{R}).$
(1.6)

Moreover, if $p<d/2$ for $d\in\left\\{1,2\right\\}$ or $p<d$ for $d\geq 3$,
convergence is almost sure:

$\lim_{n\to\infty}\frac{\sum_{\left\\{X_{i},Y_{j}\right\\}\in
T^{n}}|X_{i}-Y_{j}|^{p}}{n^{1-p/d}}=\beta_{bMST}(d,p).$

The proof is detailed in Section 4. The one-dimensional random bipartite
Euclidean MST has been recently theoretically investigated in the statistical
physics literature by Riva, Caracciolo and Malatesta [26], together with
extensive numerical simulations also in higher dimensions, hinting at the
possibility of a non-exceptional rate $n^{1-p/d}$ also for $d=2$. In
particular, our result confirms this asymptotic rate in the two dimensional
case, with a.s. convergence if $p<1$ and just convergence of the expected
costs if $1\leq p<2$ – in fact we also have a general upper bound if $p\geq 2$
(Lemma 4.5).

### Further questions and conjectures

Several extensions of the results contained in this work may be devised, for
example by generalizing to $k$-partite models or more general block models,
allowing for weights between the same coloured points but possibly with a
different function, e.g. the same power of the distance function, but
multiplied by a different pre-factor according to pair of blocks. An
interesting question, also open for the non-bipartite case, is to extend the
series representation for the limiting constant to the case $p\geq d$. On the
other side, we suspect that additivity techniques may yield convergence in
(1.5) also in the range $p\geq d$, without an explicit series, but we leave it
for future explorations. A further question, that has no counterpart in the
non-bipartite case, is what happens if the laws of different coloured points
are different, say with densities $f_{R}$ and $f_{B}$ that are regular,
uniformly positive and bounded. Assuming that $n_{R}/n\to 1/2$, a natural
conjecture is that the limit holds with (1.6) obtained by replacing
$\alpha_{R}$ and $\alpha_{B}$ with the “local” fraction of points
$f_{R}(x)/2$, $f_{R}(x)/2$ and then integrating with respect to
$x\in[0,1]^{d}$, i.e.,

$\frac{p}{d}\sum_{k_{R},k_{B}=1}^{\infty}\frac{1}{2^{k_{R}+k_{B}}}\int_{[0,1]^{d}}\frac{f_{R}^{k_{R}}}{k_{R}!}\frac{f_{B}^{k_{B}}}{k_{B}!}\frac{\Gamma((k_{R}+k_{B})/d)}{k_{B}+k_{R}}E(k_{R},k_{B},f_{R}/2,f_{B}/2).$
(1.7)

Finally, a central limit theorem is known for MST problem [27, 28] and it may
be interesting to understand the possible role played by the additional
fluctuations introduced in bipartite setting for analogue results.

### Structure of the paper

In Section 2 we collect useful notation and properties of general MST’s,
together with crucial observations in the metric setting (including the
Euclidean one) and some useful probabilistic estimates. We try here to keep
separate as much as possible probabilistic from deterministic results, to
simplify the exposition. In Section 3 we prove Theorem 1.1 and in Section 4 we
first extend [14, Theorem 1] to the bipartite case and then apply it in the
Euclidean setting. An intermediate step requires to argue on the flat torus
$\mathbb{T}^{d}$ to exploit further homogeneity. We finally use a
concentration result to obtain almost sure convergence: since the vertex
degree is not uniformly bounded, the standard inequalities were not sufficient
to directly cover the case $p<1$, so we prove a simple variant of McDiarmid
inequality in Appendix A that we did not find in the literature and may be of
independent interest.

##  2\. Notation and preliminary results

###  2.1. Minimum spanning trees

Although our focus is on weighted graphs induced by points in the Euclidean
space $\mathbb{R}^{d}$, the following general definition of minimum spanning
trees will be useful.

######  Definition 2.1.

Given a weighted undirected finite graph $G=(V,E,w)$, with $w:E\to[0,\infty]$,
the MST cost functional is defined as

$\mathcal{C}_{MST}(G)=\inf\left\\{\sum_{e\in T}w(e)\,:\,\text{$T\subseteq E$
is a connected spanning subgraph}\right\\},$ (2.1)

Here and below, connected is in the sense that only edges with finite weight
must be considered. We consider only minimizers $T$ in (2.1) that are trees,
i.e., connected and acyclic, otherwise removing the most expensive edge in a
cycle would give a competitor with smaller cost (since we assume possibly null
weights, there may be other minimizers). The following lemma is a special case
of the cut property of minimum spanning trees, but will play a crucial role in
several occasions, so we state it here.

######  Lemma 2.2.

Let $G=(V,E,w)$, $v\in V$ and assume that
$e\in\operatorname{argmin}\left\\{w(f)\,:\,v\in f\right\\}$ is unique. Then,
$e$ belongs to every minimum spanning tree of $G$.

###### Proof.

Assume that $e$ does not belong to a minimum spanning tree $T$. Addition of
$e$ to $T$ induces a cycle that includes necessarily another edge $f$, with
$v\in f$ and by assumption $w(f)>w(e)$. By removing $f$, the cost of the
resulting connected graph is strictly smaller that the cost of $T$, a
contradiction. ∎

We write $\mathsf{n}_{G}(v)\in V$, or simply $\mathsf{n}(v)$ if there are no
ambiguities, for the closest node to $v$ in $G$, i.e.,

$e=\left\\{v,\mathsf{n}(v)\right\\}\in\operatorname{argmin}_{w\in
E}\left\\{w(f)\,:\,v\in f\right\\},$

assuming that such node is unique.

The subgraphs

$G(z):=\left\\{e\in E\,:\,w(e)\leq z\right\\},\quad\text{for $z\geq 0$,}$

are strongly related to the minimum spanning tree on $G$, since the execution
of Kruskal’s algorithm yields the identity, already observed in [14],

$\mathcal{C}_{MST}(G)=\int_{0}^{\infty}\left(C_{G(z)}-1\right)dz,$ (2.2)

where we write $C_{G}$ denotes the number of connected components of a graph
$G$. Indeed, the function $z\mapsto C_{G(z)}$ is piecewise constant and
decreasing from $|V|$ towards $1$ (assuming that all weights are strictly
positive and $G$ is connected). Assume for simplicity that all weights
$\left\\{w_{e}\right\\}_{e\in E}$ are different, so that $z\mapsto C_{G(z)}$
has only unit jumps, on a set $J_{-}$. An integration by parts gives the
identity

$\int_{0}^{\infty}\left(C_{G(z)}-1\right)dz=\sum_{z\in J_{-}}z.$

To argue that the right hand side is the cost of a MST, e.g., obtained by
Kruskal’s algorithm, we may represent the connected components of $G(z)$ as a
function of $z$ in a tree-like graph (see Fig. 1): starting with components
consisting of single nodes at $z=0$, whenever two components merge (i.e., at
values $z\in J_{-}$) we connect the corresponding segments. This yields a
(continuous) tree with leaves given by the nodes and a root at $z=\infty$.
Since Kruskal’s algorithm returns exactly the tree consisting of the edges
corresponding to such $z\in J_{-}$, we obtain (2.2).

######  Remark 2.3.

The construction above also yields that the minimum spanning trees of
$G=(V,E,w)$ are also minimum spanning trees associated to the graph
$G^{\psi}=(V,E,\psi\circ w)$, i.e., weights are $\psi(w(e))$ where $\psi$ is
an increasing function. In particular, assuming that $\psi:[0,\infty)$ is
strictly increasing with $\psi(0)=0$, then $G^{\psi}(z)=G(\psi^{-1}(z))$,
hence

$\mathcal{C}_{MST}(G^{\psi})=\int_{0}^{\infty}\left(C_{G^{\psi}(z)}-1\right)dz=\int_{0}^{\infty}\left(C_{G(u)}-1\right)d\psi(u).$

In particular, choosing $\psi(x)=x^{p}$ and letting $p\to\infty$, we obtain
that any minimum spanning tree $T$ is also a minimum bottleneck spanning tree,
i.e., $T$ minimizes the functional

$\mathcal{C}_{MST}^{\infty}(G):=\inf\left\\{\max_{e\in
T}w(e)\,:\,\text{$T\subseteq E$ is a connected spanning subgraph}\right\\}.$
(2.3)

A similar argument [14, Lemma 4] yields an upper bound for a similar quantity
where $C_{G}$ is replaced with $C_{k,G}$, the number of connected components
having at least $k$ nodes.

######  Lemma 2.4.

Let $G=(V,E,w)$ be connected with all distinct weights $(w(e))_{e\in E}$ (if
finite) and $2\leq k\leq|V|$. Then, there exists a partition
$V=\bigcup_{i=1}^{m}C_{i}$ such that letting $G_{k}$ be the graph over the
node set $\left\\{C_{1},\ldots,C_{m}\right\\}$ with weights

$w(C_{i},C_{j})=\inf\left\\{w(e)\,:\,e=\left\\{x,y\right\\}\in V,x\in
C_{i},y\in C_{j}\right\\},\quad\text{for $i$,
$j\in\left\\{1,\ldots,m\right\\}$,}$

then

$\int_{0}^{\infty}(C_{k,G(z)}-1)dz\leq\mathcal{C}_{MST}(G_{k}).$ (2.4)

Moreover, for every $i=1,\ldots,m$, $|C_{i}|\geq k$, hence $m\leq|V|/k$, and
there exists $v\in C_{i}$ such that $\mathsf{n}_{G}(v)\in C_{i}$ and
$\mathsf{n}_{G}(\mathsf{n}_{G}(v))=v$.

###### Proof.

The function $z\mapsto C_{k,G(z)}$ is piecewise constant, with jumps of
absolute size $1$, with positive sign on a set $J_{+}$ and negative sign on a
set $J_{-}$. An integration by parts gives

$\int_{0}^{\infty}\left(C_{k,G(z)}(z)-1\right)dz=\sum_{z\in J_{-}}z-\sum_{z\in
J_{+}}z\leq\sum_{z\in J_{-}}z.$

We interpret the right hand side above as $\mathcal{C}_{MST}(G_{k})$ for a
suitable graph $G_{k}$. To define the sets $C_{i}$, we let
$J_{+}=\left\\{z_{1},\ldots,z_{m}\right\\}$ and define, for every $z_{i}$, the
“seed” of $C_{i}$ as the set of nodes that gives an additional component with
at least $k$ nodes, i.e., obtained by merging two components in
$G(z_{i}^{-})$, both having less that $k$ nodes. Notice that, since $C_{i}$
will be then completed by adding nodes to such seeds, the last statement is
already fulfilled. Indeed, any seed contains at least $k$ nodes we can always
choose $v_{1}$, $v_{2}$ in a seed such that the paths from $v_{1}$, $v_{2}$
merge first (among those from other nodes in the same seed). This gives that
$v_{2}=\mathsf{n}_{G}(v_{1})$ and $v_{2}=\mathsf{n}_{G}(v_{1})$.

$z$$V$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1$$2$$5$$6$$3$$4$$6$$7$$9$$7$$8$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$
Figure 1. A weighted graph $G$ and its tree-like representation of the
connected components of $G(z)$. Black dots correspond to seeds for the
construction of $C_{i}$’s with $k=3$. Notice that regardless whether the node
$7$ is added to $\left\\{1,2,3\right\\}$ or $\left\\{4,5,6\right\\}$, the
resulting (different) trees have always total weight $5+9=14$.

To completely determine every $C_{i}$, it is simpler to argue graphically on
the the tree-like representation (Fig. 1), where we highlight the “birth” of
$C_{i}$ at $z_{i}\in J_{-}$ by thickening the shortest path from the seed
towards the root at $z=\infty$. At every $z$ such that two thick paths merge,
the corresponding two connected components with at least $k$ elements become
one, hence $C_{k,G(z)}$ jumps downwards, i.e., $z\in J_{-}$. For $v\in V$, to
determine the set $C_{i}$ such that $v$ belongs, consider the shortest path
towards from the trivial component containing only $v$ at $z=0$ towards the
root at $z=\infty$ in the tree-like representation. Let $z_{v}$ be the
smallest value such that such path merges with a thick one (the case that
$z_{v}\in J_{+}$ and $v$ becomes part of a seed is trivial). We then add to a
single $C_{i}$, among those further from the root on such thick line, all the
connected component to which $v$ belongs in $G(z_{v}^{-})$. In fact, a precise
choice is not relevant to the thesis, so we simply add it to the $C_{i}$ with
smallest $i$ (other choices may give more desirable properties, but we do not
need them for our purposes).

To prove (2.4) it is sufficient to realize that the graphical representation
of Kruskal’s algorithm on the graph $G_{k}$ gives exactly the thickened tree.
∎

###  2.2. Metric MST problem

If $(X,\mathsf{d})$ is a metric space and $V\subseteq X$, then a natural
choice for a weight is $w(\left\\{x,y\right\\})=\mathsf{d}(x,y)^{p}$, where
$p>0$ is fixed. If $V$, $R$, $B\subseteq X$, are finite sets and $p>0$, we
write

$\mathcal{C}_{MST}^{p}(V)\quad\text{and
respectively}\quad\mathcal{C}_{MST}^{p}(R,B),$

for the the MST cost functional on the complete graph on $V$ (and
respectively, on the complete bipartite graph with independent sets $R$, $B$)
and edge weights $w(\left\\{x,y\right\\})=\mathsf{d}(x,y)^{p}$, for
$\left\\{x,y\right\\}\in E$. Notice that, by Remark 2.3, the MST does not in
fact depend on the choice of $p$, and moreover we may let $p\to\infty$ and
obtain

$\left(\mathcal{C}_{MST}^{p}(V)\right)^{1/p}\to\mathcal{C}_{MST}^{\infty}(V),\quad\left(\mathcal{C}_{MST}^{p}(R,B)\right)^{1/p}\to\mathcal{C}_{MST}^{\infty}(R,B),$

where $\mathcal{C}_{MST}^{\infty}$ is the minimum bottleneck spanning tree
cost defined in (2.3) with edge weight given by the distance.

We denote by

$\mathsf{d}(V,x)=\inf_{v\in V}\mathsf{d}(v,x)$

and

$\mathsf{d}(R,B)=\sup\left\\{\sup_{r\in R}\inf_{b\in
B}\mathsf{d}(r,b),\sup_{b\in B}\inf_{r\in R}\mathsf{d}(r,b)\right\\}$

respectively the distance function from $V$ and the Hausdorff distance between
$R$ and $B$. Clearly, $\mathcal{C}_{MST}^{p}(R\cup
B)\leq\mathcal{C}_{MST}^{p}(R,B)$. The following lemma provides a sort of
converse inequality.

######  Lemma 2.5.

Let $p>0$. There exists a constant $C=C(p)>0$ such that, for finite sets $R$,
$B\subseteq X$,

$\mathcal{C}_{MST}^{p}(R,B)\leq C\left(\mathcal{C}_{MST}^{p}(R)+\sum_{r\in
R}\mathsf{d}(B,r)^{p}+\sum_{b\in B}\mathsf{d}(R,b)^{p}\right),$

and, for some constant $C>0$,

$\mathcal{C}_{MST}^{\infty}(R,B)\leq
C\left(\mathcal{C}_{MST}^{\infty}(R)+\mathsf{d}(R,B)\right).$

###### Proof.

For simplicity, we assume that all edge weights are different (otherwise a
small perturbation of the weights and a suitable limit gives the thesis). Let
$T_{R}$ denote the MST for the vertex set $R$ and fix $\bar{r}\in R$. For
every $r\in R$, there exists a unique path in $T_{R}$ with minimal length
connecting $r$ to $\bar{r}$. We associate to every $r\in
R\setminus\left\\{\bar{r}\right\\}$ the first edge $e(r)$ of such path (so
that $r\in e(r)$). The correspondence $r\mapsto e(r)$ is a bijection.

We use this correspondence to define a connected spanning graph $S$ (not
necessarily a tree) on the bipartite graph with independent sets $R$, $B$. For
every $r\in R\setminus\left\\{\bar{r}\right\\}$, if
$e(r)=\left\\{r,r^{\prime}\right\\}$, we add the edge
$\left\\{\mathsf{n}(r),r^{\prime}\right\\}$ to $S$, where
$\mathsf{n}(r)=\mathsf{n}_{G}(r)\in B$ and $G$ is the complete bipartite graph
with independent sets $R$, $B$. Moreover, for every $r\in R$, $b\in B$ we also
add the edges $\left\\{r,\mathsf{n}(r)\right\\}$,
$\left\\{b,\mathsf{n}(b)\right\\}$. $S$ is connected because every $b\in B$ is
connected to $R$ and the vertex set $R$ is connected: any path on $T_{R}$
naturally corresponds to a path on $S$ using the pair of edges
$\left\\{r,\mathsf{n}(r)\right\\}$,
$\left\\{\mathsf{n}(r),r^{\prime}\right\\}$ instead of an edge
$e(r)=\left\\{r,r^{\prime}\right\\}$. The triangle inequality gives

$\mathsf{d}(\mathsf{n}(r),r^{\prime})^{p}\leq\left(\mathsf{d}(\mathsf{n}(r),r)+\mathsf{d}(r,r^{\prime})\right)^{p}\leq
C\left(\mathsf{d}(\mathsf{n}(r),r)^{p}+\mathsf{d}(r,r^{\prime})^{p}\right),$

for some constant $C=C(p)>0$, hence

$\sum_{\left\\{r,b\right\\}\in S}\mathsf{d}(r,b)^{p}\leq
C\left(\sum_{\left\\{r,r^{\prime}\right\\}\in
T}\mathsf{d}(r,r^{\prime})^{p}+\sum_{r\in
R}\mathsf{d}(r,\mathsf{n}(r))^{p}+\sum_{b\in
B}\mathsf{d}(b,\mathsf{n}(b))^{p}\right)$

and the first claim follows. Taking the $p$-th root both sides and letting
$p\to\infty$ yields the second inequality. ∎

######  Remark 2.6.

In the Euclidean setting $X=\mathbb{R}^{d}$, it is known [9] that, if $p<d$,
there exists a constant $C=C(d,p)>0$ such that

$\mathcal{C}_{MST}^{p}(V)\leq C|V|^{1-p/d},$ (2.5)

for any $V\subseteq[0,1]^{d}$. A similar uniform bound cannot be true in the
bipartite case, as simple examples show.

A second fundamental difference between the usual Euclidean MST and its
bipartite variant is that for the latter its maximum vertex degree does not
need to be uniformly bounded by a constant $C=C(d)>0$ (again, examples are
straightforward). The following result will be crucial to provide an upper
bound in the random case. We say that $Q\subseteq\mathbb{R}^{d}$ is a cube if
$Q=\prod_{i=1}^{d}(x_{i},x_{i}+a)$ with $x=(x_{i})_{i=1}^{d}\in\mathbb{R}^{d}$
and $a>0$ is its side length. The diameter of $Q$ is then $\sqrt{d}a$ and its
volume $|Q|=a^{d}$.

######  Lemma 2.7.

Let $R$, $B\subseteq X$, let $T$ be a MST on the bipartite graph with
independent sets $R$, $B$ and edge weight $w(x,y)=\mathsf{d}(x,y)$ and let
$\left\\{r,b\right\\}\in T$ with $\delta:=\mathsf{d}(r,b)>\mathsf{d}(R,B)$.
Then $S\cap R=\emptyset$, where

$S=\left\\{x\in X\,:\,\text{ $\mathsf{d}(x,r)<\delta-\mathsf{d}(R,B)$ and
$\mathsf{d}(x,b)<\delta$}\right\\}.$

In particular, when $X=[0,1]^{d}$, $S$ contains a cube $Q\subseteq[0,1]^{d}$
with volume

$|Q|=\min\left\\{\left(\frac{\delta-\mathsf{d}(R,B)}{2\sqrt{d}}\right)^{d},1\right\\}.$

###### Proof.

Assume by contradiction that there exists $r^{\prime}\in S\cap R$, and
consider the two connected components of the disconnected graph
$T\setminus\left\\{r,b\right\\}$. If $r^{\prime}$ is in the same component as
$r$, then adding $\left\\{r^{\prime},b\right\\}$ to
$T\setminus\left\\{r,b\right\\}$ yields a tree (hence, connected) with
strictly smaller cost, since $\mathsf{d}(r^{\prime},b)<\delta$, hence a
contradiction. If $r^{\prime}$ is in the same component as $b$, then adding
$\left\\{\mathsf{n}(r),r^{\prime}\right\\}$ to
$T\setminus\left\\{r,b\right\\}$ again yields a tree with strictly smaller
cost, since the triangle inequality gives

$\mathsf{d}(\mathsf{n}(r),r^{\prime})\leq\mathsf{d}(\mathsf{n}(r),r)+\mathsf{d}(r,r^{\prime})<\mathsf{d}(R,B)+\delta-\mathsf{d}(R,B)<\delta.$

To prove the last statement, notice first that by convexity of $[0,1]^{d}$,
the point $x$ on the segment connecting $r$ and $b$ at
$(\delta-\mathsf{d}(R,B))/2$ from $r$ belongs to $[0,1]^{d}$. Moreover, the
open ball centred at $x$ with radius $(\delta-\mathsf{d}(R,B))/2$ is entirely
contained in $S$. Finally, intersection of any ball with radius $u\geq 0$ and
center $x\in[0,1]^{d}$ contains at least a cube of side length
$\min\\{u/\sqrt{d},1\\}$ (the worst case is in general when $x$ is a vertex of
$[0,1]^{d}$). ∎

###  2.3. Probabilistic estimates

In this section we collect some basic probabilistic bounds on distances
between i.i.d. uniformly distributed random variables $(X_{i})_{i=1}^{n}$ on a
cube $Q\subseteq\mathbb{R}^{d}$. Some of these facts are well known,
especially for $d=1$, since they are related to order statistics, but we
provide here short proofs for completeness. The basic observation is that, for
every $x\in\mathbb{R}^{d}$,
$0\leq\lambda\leq\left(|Q|/\omega_{d}\right)^{1/d}$, then

$P(\left|x-X_{i}\right|>\lambda)=\frac{|Q\setminus B(x,\lambda)|}{|Q|}\geq
1-\omega_{d}\lambda^{d}/|Q|,$ (2.6)

hence, by independence,

$P\left(\min_{i=1,\ldots,n}\left|x-X_{i}\right|>\lambda\right)\geq\left(1-\omega_{d}\lambda^{d}/|Q|\right)^{n},\quad\text{for
every $x\in\mathbb{R}^{d}$.}$

If $x\in Q$, we also have the upper bound (the worst case being $x$ a vertex
of $Q$)

$P(\left|x-X_{i}\right|>\lambda)\leq 1-\omega_{d}2^{-d}\lambda^{d}/|Q|,$

hence,

$P\left(\min_{i=1,\ldots,n}\left|x-X_{i}\right|>\lambda\right)\leq\left(1-\omega_{d}2^{-d}\lambda^{d}/|Q|\right)^{n},\quad\text{for
every $x\in Q$.}$ (2.7)

Assume $Q=[0,1]^{d}$. The layer-cake formula
$\mathbb{E}\left[Z^{p}\right]=\int_{0}^{\infty}P(Z>\lambda)p\lambda^{p-1}d\lambda$
yields, for every $p>0$, existence of a constant $C=C(d,p)>0$ such that, for
every $n\geq 1$,

$C^{-1}n^{-p/d}\leq\sup_{x\in[0,1]^{d}}\mathbb{E}\left[\min_{i=1,\ldots,n}\left|x-X_{i}\right|^{p}\right]\leq
Cn^{-p/d}.$ (2.8)

For $A\subseteq[0,1]^{d}$, write $N(A)=\sum_{i=1}^{n}I_{A}(X_{i})$. Then
$N(A)$ has binomial law with parameters $(n,|A|)$. In particular, for every
$t>0$,

$\mathbb{E}\left[t^{N(A)}\right]=(1+(t-1)|A|)^{n}.$

Markov inequality yields that, letting $F(t)=\left(t\log t-t+1\right)$ then,
for every $t>1$,

$P(N(A)>tn|A|)\leq\exp\left(-n|A|F(t)\right),$ (2.9)

and, for $t<1$,

$P(N(A)<tn|A|)\leq\exp\left(-n|A|F(t)\right).$ (2.10)

We need some uniform bounds on $N(Q)$ for every cube $Q\subseteq[0,1]^{d}$
with sufficiently large or small volume. We write for brevity, for $v\geq 0$,

$N^{*}(v):=\sup\left\\{N(Q)\,:\,\text{ $Q\subseteq[0,1]^{d}$ cube with
$|Q|\leq v$}\right\\},$

and

$N_{*}(v):=\inf\left\\{N(Q)\,:\,\text{ $Q\subseteq[0,1]^{d}$ cube with
$|Q|\geq v$}\right\\}.$

######  Lemma 2.8.

Let $(X_{i})_{i=1}^{n}$ be i.i.d. uniformly distributed on $[0,1]^{d}$. For
every $v\in(0,1)$, there exist $C=C(v,d)\geq 1$ such that, for every $n\geq
C$, if $t>2^{2d}$, then

$P\left(N^{*}(v)>tnv\right)\leq\frac{1}{2^{d}v}\exp\left(-nv2^{d}F(t2^{-2d})\right),$
(2.11)

while, if $t<2^{-2d}$,

$P\left(N_{*}(v)<tnv\right)\leq\frac{2^{2d}}{v}\exp\left(-nv2^{-2d}F(t2^{2d})\right).$
(2.12)

###### Proof.

We prove (2.11) first. Let $k\in\mathbb{Z}$ such that

$2^{-k-2}\leq v^{1/d}<2^{-k-1},$

so that every cube $Q$ with $|Q|=v$ is contained in a dyadic cube
$\prod_{\ell=1}^{d}(n_{\ell}2^{-k},(n_{\ell}+1)2^{-k})$, with
$(n_{\ell})_{i=1}^{d}\in\left\\{0,\ldots,2^{k}-1\right\\}^{d}$. It is then
sufficient to consider the event $N(Q)>tnv$ for at least one such dyadic cube,
i.e., using the union bound (2.9), we bound from above

$P\left(N^{*}(v)>tnv\right)\leq 2^{kd}P\left(N(Q)>tnv)\right).$

Using that, for a dyadic cube with $|Q|=2^{-dk}$,

$2^{kd}\leq 1/(2^{d}v)\quad\text{and}\quad|Q|2^{-2d}\leq v\leq 2^{-d}|Q|,$

it follows that (2.9) applies with $2^{-2d}t$ instead of $t$, yielding

$\begin{split}2^{kd}P\left(N(Q)>tnv\right)&\leq
2^{kd}P\left(N(Q)>2^{-2d}tn|Q|\right)\\\
&\leq\frac{1}{2^{d}v}\exp\left(-n|Q|F(t2^{-2d})\right)\\\
&\leq\frac{1}{2^{d}v}\exp\left(-nv2^{d}F(t2^{-2d})\right).\end{split}$

The argument for (2.12) is analogous. Let $k\in\mathbb{Z}$ be such that

$2^{-k+1}\leq v^{1/d}<2^{-k+2},$

hence every cube $Q$ with $|Q|\geq v$ contains at least one dyadic cube with
volume $2^{-kd}$, and we are reduced to consider the event that for such a
cube $N(Q)<tnv$, i.e.,

$P\left(N_{*}(v)<tnv\right)\leq 2^{kd}P\left(N(Q)<tnv\right).$

Using that

$2^{kd}\leq 2^{2d}/v\quad\text{and}\quad 2^{d}|Q|\leq v\leq 2^{2d}|Q|,$

it follows that (2.10) applies with $2^{2d}t$ instead of $t$, yielding

$\begin{split}2^{kd}P\left(N(Q)<tnv\right)&\leq
2^{kd}P\left(N(Q)<2^{2d}tn|Q|\right)\\\
&\leq\frac{2^{2d}}{v}\exp\left(-n|Q|F(t2^{2d})\right)\\\
&\leq\frac{2^{2d}}{v}\exp\left(-nv2^{-2d}F(t2^{2d})\right).\qed\end{split}$

In the following result we investigate the random variable (for $n\geq 2$)

$M^{n}=\max_{i=1,\ldots,n}|X_{i}-\mathsf{n}(X_{i})|,$

where $\mathsf{n}(X_{i})$ denotes the closest point to $X_{i}$ among
$\left\\{X_{j}\right\\}_{j\neq i}$, so that

$|X_{i}-\mathsf{n}(X_{i})|=\min_{\begin{subarray}{c}j\leq n\\\ j\neq
i\end{subarray}}|X_{i}-X_{j}|.$

Heuristically, since $|X_{i}-\mathsf{n}(X_{i})|\sim n^{-1/d}$, and the random
variables are almost independent, we still expect that $M^{n}\sim n^{-1/d}$,
up to logarithmic factors. This is indeed the case.

######  Proposition 2.9.

Let $n\geq 2$, $(X_{i})_{i=1}^{n}$ be i.i.d. uniformly distributed on
$[0,1]^{d}$. Then, for every $a>0$, there exists a constant $C=C(a,d)\geq 1$
such that

$P\left(C^{-1}\leq\frac{M^{n}}{(\log(n)/n)^{1/d}}\leq C\right)\geq
1-\frac{C}{n^{a}}.$

In particular, for every $q>0$, there exists $C=C(d,q)>0$ such that, for every
$n\geq 2$,

$\mathbb{E}\left[\left(M^{n}\right)^{q}\right]\leq C\left(\frac{\log
n}{n}\right)^{q/d}.$ (2.13)

###### Proof.

For every $n$ sufficiently large, we choose
$\eta=\eta(d,n)\in((a+1)2^{2d+1},(a+1)2^{2d+2})$ such that, defining
$\delta=\left(\eta\log(n)/{n}\right)^{1/d}$, we have that $1/(3\delta)^{d}$ is
integer.

Consider a partition of $[0,1]^{d}$ into cubes $\left\\{Q_{j}\right\\}_{j\in
J}$ of volume $|Q_{j}|=v:=\delta^{d}$, with
$J=\left\\{1,\ldots,\delta^{-d}\right\\}$. Fix $\bar{t}>2^{2d}$ such that
$2^{d}F(\bar{t}2^{-2d})>a+1$. Lemma 2.8 entails that the event

$E:=\bigcap_{j\in J}\left\\{2\leq N(Q_{j})\leq\bar{t}\log
n\right\\}\supseteq\left\\{N^{*}(v)\leq\bar{t}\log
n\right\\}\cap\left\\{N_{*}(v)\geq 2\right\\}.$

has probability larger than $1-C/n^{a}$ for some constant $C=C(d,a)$. Indeed,
(2.11) gives

$\begin{split}P(N^{*}(v)\leq\bar{t}\log n)&=P\left(N^{*}(v)\leq\bar{t}/\eta
nv\right)\\\ &\leq 2^{-d}\frac{n}{\eta\log n}\exp\left(-\log(n)\eta
2^{d}F(\bar{t}2^{2d}/\eta)\right)\\\ &{}^{\leq}\frac{1}{2^{d+1}\eta
n^{a}},\end{split}$

having also used that $\eta\geq 1$. Similarly, by (2.12), with
$t=2/(\log(n)\eta)$,

$\begin{split}P(N_{*}(v)>2)&=P\left(N_{*}(v)>\left(2/(\log(n)\eta)\right)nv\right)\\\
&\leq 2^{2d}\frac{n}{\eta\log n}\exp\left(-\log(n)\eta
2^{-2d}F(2/(\log(n)\eta))\right).\end{split}$

For $n$ sufficiently large, $F\left(2/(\log(n)\eta)\right)o>1/2$, hence

$\begin{split}2^{2d}\frac{n}{\eta\log n}\exp\left(-\log(n)\eta
2^{-2d}F(2/(\log(n)\eta))\right)&\leq 2^{2d}\frac{n}{\eta\log
n}\exp\left(-\log(n)\eta 2^{-2d-1}\right)\\\ &\leq\frac{2^{2d}}{\eta
n^{a}}.\end{split}$

Hence, to prove the thesis, we can assume that $E$ holds. In such a case, it
follows at once that $M^{n}\leq\sqrt{d}v^{1/d}$, hence

$P\left(\frac{M^{n}}{(\log(n)/n)^{1/d}}>\sqrt{d}\eta^{1/d}\right)\leq\frac{C}{n^{a}}.$

Next, we introduce the random variables

$M^{n}_{j}:=\sup_{\begin{subarray}{c}i\leq n\\\ X_{i}\in
Q_{j}\end{subarray}}\,\inf_{\begin{subarray}{c}\ell\leq n\\\
0<|X_{i}-X_{\ell}|<\delta\end{subarray}}|X_{i}-X_{\ell}|,$

i.e., we maximize the minimum distances between points in $Q_{j}$ and those
that are at distance at most $\delta$. These are not necessarily in $Q_{j}$
but must belong to the union of all cubes $Q_{\ell}$ covering
$\left\\{x|\mathsf{d}(x,Q_{j})\leq\delta\right\\}$, that we denote by
$Q_{j,\delta}$. Since every cube $\left\\{Q_{j}\right\\}_{j\in J}$ has side
length $\delta$, then $Q_{j,\delta}$ is a cube of side length $3\delta$, hence
$|Q_{j,\delta}|/|Q|=3^{d}$. Notice also that, since each cube $Q_{j}$ contains
at least two elements (for we assume that $E$ holds) then

$M^{n}=\max_{j\in J}M^{n}_{j}.$

We now use the following fact: for every $f:\left\\{1,\ldots,n\right\\}\to J$,
conditioning upon the event

$A_{f}=\left\\{X_{i}\in Q_{f(i)}\quad\text{for every
$i=1,\ldots,n$,}\right\\},$

the random variables $(X_{i})_{i=1}^{n}$ are independent, each $X_{i}$ uniform
on $Q_{f(i)}$. Thus, we further disintegrate upon the events $A_{f}$, and
since $E$ holds we consider only $f$’s such that, for every $j\in J$,

$2\leq\left|\left\\{f=j\right\\}\right|\leq\bar{t}\log n.$

We let $K\subseteq J$ denote a subfamily consisting of $(\delta 3)^{-d}$ cubes
such that, for $j,k\in K$, with $j\neq k$, $Q_{j,\delta}\cap
Q_{k,\delta}=\emptyset$ so that the random variables $(M^{n}_{k})_{k\in K}$
are independent (after conditioning upon $A_{f}$). Using

$M^{n}=\max_{j\in J}M^{n}_{j}\geq\max_{k\in K}M^{n}_{k},$

and independence we have, for every $\lambda>0$,

$P(M^{n}\leq\lambda|A_{f})\leq P(\max_{k\in
K}M^{n}_{k}\leq\lambda|A_{f})=\prod_{k\in K}P(M^{n}_{k}\leq\lambda|A_{f})$

The probability $P(M^{n}_{k}\leq\lambda|A_{f})$ clearly depends only on the
number of elements in each $\left\\{f=j\right\\}$, i.e., on the number of
points in each $Q_{j}$, for $j\in J$, not their labels. We may therefore
assume that $f(1)=k$, i.e., $X_{1}\in Q_{k}$ and that

$\left\\{X_{i}\right\\}_{i=1}^{n}\cap
Q_{k,\delta}=\left\\{X_{1},\ldots,X_{\ell}\right\\},$

with

$\ell=N(Q_{k,\delta})\leq 3^{d}\bar{t}\log n.$ (2.14)

Then,

$M^{n}_{k}\geq\min_{j=2,\ldots,\ell}|X_{j}-X_{1}|,$

hence, further conditioning upon $X_{1}$ and using independence,

$\begin{split}P(M^{n}_{k}>\lambda|A_{f})&\geq\frac{1}{|Q_{k}|}\int_{Q_{k}}P\left(\min_{j=2,\ldots,\ell}|X_{j}-x|>\lambda|A_{f},X_{1}=x\right)dx\\\
&\geq\frac{1}{|Q_{k}|}\int_{Q_{k}}\prod_{j=2}^{\ell}P(|X_{j}-x|>\lambda|A_{f},X_{1}=x)dx\\\
&\geq\frac{1}{|Q_{k}|}\int_{Q_{k}}\prod_{j=2}^{\ell}\left(1-\omega_{d}\lambda^{d}/|Q_{f(j)}|\right)_{+}dx\quad\text{by
\eqref{eq:steele-lower},}\\\
&\geq\left(1-\omega_{d}(\lambda/\delta)^{d}\right)^{N(Q_{k,\delta})-1}_{+}=e^{-u(N(Q_{k,\delta})-1)},\end{split}$

where in the last equality we choose
$\lambda=\delta((1-e^{-u})/\omega_{d})^{1/d}$ with $u=1/(2\cdot
3^{d}\bar{t})$. Indeed, this choice ensures that, by (2.14) we bound from
above, for $n$ sufficiently large,

$P\left(M^{n}\leq\lambda|A_{f}\right)\leq\left(1-e^{-u(3^{d}\bar{t}\log(n)-1)}\right)^{(\delta
3)^{-d}}\leq\left(1-\frac{e^{u}}{n^{1/2}}\right)^{n/(3^{d}\log(n))}\leq\frac{C}{n^{a}}.$

Finally, (2.13) follows since $M^{n}\leq\sqrt{d}$, hence, choosing $a=q/d$, we
bound from above

$\mathbb{E}\left[\left(M^{n}\right)^{q}\right]\leq
d^{q/2}P(M^{n}>C(\log(n)/n)^{1/d})+C^{q}\left(\frac{\log
n}{n}\right)^{q/d}\leq C^{\prime}\left(\frac{\log n}{n}\right)^{q/d}.\qed$

A minor variation of the proof of the previous proposition yields the
following bipartite analogue, where we replace $M^{n}$ with the (random)
Hausdorff distance between $R$ and $B$.

######  Proposition 2.10.

For $n\geq 1$, let $R^{n}=\left\\{X_{i}\right\\}_{i=1}^{n_{R}}$,
$B^{n}=\left\\{Y_{i}\right\\}_{i=1}^{n_{B}}$ be (jointly) i.i.d. uniformly
distributed on $[0,1]^{d}$ with $n_{R}+n_{B}=n$ and

$\lim_{n\to\infty}\frac{n_{R}}{n}=\alpha_{R}\in(0,1),\quad\lim_{n\to\infty}\frac{n_{B}}{n}=\alpha_{B}=1-\alpha_{R}.$

Then, for every $a>0$, there exists a constant
$C=C(d,\alpha_{R},\alpha_{B},a)\geq 1$ such that, for every $n$ sufficiently
large,

$P\left(C^{-1}\leq\frac{\mathsf{d}(R^{n},B^{n})}{(\log(n)/n)^{1/d}}\leq
C\right)\geq 1-\frac{C}{n^{a}}.$

In particular, for every $q>0$, there exists $C=C(d,q,\alpha_{R})>0$ such
that, for every $n$ sufficiently large,

$\mathbb{E}\left[\mathsf{d}(R^{n},B^{n})^{q}\right]\leq C\left(\frac{\log
n}{n}\right)^{q/d}.$

##  3\. Proof of Theorem 1.1

Throughout this section, for $n\geq 1$, let
$R^{n}=\left\\{X_{i}\right\\}_{i=1}^{n_{R}}$,
$B^{n}=\left\\{Y_{i}\right\\}_{i=1}^{n_{B}}$ be (jointly) i.i.d. uniformly
distributed on $[0,1]^{d}$ with $n_{R}+n_{B}=n$ and

$\lim_{n\to\infty}\frac{n_{R}}{n}=\alpha_{R}\in(0,1),\quad\lim_{n\to\infty}\frac{n_{B}}{n}=\alpha_{B}=1-\alpha_{R}.$

Let $T^{n}$ denote the Euclidean bipartite MST on $R^{n}$, $B^{n}$, and write
$\Delta(T^{n})$ be the maximum vertex degree of $T^{n}$.

We split the proof into two separate results.

######  Lemma 3.1.

There exists $\epsilon>0$ such that, as $n\to\infty$,

$P\left(\Delta(T^{n})<\epsilon\log n\right)\to 0.$

###### Proof.

For $n$ sufficiently large, we have $n_{R}\geq\alpha_{R}n/2$,
$n_{B}\geq\alpha_{B}n/2$. Fix any $a>0$ and let $C_{1}=C(d,a)\geq 1$ be as in
Proposition 2.9 applied to the variables $(X_{i})_{i=1}^{n_{R}}$, so that the
event $E^{n}$, such that there exists $X_{i}\in R^{n}$ with

$\min_{j\neq i}|X_{i}-X_{j}|\geq
C^{-1}_{1}\left(\log(n_{R})/n_{R}\right)^{1/d}\geq
C^{-1}\left(\log(n)/n\right)^{1/d},$

(the second inequality being true if $n$ is sufficiently large) has
probability $P(E^{n})\geq 1-C/n^{a}$ as $n\to\infty$, for a suitable constant
$C=C(d,\alpha_{R},a)>0$. In particular, every point in the cube $Q$ centred at
$X_{i}$ with side length

$\delta=\left(\log(n)/n\right)^{1/d}/(4\sqrt{d}C)$

is strictly closer to $X_{i}$ than any other point in $R^{n}$. Notice that
$E^{n}$ and such cube $Q$ depend on the random variables $R^{n}$ only. By
Lemma 2.2, if $E^{n}$ holds, every $Y_{j}\in Q$ will be adjacent in $T^{n}$ to
$X_{i}$, hence, choosing

$\epsilon=1/\left(2(4\sqrt{d}C)^{d}\right),\quad\text{ so that
}\quad(4\sqrt{d}C)^{d}\epsilon=1/2,$

and writing $N_{B^{n}}(Q)$ for the number of elements in $B^{n}\cap Q$, we
have

$\begin{split}P(\Delta(T_{n})<\epsilon\log(n))&\leq
P((E^{n})^{c})+P(N_{B^{n}}(Q)<n|Q|/2,E^{n})\\\
&\leq\frac{C}{n^{a}}+\mathbb{E}\left[I_{E^{n}}P\left(N_{B^{n}}(Q)<n\delta^{d}/2|\left\\{X_{i}\right\\}_{i=1}^{n_{B}}\right)\right].\end{split}$

By independence, the conditional law of $N_{B^{n}}(Q)$ is Binomial with
parameters $\left(n_{B},\delta^{d}\right)$, hence we may use (2.10) to obtain

$P\left(N_{B^{n}}(Q)<\epsilon\log(n)|\left\\{X_{i}\right\\}_{i=1}^{n_{B}}\right)\leq\exp\left(-n_{B}\delta^{d}F(1/2)\right).$

Since $n_{B}\geq\alpha_{B}n/2$, $\delta^{d}=\log(n)/(n(4\sqrt{d}C))$ and
$F(1/2)>0$, it follows that, as $n\to\infty$,

$\exp\left(-n_{B}\delta^{d}F(1/2)\right)\to 0.\qed$

######  Lemma 3.2.

For every $a>0$, exists $C=C(d,a,\alpha_{R})>0$ such that, for $n$
sufficiently large,

$P\left(\Delta(T^{n})>C\log(n)\right)\leq\frac{C}{n^{a}}.$

In particular, for every $q>0$, there exists $C=C(d,q,\alpha_{R})>0$ such
that, for every $n$ large enough,

$\mathbb{E}\left[\Delta(T^{n})^{q}\right]\leq C\left(\log n\right)^{q}.$ (3.1)

###### Proof.

For $n$ sufficiently large, we have $n_{R}\geq\alpha_{R}n/2$,
$n_{B}\geq\alpha_{B}n/2$. Fix $a>0$ and let $C_{1}=C_{1}(d,a,\alpha_{R})\geq
1$ be as in Proposition 2.10 applied to the variables $(X_{i})_{i=1}^{n_{R}}$,
$(Y_{j})_{j=1}^{n_{B}}$ so that, if $n$ is sufficiently large, the event

$\left\\{\mathsf{d}(R^{n},B^{n})>C_{1}(\log(n)/n)^{1/d}\right\\}$

has probability smaller than $C_{1}/n^{a}$. We claim that there exist
$\lambda=\lambda(d,a,\alpha_{R})>8C_{1}$ and $C=C(d,a,\alpha_{R})$ such that
the following conditions hold, for $n$ sufficiently large:

  1. (1)

letting $v_{1}=\left(\lambda/8\right)^{d}\log(n)/n$, then

$P\left(N^{*}_{R^{n}}(v_{1})>\lambda^{d}\log
n\right)\leq\frac{C}{n^{a}}\quad\text{and}\quad
P\left(N^{*}_{B^{n}}(v_{1})>\lambda^{d}\log n\right)\leq\frac{C}{n^{a}};$

  2. (2)

letting
$v_{2}=\left[\left(\lambda/8-C_{1})\right)/(\sqrt{d})\right]^{d}\log(n)/n$,
then

$P\left(\left(N_{R^{n}}\right)_{*}(v_{2})=0\right)\leq\frac{C}{n^{a}},\quad
P\left(\left(N_{B^{n}}\right)_{*}(v_{2})=0\right)\leq\frac{C}{n^{a}}.$

Once the claim is proved, it is immediate to show that on the event

$\begin{split}E=\Big{\\{}\mathsf{d}(R,B)>C_{1}(\log(n)/n)^{1/d},&\max\left\\{N^{*}_{R^{n}}(v_{1}),N^{*}_{B^{n}}(v_{1})\right\\}\leq\lambda^{d}\log
n\\\
&\min\left\\{\left(N_{R^{n}}\right)_{*}(v_{2}),\left(N_{B^{n}}\right)_{*}(v_{2})\right\\}\geq
1\Big{\\}}\end{split}$

that satisfies $P(E^{c})<C/n^{a}$ (with a different constant $C$), it must be
$\Delta(T^{n})\leq\lambda^{d}\log(n)$. Indeed, if
$\Delta(T^{n})>\lambda^{d}\log n$ assuming without loss of generality that
$X_{i}\in R^{n}$ has degree larger than $\lambda^{d}\log n$, it follows from
$N_{B^{n}}^{*}(v_{1})\leq\lambda^{d}\log n$ that there must be a node in
$Y_{j}\in B^{n}$ adjacent to $X_{i}$ that does not belong to the cube with
volume $v_{1}$ centered at $X_{i}$. In particular,

$|Y_{j}-X_{i}|\geq\frac{\lambda}{8}\left(\log(n)/n\right)^{1/d}>C_{1}\left(\log(n)/n\right)^{1/d}\geq\mathsf{d}(R^{n},B^{n}).$

By Lemma 2.7, there exists a cube $Q$ with $Q\cap R^{n}=\emptyset$ and

$|Q|\geq\left[\left(\lambda/8-C_{1})\right)/(2\sqrt{d})\right]^{d}\frac{\log(n)}{n}=v_{2},$

contradicting $(N_{R^{n}})_{*}(v_{2})>0$.

To prove the claim, we apply Lemma 2.8. Indeed, (2.11) with $t=8^{d}n/n_{R}$
gives

$\begin{split}P\left(N^{*}_{R^{n}}(v_{1})>\lambda^{d}\log
n\right)&=P\left(N^{*}_{R^{n}}(v_{1})>8^{d}(n/n_{R})\cdot v_{1}n_{R}\right)\\\
&\leq\frac{1}{2^{d}v_{1}}\exp\left(-n_{R}v_{1}2^{d}F(2^{d}n/n_{R})\right)\\\
&\leq\frac{2^{2d}n}{\lambda^{d}\log(n)}\exp\left(-\log(n)(n_{R}/n)\cdot\lambda^{d}2^{-2d}F(2^{d})\right)\leq\frac{C}{n^{a}},\end{split}$

provided that $n$ is sufficiently large and
$\lambda^{d}\alpha_{R}2^{-2d-1}F(2^{d})\geq a+1$. Conversely, we use (2.12)
with
$t=1/n_{R}v_{2}=\left[\left(\lambda/8-C_{1})\right)/(\sqrt{d})\right]^{-d}n/(n_{R}\log(n))<2^{-2d}$
(if $n$ is sufficiently large) so that

$P\left(N^{*}_{R^{n}}(v_{1})<1\right)\leq
2^{2d}\left[\left(\lambda/8-C_{1})\right)/(2\sqrt{d})\right]^{-d}\frac{n}{\log
n}\exp\left(-n_{R}v_{2}2^{-2d}F(t2^{2d})\right)\leq\frac{C}{n^{a}},$

provided that we choose $\lambda$ large enough such that

$\left[\left(\lambda/8-C_{1})\right)/(2\sqrt{d})\right]^{d}2^{-2d-1}\geq a+1,$

since for $n$ sufficiently large, we have $F(t2^{2d})>1/2$.

Finally, (3.1) follows since trivially $\Delta(T^{n})\leq n$, hence, choosing
$a=q$, we bound from above

$\mathbb{E}\left[\Delta(T^{n})^{q}\right]\leq n^{q}P(\Delta(T^{n})>C\log
n)+\left(C\log n\right)^{q}\leq C+\left(C\log n\right)^{q}.\qed$

##  4\. Proof of Theorem 1.2

We first extend [14, Theorem 1] to the bipartite case. Let $G=(V,E,w)$ be a
random weighted graph, i.e., $(w_{e})_{e\in E}$ are random variables. To
simplify, we assume throughout this section that $G$ is the complete graph
over $V=\left\\{1,\ldots,m\right\\}$ for some $m\geq 1$, but allow weights
$w(e)\in[0,\infty]$. Recall that connection between nodes is meant only along
paths consisting of edges with finite weight: we assume in particular that $G$
is a.s. connected. The number of connected components of $G(z)$ can be written
as

$C_{G(z)}=\sum_{k=1}^{m}\sum_{i=1}^{m}\frac{X_{i,k,G(z)}}{k},$ (4.1)

where the random variable $X_{i,k,G(z)}\in\left\\{0,1\right\\}$ indicates
whether $i\in V$ belongs to a component of $G(z)$ having exactly $k$ elements.
Similarly, for the number of connected components having at least $k$ nodes,

$C_{k,G(z)}=\sum_{\ell=k}^{m}\sum_{i=1}^{m}\frac{X_{i,\ell,G(z)}}{\ell},$

To estimate the expectation of $X_{i,k,G(z)}$, in [14] it is assumed that
$\left(w_{i,j}\right)_{i,j\in V}$ are exchangeable random variables. To extend
the validity of their results to the bipartite case we relax this condition by
requiring that the joint law of the weights is invariant with respect to the
symmetries of an underlying graph model (such as a complete bipartite graph).
Let us give the following general definition.

######  Definition 4.1.

On a random weighted graph $G=(V,E,w)$, nodes $i,j\in V$ are said equivalent
in law if there exists a bijection $\pi:V\to V$ such that $\pi(i)=j$ and
$\left(w_{k,\ell}\right)_{k,\ell\in V}$ have the same joint law as
$\left(w_{\pi(k),\pi(\ell)}\right)_{k,\ell\in V}$.

Clearly, this defines an equivalence relation, which is relevant for our
purposes since, if $i,j\in V$ are equivalent in law, then for every $k$,
$z\geq 0$ the random variables $X_{i,k,G(z)}$, $X_{j,k,G(z)}$ have the same
law. Therefore, when computing the expectation
$\mathbb{E}\left[C_{G(z)}\right]$ using (4.1), we are reduced to a summation
upon $k$ and the equivalence classes. If the weights are exchangeable, then
there is only one equivalence class, but this is also the case a random
Euclidean bipartite graph with $V=R\cup B$ and $|R|=|B|$. To deal with
bipartite graphs with $|R|\neq|B|$ we consider the case of two (non empty)
equivalence classes $R$ and $B$. We introduce the functions

$P_{k,R,G(z)}=\mathbb{E}\left[X_{i,k,G(z)}\right]\quad\text{for $i\in R$, and
}\quad P_{k,B,G(z)}=\mathbb{E}\left[X_{j,k,G(z)}\right]\quad\text{for $j\in
B$,}$

i.e., the probability that a given node in $R$ (respectively in $B$) belongs
to a connected component of $G(z)$ with exactly $k$ elements. Taking the
expectation in (2.2) and (4.1), we deduce that

$\mathbb{E}\left[\mathcal{C}_{MST}(G)\right]=\int_{0}^{\infty}\left(\sum_{k=1}^{|V|}\frac{1}{k}\left(|R|P_{k,R,G(z)}+|B|P_{k,B,G(z)}\right)-1\right)dz.$
(4.2)

Consider now a sequence of random graphs
$\left(G^{n}\right)_{n=1}^{\infty}=\left((V^{n},E^{n},w^{n})\right)_{n=1}^{\infty}$,
each with two equivalence classes $V^{n}=R^{n}\cup B^{n}$, and write, for
brevity,

$C^{n}(z)=C_{G^{n}(z)},\quad C^{n}_{k}(z)=C_{k,G^{n}(z)},$
$P_{k,R}^{n}(z)=P_{k,R,G^{n}(z)}\quad\text{and}\quad
P_{k,B}^{n}(z)=P_{k,B,G^{n}(z)}.$

For a (pseudo-dimension) parameter $d>1$ we introduce the following
assumptions:

  1. a)

For any $k\geq 1$, $y>0$,

$\lim_{n\to\infty}P_{k,R}^{n}\left((y/n)^{1/d}\right)=f_{k,R}(y),\quad\text{and}\quad\lim_{n\to\infty}P_{k,B}^{n}\left((y/n)^{1/d}\right)=f_{k,B}(y),$

where convergence is pointwise and dominated in the following sense: there
exists a function $\ell_{k}$ such that, for every $y>0$,

$\sup_{n}P_{k,R}^{n}\left((y/n)^{1/d}\right)+P_{k,B}^{n}\left((y/n)^{1/d}\right)\leq\ell_{k}(y)$

and

$\int_{0}^{\infty}\ell_{k}(y)y^{\frac{1}{d}-1}dy<\infty.$

  2. b)

It holds

$\lim_{k\to\infty}\limsup_{n\to\infty}\left|\frac{1}{n^{1-\frac{1}{d}}}\int_{0}^{\infty}\left(\mathbb{E}\left[C_{k}^{n}(z)\right]-1\right)dz\right|=0.$

The following result extends [14, Theorem 1] to the bipartite case.

######  Theorem 4.2.

Let $d>1$ and $\left(G^{n}\right)_{n=1}^{\infty}$ be a sequence of random
graphs, each with two equivalence classes $V^{n}=R^{n}\cup B^{n}$, satisfying
assumptions a), b), and

$\lim_{n\to\infty}\frac{|R^{n}|}{n}=\alpha_{R}\in(0,1)\quad\text{and}\quad\lim_{n\to\infty}\frac{|B^{n}|}{n}=\alpha_{B}=1-\alpha_{R}.$

Then,

$\lim_{n\to\infty}\frac{\mathbb{E}\left[\mathcal{C}_{MST}(G^{n})\right]}{n^{1-1/d}}=\frac{1}{d}\sum_{k=1}^{\infty}\frac{1}{k}\int_{0}^{\infty}\left(\alpha_{R}f_{k,R}(y)+\alpha_{B}f_{k,B}(y)\right)y^{\frac{1}{d}-1}dy.$

###### Proof.

By (2.2), for any $n\geq 1$, $k\geq 1$, we decompose

$\begin{split}\frac{\mathbb{E}\left[\mathcal{C}_{MST}(G^{n})\right]}{n^{1-1/d}}&=\frac{1}{n^{1-1/d}}\int_{0}^{\infty}\left(\sum_{k=1}^{|V^{n}|}\frac{1}{k}\left(|R^{n}|P_{k,R}^{n}(z)+|B^{n}|P_{k,B}^{n}(z)\right)-1\right)dz\\\
&=n^{1/d}\int_{0}^{\infty}\left(\sum_{\ell=1}^{k-1}\frac{1}{\ell}\left(\frac{|R^{n}|}{n}P_{\ell,R}^{n}(z)+\frac{|B^{n}|}{n}P_{\ell,B}^{n}(z)\right)-\frac{1}{n}\right)dz\\\
&\quad+\frac{1}{n^{1-1/d}}\int_{0}^{\infty}\left(\mathbb{E}\left[C_{k}^{n}(z)\right]-1\right)dz.\end{split}$

Assumption b) gives that in the limit $n\to\infty$, $k\to\infty$ the second
term gives no contribution. Hence, it is sufficient to let $n\to\infty$ and
then $k\to\infty$ in first term. Actually, since $n^{1-1/d}\to\infty$, we only
need to prove that

$\begin{split}&\lim_{k\to\infty}\lim_{n\to\infty}n^{1/d}\int_{0}^{\infty}\sum_{\ell=1}^{k-1}\frac{1}{\ell}\left(\frac{|R^{n}|}{n}P_{\ell,R}^{n}(z)+\frac{|B^{n}|}{n}P_{\ell,B}^{n}(z)\right)dz\\\
&\quad=\frac{1}{d}\sum_{k=1}^{\infty}\frac{1}{k}\int_{0}^{\infty}\left(\alpha_{R}f_{k,R}(y)+\alpha_{B}f_{k,B}(y)\right)y^{1/d-1}dy,\end{split}$

which follows by dominated convergence, because of assumption b), after the
change of variables $z=(y/n)^{1/d}$. ∎

We now apply the above theorem to the bipartite MST problem on the
$d$-dimensional flat torus $\mathbb{T}^{d}=\mathbb{R}^{d}/\mathbb{Z}^{d}$,
endowed with the flat distance

$\mathsf{d}_{\mathbb{T}^{d}}(x,y):=\inf_{z\in\mathbb{Z}^{d}}|x-y+z|.$

######  Theorem 4.3.

Let $d\geq 1$, $n\geq 1$, $R^{n}=\left\\{X_{i}\right\\}_{i=1}^{n_{R}}$,
$B^{n}=\left\\{Y_{i}\right\\}_{i=1}^{n_{B}}$ be (jointly) i.i.d. uniformly
distributed on $\mathbb{T}^{d}$ with $n_{R}+n_{B}=n$ and

$\lim_{n\to\infty}\frac{n_{R}}{n}=\alpha_{R},\quad\lim_{n\to\infty}\frac{n_{B}}{n}=\alpha_{B}=1-\alpha_{R}.$

Then, for every $p\in(0,d)$,

$\lim_{n\to\infty}\frac{\mathbb{E}\left[\mathcal{C}_{MST}^{p}(R^{n},B^{n})\right]}{n^{1-p/d}}=\beta_{bMST}(d,p),$

with $\beta_{bMST}(d,p)$ as in Theorem 1.2.

###### Proof.

We apply Theorem 4.2 to the random bipartite graph $G^{n}$ over
$V^{n}=R^{n}\cup B^{n}$, and
$w^{n}(X_{i},Y_{j})=\mathsf{d}_{\mathbb{T}^{d}}(X_{i},Y_{j})^{p}$ – that can
be naturally identified with a graph over $\left\\{1,\ldots,n\right\\}$
(recall that we allow for infinite weights). We show separately that
assumptions a) and b) hold with $d/p>1$ instead of $d$.

We introduce some notation: for $k_{R}$, $k_{B}\in\mathbb{N}$, $z\geq 0$, let

$\Theta_{\mathbb{T}^{d}}(k_{R},k_{B},z)\subseteq(\mathbb{T}^{d})^{k_{R}}\times(\mathbb{T}^{d})^{k_{B}}$

denote the set of (ordered) points
$(\left(r_{i}\right)_{i=1}^{k_{R}},\left(b_{j}\right)_{j=1}^{k_{B}})$ such
that, in the associated bipartite graph with weights
$(\mathsf{d}_{\mathbb{T}^{d}}(r_{i},b_{j})^{p})_{i,j}$, the subgraph with all
edges having weight less than $z$ is connected (or equivalently, there exists
a bipartite spanning tree having all edges with weight less than $z$). For a
set $A\subseteq\mathbb{T}^{d}$, $z\geq 0$, write

$D_{\mathbb{T}^{d}}(A,z)=\left\\{x\in\mathbb{T}^{d}\,:\,\mathsf{d}_{\mathbb{T}^{d}}(A,x)^{p}\leq
z\right\\}.$

Recall that by definition $P_{k,n,R}(z)$ is the probability that a fixed
vertex in $R$, say $X_{1}$, belongs to a component of the subgraph $G^{n}(z)$
having exactly $k$ nodes. We disintegrate upon the nodes in $R$ and in $B$
belonging to such component. Clearly, only their numbers are relevant, not the
precise labels (except for $X_{1}$ that is fixed). Therefore, we compute the
probability $I_{R}(k_{R},k_{B},z)$ that $X_{1}$ belongs to a component with
$k_{R}$ nodes $\left\\{X_{i}\right\\}_{i=1}^{k_{R}}\subseteq R$ and $k_{B}$
nodes $\left\\{Y_{j}\right\\}_{j=1}^{k_{B}}\subseteq B$, with $k_{R}+k_{B}=k$,
which is precisely described as follows:

  1. i)

the set
$(\left\\{X_{i}\right\\}_{i=1}^{k_{R}},\left\\{Y_{j}\right\\}_{j=1}^{k_{B}})$
belongs to $\Theta_{\mathbb{T}^{d}}(k_{R},k_{B},z)$,

  2. ii)

$\mathsf{d}_{\mathbb{T}^{d}}(\left\\{Y_{j}\right\\}_{j=1}^{k_{B}},X_{i})>z$,
i.e. $X_{i}\notin D_{\mathbb{T}^{d}}(\left\\{Y_{j}\right\\}_{j=1}^{n_{B}},z)$,
for every $i>k_{R}$,

  3. iii)

$\mathsf{d}_{\mathbb{T}^{d}}(\left\\{X_{i}\right\\}_{i=1}^{k_{R}},Y_{j})>z$,
i.e. $Y_{j}\notin
D_{\mathbb{T}^{d}}\left(\left\\{X_{i}\right\\}_{i=1}^{k_{R}},z\right)$, for
every $j>k_{B}$.

Conditioning upon $\left\\{X_{i}\right\\}_{i=1}^{k_{R}}$,
$\left\\{Y_{j}\right\\}_{j=1}^{k_{B}}$ and using independence for the events
ii) and iii), we obtain the following expression for the probability:

$\begin{split}&I_{R}(k_{R},k_{B},z)=\\\
&\int_{\Theta_{\mathbb{T}^{d}}(k_{R},k_{B},z)}\left(1-|D_{\mathbb{T}^{d}}(\left\\{b_{j}\right\\}_{j=1}^{k_{B}},z)|\right)^{n_{R}-k_{R}}\left(1-|D_{\mathbb{T}^{d}}(\left\\{r_{i}\right\\}_{i=1}^{k_{R}},z)|\right)^{n_{B}-k_{B}}drdb,\end{split}$
(4.3)

where $drdb$ stands for integration performed with respect to the variables
$\left\\{r_{i}\right\\}_{i=1}^{k_{R}}$ and
$\left\\{b_{j}\right\\}_{j=1}^{k_{B}}$. Summing upon all the ${n_{R}\choose
k_{R}-1}{n_{B}\choose k_{B}}$ different choices of labellings (recall that
$X_{1}$ is kept fixed) and upon $k_{R}\geq 1$, $k_{B}$ with $k_{R}+k_{B}=k$
gives

$P_{k,R}^{n}(z)=\sum_{\begin{subarray}{c}k_{R}+k_{B}=k\\\ k_{R}\geq
1\end{subarray}}{n_{R}\choose k_{R}-1}{n_{B}\choose k_{B}}I(k_{R},k_{B},z).$
(4.4)

We now replace integration in (LABEL:eq:I-torus) from $(\mathbb{T}^{d})^{k}$
to $(\mathbb{R}^{d})^{k}$. This is possible provided that $z$ is small enough,
so that only the local structure is relevant. We first notice that, by
invariance with respect to translations, we can always fix one variable, say
$r_{1}=0$. We thus integrate upon the configurations
$\left\\{r_{i}\right\\}_{i=2}^{k_{R}}$, $\left\\{b_{j}\right\\}_{j=1}^{k_{B}}$
such that adding $0$ to the set $\left\\{r_{i}\right\\}_{i=2}^{k_{R}}$ yields
a bipartite graph that contains a spanning tree $T$ with edge weights smaller
than $z$. Now, if $z\leq 1/(4k)$, it follows that such tree is contained in a
ball of center $0\in\mathbb{T}^{d}$ and radius $1/4$, hence it can be
isometrically lifted to a tree on $(-1/2,1/2)^{d}\subseteq\mathbb{R}^{d}$.
Similarly, both $D(\left\\{b_{j}\right\\}_{j=1}^{k_{B}},z)$,
$D(\left\\{r_{i}\right\\}_{i=1}^{k_{R}},z)$ are then contained in a ball of
center $0$ and radius $1/2$, hence their volumes computed on $\mathbb{T}^{d}$
coincide with those of their lift on $(-1/2,1/2)^{d}\subseteq\mathbb{R}^{d}$.
To parallel the notation, we therefore the sets
$\Theta_{\mathbb{R}^{d}}(k_{R},k_{B},z)\subseteq(\mathbb{R}^{d})^{k_{R}}\times(\mathbb{R}^{d})^{k_{B}}$,
analogous to $\Theta_{\mathbb{T}^{d}}(k_{R},k_{B},z)$ – notice that

$\Theta_{\mathbb{R}^{d}}(k_{R},k_{B},1)=\Theta(k_{R},k_{B})$

defined in (1.3) – and write

$D_{\mathbb{R}^{d}}(A,z)=\left\\{x\in\mathbb{R}^{d}\,:\,\mathsf{d}(A,x)^{p}\leq
z\right\\},$

for $A\subseteq\mathbb{R}^{d}$ – notice that $D(A,1)=D(A)$ defined in (1.4).
For $z\leq 1/(4k)$, we have therefore

$\begin{split}&I_{R}(k_{R},k_{B},z)=\\\
&\int_{\Theta_{\mathbb{R}^{d}}(k_{R},k_{B},z)}\left(1-|D_{\mathbb{R}^{d}}(\left\\{b_{j}\right\\}_{j=1}^{k_{B}},z)|\right)^{n_{R}-k_{R}}\left(1-|D_{\mathbb{R}^{d}}(\left\\{r_{i}\right\\}_{i=1}^{k_{R}},z)|\right)^{n_{B}-k_{B}}\delta_{0}(r_{1})drdb,\end{split}$

where here $drdb$ denotes Lebesgue integration with respect to the remaining
$k-1$ variables in $\mathbb{R}^{d}$.

Since for every $A\subseteq\mathbb{R}^{d}$, $z>0$,

$D(A,z)=z^{1/p}D(z^{-1/p}A),$

a change of variable in the integration $r_{i}z^{-1/p}\mapsto r_{i}$,
$b_{i}z^{-1/p}\mapsto b_{i}$ yields

$\begin{split}I_{R}(k_{R},k_{B},z)=z^{(k-1)/p}&\int_{\Theta(k_{R},k_{B})}\left(1-z^{d/p}|D(\left\\{b_{j}\right\\}_{j=1}^{k_{B}})|\right)^{n_{R}-k_{R}}\cdot\\\
&\quad\cdot\left(1-z^{d/p}|D(\left\\{r_{i}\right\\}_{i=1}^{k_{R}})|\right)^{n_{B}-k_{B}}\delta_{0}(r_{1})drdb,\end{split}$

(notice the exponent $k-1$ instead of $k$ because of the different integration
for $r_{1}$). We now let $z:=\left(y/n\right)^{p/d}$, so that

$\begin{split}I_{R}(k_{R},k_{B},\left(y/n\right)^{p/d})=\frac{y^{(k-1)/d}}{n^{k-1}}&\int_{\Theta(k_{R},k_{B})}\left(1-\frac{y}{n}|D(\left\\{b_{j}\right\\}_{j=1}^{n_{B}})|\right)^{n_{R}-k_{R}}\cdot\\\
&\quad\cdot\left(1-\frac{y}{n}|D(\left\\{r_{i}\right\\}_{i=1}^{k_{R}})|\right)^{n_{B}-k_{B}}\delta_{0}(r_{1})drdb,\end{split}$

Since $\Theta(k_{R},k_{B})$ has finite measure (with respect to
$\delta_{0}(r_{1})drdb$), by dominated convergence it follows that

$\begin{split}\lim_{n\to\infty}&\int_{\Theta(k_{R},k_{B})}\left(1-\frac{y}{n}|D(\left\\{b_{j}\right\\}_{j=1}^{k_{B}})|\right)^{n_{R}-k_{R}}\left(1-\frac{y}{n}|D(\left\\{r_{i}\right\\}_{i=1}^{k_{B}})|\right)^{n_{B}-k_{B}}\delta_{0}(r_{1})drdb\\\
&=\int_{\Theta(k_{R},k_{B})}\exp\left(-y\left(\alpha_{R}|D(\left\\{b_{j}\right\\}_{j=1}^{k_{B}})|+\alpha_{B}|D(\left\\{r_{i}\right\\}_{i=1}^{k_{R}})|\right)\right)\delta_{0}(r_{1})drdb\\\
&=:\mathcal{I}_{R}(k_{R},k_{B},\alpha_{R},y).\end{split}$

Moreover,

$\lim_{n\to\infty}{n_{R}\choose k_{R}-1}{n_{B}\choose
k_{B}}\frac{1}{n^{k-1}}=\frac{\alpha_{R}^{k_{R}-1}}{(k_{R}-1)!}\frac{\alpha_{B}^{k_{B}}}{k_{B}!},$
(4.5)

so that

$\lim_{n\to\infty}P_{k,R}^{n}((y/n)^{p/d})=\sum_{\begin{subarray}{c}k_{R}+k_{B}=k\\\
k_{R}\geq
1\end{subarray}}\frac{\alpha_{R}^{k_{R}-1}}{(k_{R}-1)!}\frac{\alpha_{B}^{k_{B}}}{k_{B}!}y^{(k-1)/d}\mathcal{I}_{R}(k_{R},k_{B},\alpha_{R},y).$

To show that convergence is dominated, in view of (4.4) and the limit (4.5) it
is sufficient to dominate each term

$n^{k-1}I_{R}(k_{R},k_{R},(y/n)^{p/d}),$

If $A\subseteq\mathbb{T}^{d}$ is not empty, then
$|D(A,z)|\geq\omega_{d}z^{d/p}$ (assuming that $\omega_{d}z^{d/p}\leq 1$).
Therefore, if also $k_{B}\geq 1$, we write

$\begin{split}I_{R}(k_{R},k_{B},z)&=\int_{\Theta_{\mathbb{T}^{d}}(k_{R},k_{B},z)}(1-|D(\left\\{b_{j}\right\\}_{j=1}^{k_{B}},z)|)^{n_{R}-k_{R}}\left(1-|D(\left\\{r_{i}\right\\}_{i=1}^{k_{R}},z)|\right)^{n_{B}-k_{B}}drdb\\\
&\leq\int_{\Theta_{\mathbb{T}^{d}}(k_{R},k_{B},z)}(1-\omega_{d}z^{d/p})^{n-k}_{+}drdb\\\
&\leq\exp\left(-(n-k)z^{d/p}\right)|\Theta_{\mathbb{T}^{d}}(k_{R},k_{B},z)|\\\
&\leq k^{k-2}z^{d/p}\exp\left(-(n-k)z^{d/p}\right).\end{split}$

where the bound $|\Theta_{\mathbb{T}^{d}}(n_{R},n_{B},z)|\leq k^{k-2}z^{d/p}$
follows since every tree (even not necessarily bipartite) with edge weights
smaller than $z$ can be iteratively obtained by choosing points $x_{i+1}\in
D(\left\\{x_{j}\right\\}_{j=1}^{i},z)$. Substituting $z=(y/n)^{p/d}$ gives the
required domination. Notice that, if $k_{B}=0$ and $k_{R}\geq 2$, there is
nothing to prove, since $\Theta_{\mathbb{T}^{d}}(k_{R},k_{B},z)$ is empty. For
the case $k_{B}=0$, $k_{R}=1$ we argue similarly obtaining

$I_{R}(1,0,z)\leq\exp\left(-(n-1)z^{d/p}\right),$

which is sufficient to conclude. Arguing similarly for $P_{k,B}^{n}$ gives

$\lim_{n\to\infty}P_{k,B}^{n}((y/n)^{p/d})=\sum_{\begin{subarray}{c}k_{R}+k_{B}=k\\\
k_{B}\geq
1\end{subarray}}\frac{\alpha_{R}^{k_{R}}}{k_{R}!}\frac{\alpha_{B}^{k_{B}-1}}{(k_{B}-1)!}y^{(k-1)/d}\mathcal{I}_{B}(k_{R},k_{B},\alpha_{R},y),$

with similar definitions. Thus, the validity of assumption a) is established.

We notice here that, exchanging the order of integration,

$\begin{split}&\int_{0}^{\infty}y^{(k-1)/d}\mathcal{I}_{R}(k_{B},k_{R},\alpha_{R},y)y^{1/d-1}dy\\\
&=\int_{\Theta(k_{R},k_{B})}\int_{0}^{\infty}\exp\left(-y\left(\alpha_{R}|D(\left\\{b_{j}\right\\}_{j=1}^{k_{B}})|+\alpha_{B}D(\left\\{r_{i}\right\\}_{i=1}^{k_{R}})|\right)\right)y^{k/d-1}dy\delta_{0}(r_{1})drdb\\\
&=\Gamma(k/d)\int_{\Theta(k_{R},k_{B})}\left(\alpha_{R}|D(\left\\{b_{j}\right\\}_{j=1}^{k_{B}})|+\alpha_{B}|D(\left\\{r_{i}\right\\}_{i=1}^{k_{R}})|\right)^{-k/d}\delta_{0}(r_{1})drdb,\end{split}$

which, after some manipulations, taking into account also the term with
$\mathcal{I}_{B}$, gives the claimed expression for $\beta_{bMST}(p,d)$.

We next prove that assumption b) holds. A lower bound is straightforward,
since the maximum weight of the edges is uniformly bounded (by some constant
$M=M(d,p)>0$, e.g. $M=d^{p/2}$), it follows that $C_{k}^{n}(z)=1$ if $z\geq M$
and $n$ is sufficiently large (recall that we must let first $n\to\infty$ and
then $k\to\infty$, so we can assume $n\geq k$).

It follows that

$\frac{1}{n^{1-\frac{1}{d}}}\int_{0}^{\infty}\left(\mathbb{E}\left[C_{k}^{n}(z)\right]-1\right)dz\geq-\frac{M}{n^{1-\frac{1}{d}}}\to
0\quad\text{ as $n\to\infty$.}$

To obtain an upper bound we use Lemma 2.4 on each $G^{n}$ – we can assume
$k\geq 2$ and $n\geq k$. Given the sets $C_{i}$, for $i=1\ldots,m$ with $m\leq
n/k$, we choose elements $r_{i}\in C_{i}$ such that
$b_{i}:=\mathsf{n}_{G^{n}}(r_{i})\in C_{i}$ and
$\mathsf{n}_{G^{n}}(b_{i})=r_{i}$. Without loss of generality, we can assume
that $r_{i}\in R^{n}$, $b_{i}\in B^{n}$. We consider the induced subgraph of
$G^{n}_{k}\subseteq G_{k}$ obtained by restriction on the nodes
$R^{n}_{k}:=\left\\{r_{i}\right\\}_{i=1}^{m}$,
$B^{n}_{k}:=\left\\{b_{i}\right\\}_{i=1}^{m}$. With the notation of Lemma 2.4,
we have

$w(i,j)\leq\mathsf{d}_{\mathbb{T}^{d}}(r_{i},b_{j})^{p},$

hence

$\frac{1}{n^{1-\frac{1}{d}}}\int_{0}^{\infty}\left(\mathbb{E}\left[C_{k}^{n}(z)\right]-1\right)dz\leq\mathcal{C}_{MST}(G^{n}_{k}).$

We then use Lemma 2.5 (in fact applied on the metric space $\mathbb{T}^{d}$)
to obtain that, for some constant $C=C(p)>0$,

$\mathcal{C}_{MST}(G^{n}_{k})\leq
C\left(\mathcal{C}_{MST}(R^{n}_{k})+\sum_{i=1}^{m}\mathsf{d}_{\mathbb{T}^{d}}(r_{i},b_{i})^{p}\right),$

where only one summation appears since
$\mathsf{n}_{G^{n}_{k}}(b_{i})=\mathsf{n}_{G}(b_{i})=r_{i}$. Bounding from
above the distance on $\mathbb{T}^{d}$ with the Euclidean distance, and using
Remark (2.6), we have the inequality, for some constant $C=C(d,p)>0$,

$\mathcal{C}_{MST}(R^{n}_{k})+\sum_{i=1}^{m}\mathsf{d}_{\mathbb{T}^{d}}(r_{i},b_{i})^{p}\leq
Cm^{1-p/d}+\sum_{i=1}^{m}\min_{j=1,\ldots,n}|r_{i}-Y_{j}|^{p},$

where we also used that $b_{i}=\mathsf{n}_{G^{n}}(r_{i})$. We finally apply
(2.8) with $x=r_{i}$ and the i.i.d. uniform random variables
$(Y_{j})_{j=1}^{n}$ to conclude that, again for some further constant
$C=C(d,p)>0$,

$\mathbb{E}\left[\mathcal{C}_{MST}(R^{n}_{k},B^{n}_{k})\right]\leq
C\left(m^{1-p/d}+mn^{-p/d}\right)\leq
C\left(\left(\frac{n}{k}\right)^{1-p/d}+\frac{n}{k}n^{-p/d}\right).$

Dividing by $n^{1-p/d}$ and letting first $n\to\infty$ and then $k\to\infty$
gives the thesis.∎

To transfer the result from the torus $\mathbb{T}^{d}$ to the cube
$[0,1]^{d}$, we use the fact that points in $[0,1]^{d}$ can be projected to
$\mathbb{T}^{d}$, and $\mathsf{d}_{\mathbb{T}^{d}}(x,y)\leq|x-y|$, so that,
for any $p>0$, $R$, $B\subseteq[0,1]^{d}$,

$\mathcal{C}_{MST}^{p}(R,B|\mathbb{T}^{d})\leq\mathcal{C}_{MST}^{p}(R,B),$

for any set of points $R$, $B\subseteq[0,1]^{d}$, where
$\mathcal{C}_{MST}^{p}(R,B|\mathbb{T}^{d})$ denotes the MST cost functional on
$\mathbb{T}^{d}$. Letting $p\to\infty$ yields also
$\mathcal{C}_{MST}^{\infty}(R,B|\mathbb{T}^{d})\leq\mathcal{C}_{MST}^{\infty}(R,B)$.
A converse inequality is the following one.

######  Lemma 4.4.

If $\delta\in(0,1/2)$ is such that
$\mathcal{C}_{MST}^{\infty}(R,B)\leq\delta$, then, for every $p>0$,

$\mathcal{C}_{MST}^{p}(R,B)\leq\mathcal{C}_{MST}^{p}(R,B|\mathbb{T}^{d})+\mathcal{C}_{MST}^{p}(R_{\delta},B_{\delta}),$

where $R_{\delta}=R\setminus[\delta,1-\delta]^{d}$,
$B_{\delta}=B\setminus[\delta,1-\delta]^{d}$.

###### Proof.

Indeed, let $T$ be a MST for $R$, $B$ projected on $\mathbb{T}^{d}$. The
assumption gives that for every $\left\\{r,b\right\\}\in T$, since
$|r-b|\leq\delta$, it must be $\mathsf{d}_{\mathbb{T}^{d}}(r,b)=|r-b|$ if
$r\in R\setminus R_{\delta}$ or $b\in B\setminus B_{\delta}$. Therefore, the
only obstacle to bound $\mathcal{C}_{MST}^{p}(R,B)$ from above by
$\mathcal{C}_{MST}^{p}(R,B|\mathbb{T}^{d})$ is due to edges
$\left\\{r,b\right\\}\in T$ with $r\in R_{\delta}$ and $b\in B_{\delta}$, for
which $\mathsf{d}_{\mathbb{T}^{d}}(r,b)$ may be much smaller than $|r-b|$.
However, removing all these edges and adding all the edges of a bipartite
Euclidean MST over $R_{\delta}$, $B_{\delta}$ yields a connected graph and the
desired upper bound. ∎

We combine the above lemma with the following asymptotic upper bounds.

######  Lemma 4.5.

For $n\geq 1$, let $R^{n}=\left\\{X_{i}\right\\}_{i=1}^{n_{R}}$,
$B^{n}=\left\\{Y_{i}\right\\}_{i=1}^{n_{B}}$ be (jointly) i.i.d. uniformly
distributed on $[0,1]^{d}$ with $n_{R}+n_{B}=n$ and

$\lim_{n\to\infty}\frac{n_{R}}{n}=\alpha_{R}\in(0,1),\quad\lim_{n\to\infty}\frac{n_{B}}{n}=\alpha_{B}=1-\alpha_{R}.$

Then, for every $p>0$, there exists a constant $C=C(d,p,\alpha_{R})>0$ such
that, for $n$ large enough,

$\mathbb{E}\left[\mathcal{C}_{MST}^{p}\left(R^{n}\right)\right]\leq
Cn^{1-p/d},\quad\text{and}\quad\mathbb{E}\left[\mathcal{C}_{MST}^{p}\left(R^{n},B^{n}\right)\right]\leq
Cn^{1-p/d},$

as well as, for some constant $C=C(d,q,\alpha_{R})>0$,

$\mathbb{E}\left[\left(\mathcal{C}_{MST}^{\infty}\left(R^{n}\right)\right)^{q}\right]\leq
C\left(\frac{\log
n}{n}\right)^{q/d},\quad\mathbb{E}\left[\left(\mathcal{C}_{MST}^{\infty}\left(R^{n},B^{n}\right)\right)^{q}\right]\leq
C\left(\frac{\log n}{n}\right)^{q/d},$

and finally, for every $a>0$, there exists $C=C(d,a,\alpha_{R})>0$, such that
for $n$ large enough,

$P(\mathcal{C}_{MST}^{\infty}\left(R^{n}\right)>C(\log(n)/n)^{1/d})\leq\frac{C}{n^{a}},\quad
P(\mathcal{C}_{MST}^{\infty}\left(R^{n},B^{n}\right)>C(\log(n)/n)^{1/d})\leq\frac{C}{n^{a}}.$
(4.6)

###### Proof.

This follows from an application of the space-filling curve technique:
consider $\gamma:[0,1]\to[0,1]^{d}$ such that the push-forward of the uniform
measure on $[0,1]^{d}$ is the uniform measure on $[0,1]^{d}$ and it is Hölder
continuous with exponent $1/d$, i.e.,

$C_{\gamma}:=\sup_{s\neq t}\frac{|\gamma(t)-\gamma(s)|^{1/d}}{|t-s|}<\infty.$

While many constructions for $d=2$ are historically well-known, the case of
general $d$ is established in detail e.g. in [29]. Let then
$\left(Z_{i}\right)_{i=1}^{m}$ be i.i.d. uniform on $[0,1]$, so that
$\left(\gamma(Z_{i})\right)_{i=1}^{m}$ are i.i.d. on $[0,1]^{d}$. Consider the
order statistics

$Z_{(1)}=\min_{i=1,\ldots,m}Z_{i}\leq Z_{(2)}\leq\ldots\leq
Z_{(m)}=\max_{i=1,\ldots,m}Z_{i}$

and let $T$ be the connected graph on
$\left\\{\gamma(Z_{i})\right\\}_{i=1}^{m}$ with edges

$\left\\{\left\\{\gamma(Z_{(i)}),\gamma(Z_{(i+1)})\right\\}\,:\,i=1,\ldots,m-1\right\\}.$

We have

$\mathcal{C}_{MST}^{p}\left(\left(\gamma(Z_{i})\right)_{i=1}^{m}\right)\leq\sum_{i=1}^{m-1}|\gamma(Z_{(i+1)})-\gamma(Z_{(i)})|^{p}\leq
C_{\gamma}\sum_{i=1}^{m-1}|Z_{(i+1)}-Z_{(i)}|^{p}.$

The law of each $Z_{(i+1)}-Z_{(i)}$ is beta $B(1,n)$, so that, for every
$q\in\mathbb{N}$,

$\mathbb{E}\left[|Z_{(i+1)}-Z_{(i)}|^{q}\right]=\prod_{r=0}^{q-1}\frac{r+1}{m+r+1}\leq
C(q)m^{-q}.$

Bounding the $p$-th moment with the $\left\lceil p\right\rceil$-th moment
gives that, for $p>0$, there exists a constant $C(p)$ such that, for every $m$
and $i$,

$\mathbb{E}\left[|Z_{(i+1)}-Z_{(i)}|^{p}\right]\leq C(p)m^{-p}$

The first inequality of the thesis thus follows by summation upon
$i=1\ldots,m-1$ and letting $m=n_{R}$. For the second inequality, we use Lemma
2.5 and (2.8). The remaining inequalities follow analogously, noticing that

$\max_{i=1,\ldots,m-1}|Z_{(i+1)}-Z_{(i)}|=\max_{i=1,\ldots,m}|Z_{i}-\mathsf{n}(Z_{i})|=M^{m},$

with the notation of Proposition 2.9. ∎

The following result entails that the expectation of the bipartite Euclidean
minimum spanning tree cost on $\mathbb{T}^{d}$ and on the cube $[0,1]^{d}$ are
much closer than the rate $n^{1-p/d}$.

######  Proposition 4.6.

For $n\geq 1$, let $R^{n}=\left\\{X_{i}\right\\}_{i=1}^{n_{R}}$,
$B^{n}=\left\\{Y_{i}\right\\}_{i=1}^{n_{B}}$ be (jointly) i.i.d. uniformly
distributed on $[0,1]^{d}$ with $n_{R}+n_{B}=n$ and

$\lim_{n\to\infty}\frac{n_{R}}{n}=\alpha_{R}\in(0,1),\quad\lim_{n\to\infty}\frac{n_{B}}{n}=\alpha_{B}=1-\alpha_{R}.$

Then, for every $p>0$, there exists a constant $C=C(p,d)>0$ such that, for $n$
large enough,

$\mathbb{E}\left[\mathcal{C}_{MST}^{p}(R^{n},B^{n})\right]-\mathbb{E}[\mathcal{C}_{MST}^{p}(R^{n},B^{n}|\mathbb{T}^{d})]\leq
Cn^{1-(p+1)/d}(\log n)^{(p+1)/d}.$

In particular, for every $p<d$,

$\lim_{n\to\infty}\frac{\mathbb{E}\left[\mathcal{C}_{MST}^{p}(R^{n},B^{n})\right]}{n^{1-p/d}}=\beta_{bMST}(p,d)$

with $\beta_{bMST}(p,d)$ as in Theorem 1.2.

###### Proof.

Let $C>0$ be as in (4.6) with $a>p/d$ and let $\delta=C(\log(n)/n)^{1/d}$.
Since both $n_{R}$ and $n_{B}$ grow linearly with $n\to\infty$, an application
of Lemma 2.8 as in the proof of Proposition 2.9 ensures that with probability
larger than $1-C/n^{a}$, for every fixed $a>0$, in particular for $a>p/d$ (and
a suitable constant $C>0$) all cubes $Q$ with $|Q|=\delta^{d}$ have non-empty
intersections both with $R^{n}$ and $B^{n}$. Let $E$ the event where both
these conditions occur as well as
$\mathcal{C}_{MST}^{\infty}(R^{n},B^{n})\leq\delta$. In the event $E$, we may
apply Lemma 4.4, otherwise we simply bound
$\mathcal{C}_{MST}^{p}(R^{n},B^{n})\leq nd^{p/2}$ and use the fact that
$P(E^{c})\leq C/n^{a}$ for $a$ arbitrary large.

We are then reduced to bound from above

$\mathbb{E}\left[\mathcal{C}_{MST}^{p}\left(R^{n}_{\delta},B^{n}_{\delta}\right)I_{E}\right]$

where $R^{n}_{\delta}=R^{n}\setminus[\delta,1-\delta]^{d}$,
$B^{n}_{\delta}=B^{n}\setminus[\delta,1-\delta]^{d}$. We decompose
$[0,1]^{d}\setminus[\delta,1-\delta]^{d}$ into $\left(Q_{i}\right)_{i=1}^{m}$,
cubes with side length $\delta$, with $m\leq C\delta^{-(d-1)}$, for some
$C=C(d)>0$. We consider a bipartite Euclidean minimum spanning tree
$T^{n}_{i}$ on $R^{n}_{i}:=R^{n}\cap Q_{i}$, $B^{n}_{i}:=B^{n}\cap Q_{i}$ –
both are non empty if the event $E$ occurs – and then add $m-1$ edges, each
with one node in a cube and an adjacent one, to connect all these trees (again
this is possible since $E$ occurs). This construction leads to a bipartite
spanning tree on $R^{n}_{\delta}$, $B^{n}_{\delta}$, so that, in $E$,

$\mathcal{C}_{MST}^{p}\left(R^{n}_{\delta},B^{n}_{\delta}\right)\leq\sum_{i=1}^{m}\mathcal{C}_{MST}^{p}\left(R^{n}_{i},B^{n}_{i}\right)+m\delta^{p}.$

Taking expectation and rescaling from the cube $Q_{i}$ to $[0,1]^{d}$, we
bound each term in the sum using Lemma 4.5, writing
$N_{R}(Q_{i})=|R^{n}_{i}|$, $N_{B}(Q_{i})=|B^{n}_{i}|$, that are independent
random variables with binomial laws with common parameters $(n,\delta^{d})$.
It follows that

$\begin{split}\mathbb{E}\left[\mathcal{C}_{MST}^{p}\left(R^{n}_{i},B^{n}_{i}\right)I_{E}\right]&\leq\delta^{p}\mathbb{E}\left[\mathcal{C}_{MST}^{p}\left(R^{n}_{i},B^{n}_{i}\right)I_{\left\\{N_{R}(Q_{i})>0,N_{B}(Q_{i})>0\right\\}}\right]\\\
&\leq
C\delta^{p}\left(\mathbb{E}\left[N_{R}(Q_{i})^{1-p/d}\right]+\mathbb{E}\left[N_{B}(Q_{i})\right]\mathbb{E}\left[N_{R}(Q_{i})^{-p/d}I_{\left\\{N_{R}(Q_{i})>0\right\\}}\right]\right)\\\
&\leq C\delta^{p}\log n,\end{split}$

having used that

$\mathbb{E}\left[N_{R}(Q_{i})^{1-p/d}\right]\leq\mathbb{E}\left[N_{R}(Q_{i})\right]^{1-p/d}\leq
C(\log n)^{1-p/d}$

and

$\mathbb{E}\left[N_{R}(Q_{i})^{-p/d}I_{\left\\{N_{R}(Q_{i})>0\right\\}}\right]\leq
1.$

It follows that, for some (other) constant $C=C(p,d)>0$,

$\mathbb{E}\left[\mathcal{C}_{MST}^{p}\left(R^{n}_{i},B^{n}_{i}\right)I_{E}\right]\leq
Cm\delta^{p}\log n=C\delta^{p-d+1}\log n,$

that eventually gives the thesis. ∎

We end the proof of Theorem 1.2 with a concentration result to improve from
convergence of expectations to complete convergence.

######  Proposition 4.7.

Let $d\geq 1$. For $n\geq 1$, let
$R^{n}=\left\\{X_{i}\right\\}_{i=1}^{n_{R}}$,
$B^{n}=\left\\{Y_{i}\right\\}_{i=1}^{n_{B}}$ be (jointly) i.i.d. uniformly
distributed on $[0,1]^{d}$ with $n_{R}+n_{B}=n$ and

$\lim_{n\to\infty}\frac{n_{R}}{n}=\alpha_{R}\in(0,1),\quad\lim_{n\to\infty}\frac{n_{B}}{n}=\alpha_{B}=1-\alpha_{R}.$

Then, for every $p\in(0,d/2)$ if $d\in\left\\{1,2\right\\}$ or any $p>0$ if
$d\geq 3$, complete convergence holds:

$\lim_{n\to\infty}\frac{\mathcal{C}_{MST}^{p}(R^{n},B^{n})-\mathbb{E}\left[\mathcal{C}_{MST}^{p}(R^{n},B^{n})\right]}{n^{1-p/d}}=0.$

###### Proof.

Consider the function

$\left([0,1]^{d}\right)^{n_{R}+n_{B}}\ni(x,y)=(x_{1},\ldots,x_{n_{R}},y_{1},\ldots,y_{n_{B}})\mapsto
f(x,y)=\mathcal{C}_{MST}^{p}\left(\left\\{x_{i}\right\\}_{i=1}^{n_{R}},\left\\{y_{j}\right\\}_{j=1}^{n_{B}}\right).$

We argue separately for $p<1$ and $p\geq 1$. In the former case, if $(x,y)$,
$(x^{\prime},y^{\prime})\in\left([0,1]^{d}\right)^{n_{R}+n_{B}}$ differ only
on a single coordinate, say for simplicity $x_{1}\neq x_{1}^{\prime}$, then,
letting $T$ denote the Euclidean bipartite minimum spanning tree on
$\left\\{x_{i}\right\\}_{i=1}^{n_{R}}$,
$\left\\{y_{j}\right\\}_{j=1}^{n_{B}}$,

$\begin{split}f(x^{\prime},y^{\prime})&\leq
f(x,y)+\sum_{\left\\{y_{j},x_{1}\right\\}\in
T}|y_{j}-x_{1}^{\prime}|^{p}-|y_{j}-x_{1}|^{p}\\\ &\leq
f(x,y)+\sum_{\left\\{y_{j},x_{1}\right\\}\in
T}|x_{1}-x_{1}^{\prime}|^{p}\quad\text{(by the triangle inequality, since
$p\leq 1$)}\\\ &\leq f(x,y)+\deg_{T}(x_{1})|x_{1}-x^{\prime}_{1}|^{p}\\\ &\leq
f(x,y)+\Delta(T)d^{p/2},\end{split}$

where $\Delta(T)$ denote the maximum degree of $T$. Arguing symmetrically, we
obtain

$|f(x,y)-f(x^{\prime},y^{\prime})|\leq\Delta(T)d^{p/2}+\Delta(T^{\prime})d^{p/2}.$

By Lemma A.1 with $E_{i}=[0,1]^{d}$ and $g_{i}(x,y)=\Delta(T)d^{p/2}$ (for
every $i=1,\ldots,n$) we obtain, for every $q\geq 2$, that there exists
$C=C(q)>0$ such that

$\begin{split}\mathbb{E}\left[\left|\mathcal{C}_{MST}^{p}\left(R^{n},B^{n}\right)-\mathbb{E}\left[\mathcal{C}_{MST}^{p}\left(R^{n},B^{n}\right)\right]\right|^{q}\right]&\leq
Cn^{q/2}\mathbb{E}\left[\left(\Delta(T^{n})d^{p/2}\right)^{q}\right]\\\ &\leq
C^{\prime}n^{q/2}(\log n)^{q},\end{split}$

where we used (3.1) and $C^{\prime}=C(d,q,\alpha_{R},\alpha_{b})>0$ is a
constant. Dividing both sides by $n^{q(1-p/d)}$ and using Markov inequality
yields, for every $\epsilon>0$,

$P\left(\left|\mathcal{C}_{MST}^{p}\left(R^{n},B^{n}\right)-\mathbb{E}\left[\mathcal{C}_{MST}^{p}\left(R^{n},B^{n}\right)\right]\right|/n^{1-p/d}>\epsilon\right)\leq
C^{\prime}\epsilon^{-q}n^{q(p/d-1/2)}(\log n)^{q},$

that is summable if $p/d-1/2<0$, i.e., $p<d/2$, and $q$ is sufficiently large.

In the case $p\geq 1$, we use the fact that $f$ is Lipschitz (being minimum of
Lipschitz functions) with a.e. derivative given by

$\nabla_{x_{i}}f(x,y)=\sum_{\begin{subarray}{c}j=1,\ldots,n_{B}\\\
\left\\{x_{i},y_{j}\right\\}\in
T\end{subarray}}p|x_{i}-y_{j}|^{p-2}(x_{i}-y_{j}),$
$\nabla_{y_{j}}f(x,y)=\sum_{\begin{subarray}{c}i=1,\ldots,n_{R}\\\
\left\\{x_{i},y_{j}\right\\}\in
T\end{subarray}}p|x_{i}-y_{j}|^{p-2}(x_{i}-y_{j}),$

We bound from above, using Cauchy-Schwartz inequality

$|\nabla_{x_{i}}f(x,y)|^{2}\leq
p^{2}\Delta(T)\sum_{\begin{subarray}{c}j=1,\ldots,n_{B}\\\
\left\\{x_{i},y_{j}\right\\}\in T\end{subarray}}|x_{i}-y_{j}|^{2(p-1)}.$

It follows that the (Euclidean) norm of the derivative is bounded above by

$|\nabla f(x,y)|^{2}\leq 2p^{2}\Delta(T)\mathcal{C}_{MST}^{2(p-1)}(x,y)\leq
2p^{2}\Delta(T)\left(\mathcal{C}_{MST}^{\infty}(x,y)\right)^{2(p-1)}n,$

where we used the fact that the minimum spanning tree $T$ does not depend on
the choice of $p$, see Remark 2.3. For every $q>0$ Lemma 3.2 and Lemma 4.5
yield that, for some constant $C=C(d,p,q)>0$ and $n$ sufficiently large,

$\begin{split}\mathbb{E}\left[\Delta(T^{n})^{q/2}\left(\mathcal{C}_{MST}^{\infty}(R^{n},B^{n})\right)^{q(p-1)}\right]&\leq\mathbb{E}\left[\Delta(T^{n})^{q}\right]^{1/2}\mathbb{E}\left[\left(\mathcal{C}_{MST}^{\infty}(R^{n},B^{n})\right)^{2q(p-1)}\right]^{1/2}\\\
&\leq C\log(n)^{q/2}\left(\frac{\log n}{n}\right)^{q(p-1)/d}\end{split}$

It follows that (possibly for a larger constant $C$)

$\mathbb{E}\left[|\nabla
f(\left\\{X_{i}\right\\}_{i=1}^{n},\left\\{Y_{i}\right\\}_{i=1})|^{q}\right]\leq
C\log(n)^{q\left(1/2+(p-1)/d\right)}n^{q(1/2-(p-1)/d)}.$

Poincaré inequality for the uniform measure on the unit cube, see e.g. the
argument in [30, Prop. 2.8], gives that, for some constant $C=C(q)>0$,

$\mathbb{E}\left[\left|f(\left\\{X_{i}\right\\}_{i=1}^{n},\left\\{Y_{i}\right\\}_{i=1})-\mathbb{E}\left[f(\left\\{X_{i}\right\\}_{i=1}^{n},\left\\{Y_{i}\right\\}_{i=1})\right]\right|^{q}\right]\leq
C(q)\mathbb{E}\left[|\nabla
f(\left\\{X_{i}\right\\}_{i=1}^{n},\left\\{Y_{i}\right\\}_{i=1})|^{q}\right],$

thus using Markov inequality, for every $\epsilon>0$, we have

$P\left(\left|\mathcal{C}_{MST}^{p}\left(R^{n},B^{n}\right)-\mathbb{E}\left[\mathcal{C}_{MST}^{p}\left(R^{n},B^{n}\right)\right]\right|/n^{1-p/d}>\epsilon\right)\leq
C\frac{(\log n)^{q\left(1/2+(p-1)/d\right)}}{\epsilon^{q}n^{q(1/2-1/d)}},$

which is summable if $q$ is large enough and $d\geq 3$. ∎

##  Appendix A A concentration inequality in $L^{q}$.

McDiarmid inequality [31] is a simple but effective concentration inequality
often used in random combinatorial optimization problems. An interpretation is
that the oscillations of a function of many independent random variables are
bounded by its Lipschitz norm (with respect to a Hamming-type distance). The
usual proof relies concentration inequalities for discrete time exponential
martingales. In this section we show an analogous result where we replace the
Lipschitz condition with a “Sobolev” one and use Burkholder-Gundy inequalities
instead.

######  Lemma A.1.

Let $\left((E_{i},\mathcal{E}_{i})\right)_{i=1}^{n}$ be measurable spaces, set
$E=\prod_{i=1}^{n}E_{i}$ and let

$f:E\to\mathbb{R},\quad g_{i}:E\to[0,\infty]\quad\text{for $i=1,\ldots,n$,}$

be such that, for every $i\in\left\\{1,\ldots,n\right\\}$, for every $x$,
$x^{\prime}\in E$ with

$x=(x_{1},\ldots,x_{i},\ldots,x_{n})\quad
x^{\prime}=(x_{1},\ldots,x^{\prime}_{i},\ldots,x_{n})$

then

$\left|f(x)-f(x^{\prime})\right|\leq g_{i}(x)+g_{i}(x^{\prime}).$

For every $q\geq 2$, there exists $C=C(q)>0$ such that, if
$X=(X_{i})_{i=1}^{n}$ are independent random variables, with $X_{i}:\Omega\to
E_{i}$, then

$\mathbb{E}\left[|f(X)-\mathbb{E}\left[f(X)\right]|^{q}\right]\leq
C(q)n^{q/2-1}\sum_{i=1}^{n}\mathbb{E}\left[g_{i}(X)^{q}\right].$

###### Proof.

Write $\mathbb{E}_{i}$ for the conditional expectation with respect to the
variables $\left(X_{j}\right)_{j\leq i}$. In particular,
$\mathbb{E}_{0}=\mathbb{E}$ and $\mathbb{E}_{n}$ is the identity operator. We
write $f(X)-\mathbb{E}\left[f(X)\right]$ as a sum of martingale differences

$f(X)-\mathbb{E}\left[f(X)\right]=\sum_{i=1}^{n}\mathbb{E}_{i}\left[f(X)\right]-\mathbb{E}_{{i-1}}\left[f(X)\right].$

Burkholder-Gundy inequality [32] gives, for some constant $C=C(q)\geq 0$,

$\mathbb{E}\left[|f(X)-\mathbb{E}\left[f(X)\right]|^{q}\right]\leq
C(q)\mathbb{E}\left[\left(\sum_{i=1}^{n}\left|\mathbb{E}_{i}\left[f(X)\right]-\mathbb{E}_{{i-1}}\left[f(X)\right]\right|^{2}\right)^{q/2}\right].$
(A.1)

To simplify notation, we introduce a copy of the independent variables
$(X_{i}^{\prime})_{i=1}^{n}$ defined on a different space $\Omega^{\prime}$,
and write $\mathbb{E}^{\prime}$ for expectation with respect to such
variables, so that, because of independence, for every $i=0,\ldots,n$,

$\mathbb{E}_{i}\left[f(X)\right]=\mathbb{E}^{\prime}\left[f(X_{1},\ldots,X_{i},X^{\prime}_{i+1},\ldots
X^{\prime}_{n})\right].$
$\begin{split}&\left|\mathbb{E}_{i}\left[f(X)\right]-\mathbb{E}_{i-1}\left[f(X)\right]\right|\\\
&\quad=\left|\mathbb{E}^{\prime}\left[f(X_{1},\ldots,X_{i},X^{\prime}_{i+1},\ldots
X^{\prime}_{n})\right]-\mathbb{E}^{\prime}\left[f(X_{1},\ldots,X_{i-1},X^{\prime}_{i},\ldots
X^{\prime}_{n})\right]\right|\\\
&\quad\leq\mathbb{E}^{\prime}\left[\left|f(X_{1},\ldots,X_{i},X^{\prime}_{i+1},\ldots
X^{\prime}_{n})-f(X_{1},\ldots,X_{i-1},X^{\prime}_{i},\ldots
X^{\prime}_{n})\right|\right]\\\
&\quad\leq\mathbb{E}^{\prime}\left[g_{i}(X_{1},\ldots,X_{i},X^{\prime}_{i+1},\ldots,X^{\prime}_{n})+g_{i}(X_{1},\ldots,X_{i-1},X^{\prime}_{i},\ldots,X^{\prime}_{n})\right]\\\
&\quad=\mathbb{E}_{i}\left[g_{i}\right]+\mathbb{E}_{{i-1}}\left[g_{i}\right].\end{split}$

Using these inequalities in (A.1) yields

$\begin{split}\mathbb{E}\left[|f(X)-\mathbb{E}\left[f(X)\right]|^{q}\right]&\leq
C(q)\mathbb{E}\left[\left(\sum_{i=1}^{n}\left(\mathbb{E}_{i}\left[g_{i}\right]+\mathbb{E}_{{i-1}}\left[g_{i}\right]\right)^{2}\right)^{q/2}\right]\\\
&\leq
C(q)n^{q/2-1}\sum_{i=1}^{n}\mathbb{E}\left[\left(\mathbb{E}_{i}\left[g_{i}\right]+\mathbb{E}_{{i-1}}\left[g_{i}\right]\right)^{q}\right]\\\
&\leq\tilde{C}(q)n^{q/2-1}\sum_{i=1}^{n}\mathbb{E}\left[\mathbb{E}_{i}\left[g_{i}\right]^{q}+\mathbb{E}_{{i-1}}\left[g_{i}\right]^{q}\right]\\\
&\leq
2\tilde{C}(q)n^{q/2-1}\sum_{i=1}^{n}\mathbb{E}\left[g_{i}^{q}\right],\end{split}$

hence the thesis. ∎

## References

  * [1] R.. Graham and Pavol Hell  “On the History of the Minimum Spanning Tree Problem”  In _IEEE Ann. Hist. Comput._ 7.1, 1985, pp. 43–57  DOI: 10.1109/MAHC.1985.10011
  * [2] Nicos Christofides  “Worst-case analysis of a new heuristic for the travelling salesman problem”, 1976
  * [3] L. Kou, G. Markowsky and L. Berman  “A fast algorithm for Steiner trees”  In _Acta Informatica_ 15.2, 1981, pp. 141–145  DOI: 10.1007/BF00288961
  * [4] T. Asano, B. Bhattacharya, M. Keil and F. Yao  “Clustering algorithms based on minimum and maximum spanning trees”  In _Proceedings of the fourth annual symposium on Computational geometry_ , SCG ’88  New York, NY, USA: Association for Computing Machinery, 1988, pp. 252–257  DOI: 10.1145/73393.73419
  * [5] Bernard Chazelle  “A minimum spanning tree algorithm with inverse-Ackermann type complexity”  In _Journal of the ACM (JACM)_ 47.6 ACM New York, NY, USA, 2000, pp. 1028–1047
  * [6] David R. Karger, Philip N. Klein and Robert E. Tarjan  “A randomized linear-time algorithm to find minimum spanning trees”  In _J. ACM_ 42.2, 1995, pp. 321–328  DOI: 10.1145/201019.201022
  * [7] A.. Frieze  “On the value of a random minimum spanning tree problem”  In _Discrete Applied Mathematics_ 10.1, 1985, pp. 47–56  DOI: 10.1016/0166-218X(85)90058-7
  * [8] Jillian Beardwood, J.. Halton and J.. Hammersley  “The shortest path through many points” Publisher: Cambridge University Press  In _Mathematical Proceedings of the Cambridge Philosophical Society_ 55.4, 1959, pp. 299–327  DOI: 10.1017/S0305004100034095
  * [9] J. Steele  “Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted Edges” Publisher: Institute of Mathematical Statistics  In _The Annals of Probability_ 16.4, 1988, pp. 1767–1787  URL: https://www.jstor.org/stable/2243991
  * [10] D. Aldous and J.. Steele  “Asymptotics for Euclidean minimal spanning trees on random points”  In _Probability Theory and Related Fields_ 92.2, 1992, pp. 247–258  DOI: 10.1007/BF01194923
  * [11] J.. Yukich  “Asymptotics for weighted minimal spanning trees on random points”  In _Stochastic Processes and their Applications_ 85.1, 2000, pp. 123–138  DOI: 10.1016/S0304-4149(99)00068-X
  * [12] J. Steele  “Subadditive Euclidean Functionals and Nonlinear Growth in Geometric Probability” Publisher: Institute of Mathematical Statistics  In _The Annals of Probability_ 9.3, 1981, pp. 365–376  DOI: 10.1214/aop/1176994411
  * [13] Joseph E. Yukich  “Probability Theory of Classical Euclidean Optimization Problems”, Lecture Notes in Mathematics  Berlin Heidelberg: Springer-Verlag, 1998  DOI: 10.1007/BFb0093472
  * [14] Florin Avram and Dimitris Bertsimas  “The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model: A Unified Approach” Publisher: Institute of Mathematical Statistics  In _The Annals of Applied Probability_ 2.1, 1992, pp. 113–130  DOI: 10.1214/aoap/1177005773
  * [15] Mathew D. Penrose  “The random minimal spanning tree in high dimensions” Publisher: Institute of Mathematical Statistics  In _The Annals of Probability_ 24.4, 1996, pp. 1903–1925  DOI: 10.1214/aop/1041903210
  * [16] J. Steele  “Minimal Spanning Trees for Graphs with Random Edge Lengths”  In _Mathematics and Computer Science II_ , Trends in Mathematics  Basel: Birkhäuser, 2002, pp. 223–245  DOI: 10.1007/978-3-0348-8211-8˙14
  * [17] A.. Frieze and C… McDiarmid  “On random minimum length spanning trees”  In _Combinatorica_ 9.4, 1989, pp. 363–374  DOI: 10.1007/BF02125348
  * [18] Sergio Caracciolo, Andrea Di Gioacchino, Marco Gherardi and Enrico M. Malatesta  “Solution for a bipartite Euclidean traveling-salesman problem in one dimension” Publisher: American Physical Society  In _Phys. Rev. E_ 97.5, 2018, pp. 052109  DOI: 10.1103/PhysRevE.97.052109
  * [19] Riccardo Capelli, Sergio Caracciolo, Andrea Di Gioacchino and Enrico M. Malatesta  “Exact value for the average optimal cost of the bipartite traveling salesman and two-factor problems in two dimensions” Publisher: American Physical Society  In _Phys. Rev. E_ 98.3, 2018, pp. 030101  DOI: 10.1103/PhysRevE.98.030101
  * [20] M. Ajtai, J. Komlós and G. Tusnàdy  “On optimal matchings”  In _Combinatorica_ 4.4, 1984, pp. 259–264  DOI: 10.1007/BF02579135
  * [21] Michel Talagrand  “The Ajtai-Komlos-Tusnady Matching Theorem for General Measures”  In _Probability in Banach Spaces, 8: Proceedings of the Eighth International Conference_ , Progress in Probability  Boston, MA: Birkhäuser, 1992, pp. 39–54  DOI: 10.1007/978-1-4612-0367-4˙2
  * [22] Michel Talagrand  “Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems”, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics  Berlin Heidelberg: Springer-Verlag, 2014  DOI: 10.1007/978-3-642-54075-2
  * [23] Luigi Ambrosio, Federico Stra and Dario Trevisan  “A PDE approach to a 2-dimensional matching problem”  In _Probab. Theory Relat. Fields_ 173.1-2, 2019, pp. 433–477  DOI: 10.1007/s00440-018-0837-x
  * [24] S. Caracciolo, C. Lucibello, G. Parisi and G. Sicuro  “Scaling hypothesis for the Euclidean bipartite matching problem” Publisher: American Physical Society  In _Phys. Rev. E_ 90.1, 2014, pp. 012118  DOI: 10.1103/PhysRevE.90.012118
  * [25] Franck Barthe and Charles Bordenave  “Combinatorial Optimization Over Two Random Point Sets”  In _Séminaire de Probabilités XLV_ , Lecture Notes in Mathematics  Heidelberg: Springer International Publishing, 2013, pp. 483–535  DOI: 10.1007/978-3-319-00321-4˙19
  * [26] Andrea Riva, Sergio Caracciolo and Enrico Malatesta  “The random Minimum Spanning Tree problem”, 2018-2019  URL: http://pcteserver.mi.infn.it/~caraccio/Lauree/Riva.pdf
  * [27] Harry Kesten and Sungchul Lee  “The central limit theorem for weighted minimal spanning trees on random points” Publisher: Institute of Mathematical Statistics  In _Ann. Appl. Probab._ 6.2, 1996, pp. 495–527  DOI: 10.1214/aoap/1034968141
  * [28] Sourav Chatterjee and Sanchayan Sen  “Minimal spanning trees and Stein’s method” Publisher: Institute of Mathematical Statistics  In _Ann. Appl. Probab._ 27.3, 2017, pp. 1588–1645  DOI: 10.1214/16-AAP1239
  * [29] Stephen C Milne  “Peano curves and smoothness of functions”  In _Advances in Mathematics_ 35.2 Academic Press, 1980, pp. 129–157
  * [30] M. Ledoux  “The concentration of measure phenomenon”  American Mathematical Soc., 2001
  * [31] Colin McDiarmid  “On the method of bounded differences”  In _Surveys in combinatorics, 1989 (Norwich, 1989)_ 141, London Math. Soc. Lecture Note Ser.  Cambridge Univ. Press, Cambridge, 1989, pp. 148–188
  * [32] D.. Burkholder and R.. Gundy  “Extrapolation and interpolation of quasi-linear operators on martingales” Publisher: Institut Mittag-Leffler  In _Acta Mathematica_ 124.none, 1970, pp. 249–304  DOI: 10.1007/BF02394573