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 [Reference Graham and Hell17] including approximation algorithms for more complex problems [Reference Christofides13, Reference Kou, Markowsky and Berman20] and cluster analysis [Reference Asano, Bhattacharya, Keil and Yao4].
Its formulation is straightforward: given a weighted undirected graph
$G=(V,E,w)$
with
$w \,:\, E \to (0, \infty )$
, find a subgraph
$T\subseteq E$
that connects all nodes
$V$
and has a minimal total edge cost
\begin{equation*} \sum _{e \in T} w(e),\end{equation*}
thus defining the MST cost functional
$\mathcal{C}_{\text{MST}}(G)$
. Minimality yields that redundant connections can be discarded, so that the resulting subgraph
$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 [Reference Chazelle12], possibly randomised [Reference Karger, Klein and Tarjan18].
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 [Reference Frieze16], 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
\begin{equation} \lim _{n\to \infty } \mathcal{C}_{\text{MST}}(G^n) = \zeta (3) = \sum _{k=1}^\infty \frac{1}{k^3}. \end{equation}
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\gt 0$
. This setting dates back at least to the seminal paper by Beardwood, Halton and Hammersley [Reference Beardwood, Halton and Hammersley8] 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 [Reference Steele28] who proved that, if the Euclidean graph consists of
$n$
nodes, then for every
$0\lt p\lt d$
, almost sure convergence holds
\begin{equation} \lim _{n\to \infty } \frac{ \mathcal{C}_{\text{MST}}(G^n)}{n^{1-p/d}} = \beta _{\text{MST}}(p,d), \end{equation}
where
$\beta _{\text{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 in 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\lt d$
was removed by Aldous and Steele [Reference Aldous and Steele3] and Yukich [Reference Yukich31], so that convergence holds in fact for any
$p\gt 0$
. This result can be seen as an application of a general Euclidean additive functional theory [Reference Steele27, Reference Yukich32]. However, such general methods that work for other combinatorial optimisation 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 [Reference Avram and Bertsimas1], although only in the range
$0\lt p\lt d$
. The latter was used by Penrose [Reference Penrose24], 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 [Reference Steele, Chauvin, Flajolet, Gardy and Mokkadem26], but limited to the case of i.i.d. weights, based on Tutte polynomials.
The 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 [Reference Frieze and McDiarmid15]. 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}$
[Reference Caracciolo, Di Gioacchino, Gherardi and Malatesta11] and
$\sqrt{n \log n }$
[Reference Capelli, Caracciolo, Di Gioacchino and Malatesta9], 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 [Reference Steele27] and its bipartite counterpart, also related to the optimal transport problem [Reference Ajtai, Komlós and Tusnády2, Reference Ambrosio, Stra and Trevisan5, Reference Caracciolo, Lucibello, Parisi and Sicuro10, Reference Talagrand29, Reference Talagrand30]. Barthe and Bordenave proposed a bipartite extension of the Euclidean additive functional theory [Reference Barthe, Bordenave, Donati-Martin, Lejay and Rouault6] that allows to recover an analogue of (1.2) for many relevant combinatorial optimisation problems on bipartite Euclidean random models, although its range of applicability is restricted to
$0\lt p\lt 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 an 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).
1.1. Main results
Our first main result describes precisely the asymptotic maximum degree of an 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\ge 1$
, let
$n \ge 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
\begin{equation*} \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.\end{equation*}
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)\gt 0$
such that
\begin{equation*} \lim _{ n \to \infty } \mathbb {P}\!\left ( C^{-1} \lt \frac {\Delta (T^n)}{\log (n)} \lt C \right ) = 1.\end{equation*}
(Indeed, the structure of the MST does not depend on the specific choice of the exponent
$p\gt 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 \ge 1$
,
$k_R$
,
$k_B \ge 1$
,
$\alpha _R \in (0,1)$
,
\begin{equation*} \begin{split} E\!\left(k_R, k_B, \alpha _R\right) = & \int _{\Theta \!\left(k_R, k_B\right)} \left ( \alpha _R \left|D\!\left(\left \{ b_j \right \}_{j=1}^{k_B}\right)\right| + \alpha _B \left| D\!\left(\left \{ r_i \right \}_{i=1}^{k_R}\right)\right| \right )^{-(k_R+k_B)/d}\cdot \\ & \quad \cdot \left ( \frac{k_R}{\alpha _R} \delta _0(r_1)d b_1 + \frac{k_B}{\alpha _B}d r_1 \delta _0(b_1) \right ) dr_2 \ldots d r_{k_R} db_2 \ldots d b_{k_B},\end{split} \end{equation*}
where
$\alpha _B = 1-\alpha _R$
and we write
\begin{equation} \Theta \!\left(k_R, k_B\right) \subseteq \big({\mathbb{R}}^d\big)^{k_R} \times \big({\mathbb{R}}^d\big)^{k_B}, \end{equation}
for the set of (ordered) points
$\left( \left ( r_i \right )_{i=1}^{k_R}, \left ( b_j \right )_{j=1}^{k_B}\right)$
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
\begin{equation} D(A) = \left \{ x \in{\mathbb{R}}^d\, : \, \mathsf{dist}(A,x) \le 1 \right \}, \end{equation}
and
$|D(A)|$
for its Lebesgue measure. Notice also that the overall integration is performed with respect to the
$d$
-dimensional Lebesgue measure over
$k_R+k_B-1$
variables 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\ge 1$
, let
$n \ge 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
\begin{equation*} \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.\end{equation*}
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
\begin{equation} \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 _{b\text{MST}}(d,p), \end{equation}
and the constant
$\beta _{b\text{MST}}(d,p) \in (0, \infty )$
is given by the series
\begin{equation} \beta _{b\text{MST}}(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\!\left(k_R, k_B, \alpha _R\right). \end{equation}
Moreover, if
$p\lt d/2$
for
$d \in \left \{ 1,2 \right \}$
or
$p\lt d$
for
$d \ge 3$
, convergence is almost sure:
\begin{equation*} \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 _{b\text{MST}}(d,p).\end{equation*}
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 [Reference Riva, Caracciolo and Malatesta25], 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\lt 1$
and just convergence of the expected costs if
$1\le p \lt 2$
– in fact we also have a general upper bound if
$p\ge 2$
(Lemma 4.5).
1.2. Further questions and conjectures
Several extensions of the results contained in this work may be devised, for example by generalising 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\ge d$
. On the other side, we suspect that additivity techniques may yield convergence in (1.5) also in the range
$p \ge 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.,
\begin{equation} \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). \end{equation}
Furthermore, a central limit theorem is known for MST problem [Reference Chatterjee and Sen14, Reference Kesten and Lee19] and it may be interesting to understand the possible role played by the additional fluctuations introduced in bipartite setting for analogue results.
Finally, it may be of interest to strengthen Theorem 1.1, by establishing the limit (e.g. in probability)
\begin{equation*} \lim _{n \to \infty } \frac { \Delta (T^n) }{\log n} = \gamma (d), \end{equation*}
for some constant
$\gamma (d) \in (0, \infty )$
, and further investigating the vertex degree distribution of
$T^n$
.
1.3. 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 [Reference Avram and Bertsimas1, 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}$
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\lt 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
We always consider the space
${\mathbb{R}}^d$
,
$d \ge 1$
, endowed with the Euclidean distance, which we denote with
$|x-y|$
for
$x$
,
$y \in{\mathbb{R}}^d$
. The volume of the unit ball is denoted with
$\omega _d$
. We also use throughout the letter
$C$
to denote constants that may depend upon parameters (such as the dimension
$d$
, exponents
$p$
, etc.), warning the reader that to simplify the notation in some proofs, the same letter may be used in different locations to denote possibly different constants.
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
\begin{equation} \mathcal{C}_{\text{MST}}(G) = \inf \left \{ \sum _{e \in T} w(e)\, : \, \text{$T \subseteq E$ is a connected spanning subgraph} \right \}, \end{equation}
Here and below, connected is in the sense that only edges with finite weight must be considered. We consider only minimisers
$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 minimisers). 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{arg min}\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)\gt 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.,
\begin{equation*} e = \left \{ v, \mathsf {n}(v) \right \} \in \operatorname {arg min}\left \{ w(f)\, : \, v \in f \right \},\end{equation*}
assuming that such node is unique.
The subgraphs
\begin{equation*} G(z) \,:\!=\, \left \{ e \in E \, : \, w(e) \le z \right \}, \quad \text {for $z \ge 0$,}\end{equation*}
are strongly related to the minimum spanning tree on
$G$
, since the execution of Kruskal’s algorithm yields the identity, already observed in [Reference Avram and Bertsimas1],
\begin{equation} \mathcal{C}_{MST}(G) =\int _{0}^{\infty }\left ( C_{G(z)}-1 \right )dz, \end{equation}
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
\begin{equation*} \int _{0}^{\infty }\left ( C_{G(z)}-1 \right )dz= \sum _{z\in J_{-}} z. \end{equation*}
To argue that the right hand side is the cost of an 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).
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
$\{ 1,2,3 \}$
or
$\{ 4,5,6\}$
, the resulting (different) trees have always total weight
$5+9=14$
.
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
\begin{equation*} \mathcal {C}_{\text{MST}}\big(G^\psi \big) = \int _0^\infty \left ( C_{G^\psi (z)} - 1 \right ) d z = \int _0^\infty \left ( C_{G(u)} -1 \right )d \psi (u).\end{equation*}
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$
minimises the functional
\begin{equation} \mathcal{C}_{\text{MST}}^\infty (G) \,:\!=\, \inf \left \{ \max _{e \in T}w(e)\, : \, \text{$T \subseteq E$ is a connected spanning subgraph} \right \}. \end{equation}
A similar argument [Reference Avram and Bertsimas1, 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 \le k \le |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
\begin{equation} w(C_i,C_j) = \inf \left \{ w(e) \, : \, e = \{ x,y\} \in V, x\in C_i, y \in C_j \right \}, \quad \text{for $i$, $j \in \left \{ 1, \ldots, m \right \}$,} \end{equation}
then
\begin{equation} \int _0^\infty \left( C_{k,G(z)} -1 \right) d z \le \mathcal{C}_{\text{MST}}(G_k). \end{equation}
Moreover, for every
$i=1, \ldots, m$
,
$|C_i| \ge k$
, hence
$m \le |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
\begin{equation*} \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.\end{equation*}
We interpret the right hand side above as
$\mathcal{C}_{\text{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)$
.
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_{-}$
. Given
$v \in V$
, we introduce the following rule in order to determine the set
$C_i$
to which
$v$
belongs. Consider the shortest path from the trivial component containing only
$v$
at
$z=0$
towards the root at
$z = \infty$
in the tree-like representation. We focus on the first point where such path merges with a thick line and write
$z_v$
for the corresponding value on the
$z$
-axis and let
$\mathcal{S}_v$
denote the subset of ‘seeds’ among the
$C_i$
’s that are located further from the root (i.e., with smaller
$z$
values) along the thick path, starting from such point (for example, in Fig. 1 we report the construction for
$k=3$
, where we have for
$v=7$
,
$z_7 = 6$
and
$\mathcal{S}_7 = \left \{ \left \{ 1,2,3 \right \}, \left \{ 4,5,6 \right \} \right \}$
). If
$z_v \in J_+$
, then
$v$
already becomes part of a seed of some
$C_i$
, hence the situation is trivial, and we let
$v \in C_i$
. Otherwise the node
$v$
will be assigned to a chosen cluster
$C_i$
among those in
$\mathcal{S}_v$
. We choose to add the vertex
$v$
to the
$C_i \in \mathcal{S}_v$
with smallest label index
$i$
. Our choice ensures that all the connected component of
$v$
in the graph
$G(z_v^-)$
is added to the same
$C_i$
. We highlight that, as long as it is consistent, other choices of
$C_i$
’s would be possible, as such nodes play a role only later in the construction of the MST, when the clusters are already merged. Anyway, the resulting
$C_i$
’s thus well-defined and moreover the induced weight between them defined via (2.4) actually coincides with the weight between the original seeds. Using this fact, to prove (2.5) it is then elementary to check 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(\{ x,y\}) = \mathsf{d}(x,y)^p$
, where
$p\gt 0$
is fixed. If
$V$
,
$R$
,
$B \subseteq X$
, are finite sets and
$p\gt 0$
, we write
\begin{equation*} \mathcal {C}_{\text{MST}}^p(V) \quad \text {and respectively} \quad \mathcal {C}_{\text{MST}}^p(R, B),\end{equation*}
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(\{ x,y\}) = \mathsf{d}(x,y)^p$
, for
$\{ x,y\} \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
\begin{equation*} \left ( \mathcal {C}_{\text{MST}}^p(V) \right )^{1/p} \to \mathcal {C}_{\text{MST}}^\infty (V), \quad \left ( \mathcal {C}_{\text{MST}}^p(R, B) \right )^{1/p} \to \mathcal {C}_{\text{MST}}^\infty (R,B),\end{equation*}
where
$\mathcal{C}_{\text{MST}}^\infty$
is the minimum bottleneck spanning tree cost defined in (2.3) with edge weight given by the distance.
We denote by
\begin{equation*} \mathsf {d}(V,x) = \inf _{v \in V} \mathsf {d}(v,x)\end{equation*}
and
\begin{equation*} \mathsf {d}(R, B) = \max \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 \}\end{equation*}
respectively the distance function from
$V$
and the Hausdorff distance between
$R$
and
$B$
. Clearly,
$\mathcal{C}_{\text{MST}}^p(R \cup B) \le \mathcal{C}_{\text{MST}}^p(R, B)$
. The following lemma provides a sort of converse inequality.
Lemma 2.5.
Let
$p\gt 0$
. There exists a constant
$C = C(p) \in (0, \infty )$
such that, for finite sets
$R$
,
$B \subseteq X$
,
\begin{equation*} \mathcal {C}_{\text{MST}}^p(R, B) \le C \!\left ( \mathcal {C}_{\text{MST}}^p(R) + \sum _{r \in R} \mathsf {d}(B,r)^p + \sum _{b \in B} \mathsf {d}(R,b)^p \right ),\end{equation*}
and, for some constant
$C\gt 0$
,
\begin{equation*} \mathcal {C}_{\text{MST}}^\infty (R,B) \le C\!\left ( \mathcal {C}_{\text{MST}}^\infty (R) + \mathsf {d}(R,B) \right ).\end{equation*}
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) = \big\{ r,r^{\prime} \big\}$
. The triangle inequality gives
\begin{equation*} \mathsf {d}(\mathsf {n}(r), r^{\prime})^p \le \left ( \mathsf {d}(\mathsf {n}(r),r) + \mathsf {d}(r, r^{\prime}) \right )^p \le C\!\left ( \mathsf {d}(\mathsf {n}(r),r)^p + \mathsf {d}(r, r^{\prime})^p \right ),\end{equation*}
for some constant
$C = C(p)\ge 1$
, hence
\begin{equation*} \sum _{ \left \{ r,b \right \} \in S} \mathsf {d}(r,b)^p \le C \!\left ( \sum _{\{ r,r^{\prime}\} \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 )\end{equation*}
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 (see [Reference Steele28]) that, if
$p\lt d$
, there exists a constant
$C =C(d,p)\gt 0$
such that
\begin{equation} \mathcal{C}_{\text{MST}}^p(V) \le C |V|^{1-p/d}, \end{equation}
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)\gt 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\gt 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 an 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) \gt \mathsf{d}(R,B)$
. Then
$S \cap R = \emptyset$
, where
\begin{equation*} S = \left \{ x \in X\, : \, \text { $\mathsf {d}(x,r) \lt \delta -\mathsf {d}(R,B)$ and $\mathsf {d}(x,b)\lt \delta $} \right \}.\end{equation*}
In particular, when
$X = [0,1]^d$
,
$S$
contains a cube
$Q\subseteq [0,1]^d$
with volume
\begin{equation*} |Q| = \left ( \frac { \delta - \mathsf {d}(R,B)}{2 \sqrt {d}} \right )^{d}.\end{equation*}
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) \lt \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
\begin{equation*} \mathsf {d}(\mathsf {n}(r),r^{\prime}) \le \mathsf {d}(\mathsf {n}(r),r) + \mathsf {d}(r,r^{\prime}) \lt \mathsf {d}(R,B) + \delta - \mathsf {d}(R,B) \lt \delta .\end{equation*}
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\ge 0$
and centre
$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 \le \lambda \le \big( |Q|/\omega _d \big)^{1/d}$
, we have
\begin{equation} \mathbb{P}\!\left(\left | x- X_i \right | \gt \lambda \right) = \frac{| Q \setminus B(x, \lambda )| }{|Q|} \ge 1- \omega _d \lambda ^d/ |Q|, \end{equation}
hence, by independence,
\begin{equation*}\mathbb {P}\!\left ( \min _{i=1,\ldots, n}\left | x- X_i \right | \gt \lambda \right ) \ge \left ( 1- \omega _d \lambda ^d/ |Q| \right )^n, \quad \text {for every $x \in {\mathbb {R}}^d$.} \end{equation*}
If
$x \in Q$
, we also have the upper bound (the worst case being
$x$
a vertex of
$Q$
)
\begin{equation*} \mathbb {P}\!\left(\left | x- X_i \right | \gt \lambda \right) \le 1- \omega _d 2^{-d} \lambda ^d/ |Q|,\end{equation*}
hence,
\begin{equation} \mathbb{P}\!\left ( \min _{i=1,\ldots,n} \left | x - X_i \right | \gt \lambda \right ) \le \left ( 1- \omega _d 2^{-d} \lambda ^d/ |Q| \right )^n, \quad \text{for every $x \in Q$.} \end{equation}
Assume
$Q = [0,1]^d$
. The standard layer-cake formula
$\mathbb{E}\!\left [ Z^p \right ] = \int _0^\infty \mathbb{P}(Z\gt \lambda ) p \lambda ^{p-1} d \lambda$
yields, for every
$p\gt 0$
, the existence of a constant
$C =C(d,p)\gt 0$
such that, for every
$n\ge 1$
,
\begin{equation} C^{-1} n^{-p/d} \le \sup _{x \in [0,1]^d} \mathbb{E} \!\left [ \min _{i=1,\ldots,n} \left | x - X_i \right |^p \right ] \le C n^{-p/d}. \end{equation}
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\gt 0$
,
\begin{equation*} \mathbb {E}\big[ t^{N(A)} \big] = (1+ (t-1)|A|)^n.\end{equation*}
An application of Markov’s inequality yields that, letting
\begin{equation} F(t) = \left ( t \log t - t + 1 \right ) \quad \text{for $t \gt 0$,} \end{equation}
then, for every
$t\gt 1$
, it holds
\begin{equation} \mathbb{P}( N(A) \gt t n|A| ) = \mathbb{P}\!\left( t^{N(A)} \gt t^{tn|A|} \right)\le \exp \!\left ( -n |A|F(t) \right ), \end{equation}
and, for
$t\lt 1$
,
\begin{equation} \mathbb{P}(N(A) \lt t n|A|) \le \exp \!\left ( - n|A|F(t) \right ). \end{equation}
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 \ge 0$
,
\begin{equation*} N^*(v) \,:\!=\, \sup \left \{ N(Q) \, : \, \text { $Q \subseteq [0,1]^d $ cube with $|Q| \le v$} \right \},\end{equation*}
and
\begin{equation*} N_*(v) \,:\!=\, \inf \left \{ N(Q) \, : \, \text { $Q \subseteq [0,1]^d $ cube with $|Q| \ge v$} \right \}.\end{equation*}
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 exists
$C = C(v,d) \ge 1$
such that, for every
$n \ge C$
, if
$t\gt 2^{2d}$
, then
\begin{equation} \mathbb{P}\!\left ( N^*(v) \gt t nv \right ) \le \frac{1}{2^d v} \exp \!\left ( - n v 2^{d} F\big( t 2^{-2d}\big) \right ), \end{equation}
while, if
$t\lt 2^{-2d}$
,
\begin{equation} \mathbb{P}\!\left ( N_*(v) \lt t nv \right ) \le \frac{ 2^{2d}}{v} \exp \!\left ( - n v 2^{-2d} F\big( t 2^{2d}\big) \right ), \end{equation}
with
$F$
as in (2.10).
Proof. We prove (2.13) first. Let
$k \in \mathbb{Z}$
be such that
\begin{equation*} 2^{-k-2} \le v^{1/d} \lt 2^{-k-1},\end{equation*}
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 \big\{ 0,\ldots, 2^{k}-1 \big\}^d$
. It is then sufficient to consider the event
$N(Q) \gt t nv$
for at least one such dyadic cube, i.e., using the union bound (2.11), we bound from above
\begin{equation*} \mathbb {P}\!\left ( N^*(v ) \gt tnv \right )\le 2^{kd} \mathbb {P}\!\left ( N(Q) \gt t nv \right ).\end{equation*}
Using that, for a dyadic cube with
$|Q| = 2^{-dk}$
,
\begin{equation*} 2^{kd} \le 1/\big( 2^{d} v \big) \quad \text {and} \quad |Q|2^{-2d} \le v \le 2^{-d} |Q|, \end{equation*}
it follows that (2.11) applies with
$2^{-2d}t$
instead of
$t$
, yielding
\begin{equation*} \begin{split} 2^{kd} \mathbb{P}\!\left ( N(Q) \gt t nv \right ) & \le 2^{kd} \mathbb{P}\!\left ( N(Q) \gt 2^{-2d} t n| Q| \right ) \\ & \le \frac{1}{2^d v} \exp \!\left ( - n|Q| F\big( t 2^{-2d}\big) \right )\\ & \le \frac{1}{2^d v} \exp \!\left ( - n v 2^{d} F\big( t 2^{-2d}\big) \right ). \end{split} \end{equation*}
The argument for (2.14) is analogous. Let
$k \in \mathbb{Z}$
be such that
\begin{equation*} 2^{-k+1} \le v^{1/d} \lt 2^{-k+2},\end{equation*}
hence every cube
$Q$
with
$|Q| \ge 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) \lt t nv$
, i.e.,
\begin{equation*} \mathbb {P}\!\left ( N_*(v ) \lt tnv \right )\le 2^{kd} \mathbb {P}\!\left ( N(Q) \lt tnv \right ) .\end{equation*}
Using that
\begin{equation*} 2^{kd} \le 2^{2d}/v \quad \text {and} \quad 2^d |Q|\le v \le 2^{2d}|Q|, \end{equation*}
it follows that (2.12) applies with
$2^{2d}t$
instead of
$t$
, yielding
\begin{equation*} \begin{split} 2^{kd} \mathbb{P}\!\left ( N(Q) \lt t nv \right ) & \le 2^{kd} \mathbb{P}\!\left ( N(Q) \lt 2^{2d} t n |Q| \right ) \\ & \le \frac{ 2^{2d}}{v} \exp \!\left ( - n |Q| F\big( t 2^{2d}\big) \right )\\ & \le \frac{ 2^{2d}}{v} \exp \!\left ( - n v 2^{-2d} F\big( t 2^{2d}\big) \right ). \end{split} \end{equation*}
In the following result we investigate the random variable (for
$n \ge 2$
)
\begin{equation*} M_n = \max _{i=1, \ldots, n} |X_i - \mathsf {n}(X_i)|,\end{equation*}
where
$\mathsf{n}(X_i)$
denotes the closest point to
$X_i$
among
$\left \{ X_j \right \}_{j \neq i}$
, so that
\begin{equation*} |X_i - \mathsf {n}(X_i)| = \min _{\substack { j \le n \\ j \neq i}} |X_i - X_j|.\end{equation*}
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 \ge 2$
,
$(X_i)_{i=1}^n$
be i.i.d. uniformly distributed on
$[0,1]^d$
. Then, for every
$a\gt 0$
, there exists a constant
$C = C(a,d) \ge 1$
such that
\begin{equation*} \mathbb {P} \!\left ( C^{-1} \le \frac {M_n}{({\log}\,( n)/ n)^{1/d}} \le C \right ) \ge 1 - \frac {C}{n^a}.\end{equation*}
In particular, for every
$q\gt 0$
, there exists
$C =C(d,q)\gt 0$
such that, for every
$n \ge 2$
,
\begin{equation} \mathbb{E}\!\left [ \left ( M_n \right )^q \right ] \le C \!\left ( \frac{ \log n}{n} \right )^{q/d}. \end{equation}
Proof. It is convenient to replace the Euclidean distance in the definition of
$M_n$
with the
$\ell ^{\infty }$
distance
$|x-y|_\infty = \max _{i=1, \ldots, d} |x_i-y_i|$
, i.e., we consider
\begin{equation*} M_n^\infty \,:\!=\, \max _{i=1, \ldots, n}\min _{j \neq i} |X_i -X_j|_\infty .\end{equation*}
Using that
$|x-y|_\infty \le |x-y| \le \sqrt{d} | x-y|_\infty$
, we have
$M_n^\infty \le M_n \le \sqrt{d} M_n^\infty$
, hence the thesis for the Euclidean case would follow once established for
$M_n^\infty$
, since we do not aim for a sharp constant
$C$
.
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 an integer.
Consider a partition of
$[0,1]^d$
into cubes
$\left \{ Q_j \right \}_{j\in J}$
of volume
\begin{equation*} |Q_j| = v \,:\!=\,\delta ^d\end{equation*}
with
$J = \big\{ 1, \ldots, \delta ^{-d} \big\}$
. Fix
$\bar{t}$
large enough, in particular such that
$\bar{t}\gt 2^{2d}\eta$
and
$\eta 2^d F(\bar{t}2^{-2d}/\eta ) \gt a+1$
. Lemma 2.8 entails that the event
\begin{equation*} E \,:\!=\, \bigcap _{j \in J} \left \{ 2 \le N(Q_j) \le \bar {t} \log n \right \} \supseteq \left \{ N^*(v) \le \bar {t} \log n \right \} \cap \left \{ N_*(v) \ge 2 \right \}.\end{equation*}
has probability larger than
$1- C/n^a$
for some constant
$C = C(d,a)$
. Indeed, since
$v = \delta ^d = \eta \log (n)/n$
, inequality (2.13) yields
\begin{equation*} \begin{split} \mathbb{P}\!\left( N^*(v) \gt \bar{t} \log n \right) & = \mathbb{P}\!\left ( N^*(v) \gt \bar{t}/\eta nv \right ) \\ & \le 2^{-d} \frac{n}{\eta \log n} \exp \!\left ( - \log (n) \eta 2^d F\!\left(\bar{t}2^{-2d}/\eta \right) \right ) \le \frac{1}{2^{d} \eta \log 2} \cdot n^{-a},\end{split} \end{equation*}
where we used that
$\log (n)\gt \log (2)$
.
Similarly, by (2.14), with
$t = 2/({\log}\,(n) \eta )$
(that is smaller than
$2^{-2d}$
for
$n$
large enough) it holds
\begin{equation*} \begin{split} \mathbb{P}( N_*(v) \lt 2 ) & = \mathbb{P}\!\left ( N_*(v) \lt \left ( 2/({\log}\,(n) \eta ) \right ) nv \right ) \\ & \le 2^{2d} \frac{n}{\eta \log n} \exp \!\left ( - \log (n) \eta 2^{-2d} F\!\left(2^{2d+1}/({\log}\,(n) \eta )\right) \right ).\end{split} \end{equation*}
For
$n$
sufficiently large, it holds
$F\!\left ( 2^{2d+1}/({\log}\,(n) \eta ) \right )\gt 1/2$
, hence
\begin{equation*} \begin{split} 2^{2d} \frac{n}{\eta \log n} \exp \!\left ( - \log (n) \eta 2^{-2d} F\!\left(2^{2d+1}/({\log}\,(n) \eta )\right) \right ) & \le 2^{2d} \frac{n}{\eta \log n } \exp \!\left ( - \log (n) \eta 2^{-2d-1} \right )\\ & \le \frac{2^{2d}}{\eta n^a}. \end{split} \end{equation*}
using that
$\eta \gt (a+1)2^{2d+1}$
.
Hence, to prove the thesis, we can assume that
$E$
holds. In such a case, it follows immediately that
$M_n^\infty \le \delta$
, since the
$\ell ^\infty$
-diameter of a cube
$Q_j$
for
$j \in J$
is
$v^{1/d} = \delta$
and each point belongs in one such cube where at least one other point can be found. Hence, we deduce
\begin{equation*} \mathbb {P}\!\left ( \frac {M_n^\infty }{({\log}\,(n)/n)^{1/d}} \gt \eta ^{1/d} \right ) \le \mathbb {P}( E^c ) \le \frac {C}{n^a}.\end{equation*}
Next, for each
$j \in J$
, we introduce the random variables
\begin{equation*} M_{n,j} \,:\!=\, \sup _{\substack { i \le n \\ X_i \in Q_j} }\, \inf _{ \substack { \ell \le n \\ 0\lt |X_i- X_\ell |_\infty \le \delta } } | X_i - X_\ell |_\infty \end{equation*}
i.e., we maximise the minimum
$\ell ^\infty$
distances between points in
$Q_j$
and those that are at
$\ell ^\infty$
distance at most
$\delta$
. These are not necessarily in
$Q_j$
but must belong to the union of all cubes
$Q_\ell$
covering the set
\begin{equation*} Q_{j, \delta } \,:\!=\, \left \{ x \in [0,1]^d \, : \, \min _{y \in Q_j} |x-y|_\infty \le \delta \right \}.\end{equation*}
and is easily seen to be a cube of side length
$3 \delta$
. Notice also that, since we argue in the event
$E$
, each cube
$Q_j$
contains at least two elements, hence
\begin{equation*} M_n^\infty = \max _{j \in J} M_{n,j}.\end{equation*}
We now use the following fact: for every
$f\,:\, \left \{ 1, \ldots, n \right \} \to J$
, conditioning upon the event
\begin{equation*} A_f = \left \{ X_i \in Q_{f(i)}\quad \text {for every $i=1, \ldots, n$,} \right \}, \end{equation*}
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$
,
\begin{equation*} 2 \le \left | \{ i \in \left \{ 1,\ldots, n \right \} \, : \, f(i) =j \right | \le \bar {t} \log n.\end{equation*}
We introduce then a subfamily
$K \subseteq J$
consisting of
$(3 \delta )^{-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
\begin{equation*} M_n^\infty = \max _{j\in J} M_{n,j} \ge \max _{k \in K} M_{n,k},\end{equation*}
and independence we have, for every
$\lambda \gt 0$
,
\begin{equation*} \mathbb {P}\!\left( M_n \le \lambda | A_f\right) \le \mathbb {P}\!\left( \max _{k \in K} M_{n,k} \le \lambda | A_f \right) = \prod _{k \in K} \mathbb {P}\!\left( M_{n,k} \le \lambda | A_f \right) \end{equation*}
The probability
$\mathbb{P}\!\left( M_{n,k} \le \lambda | A_f \right)$
clearly depends only on the number of elements in each set
$f^{-1}(j)$
, i.e., on the number of points in each
$Q_j$
, for
$j \in J$
, not their labels. We may therefore assume without loss of generality that
$f(1) = k$
, i.e.,
$X_1 \in Q_k$
and that
\begin{equation*} \left \{ X_i \right \}_{i=1}^n \cap Q_{k,\delta } = \left \{ X_1, \ldots, X_\ell \right \},\end{equation*}
with
\begin{equation} \ell = N(Q_{k, \delta })\le 3^d \bar{t} \log n. \end{equation}
Then,
\begin{equation*} M_{n,k} \ge \min _{ j=2,\ldots, \ell } |X_j - X_1|_\infty,\end{equation*}
hence, further conditioning upon
$X_1$
and using independence,
\begin{equation*} \begin{split} \mathbb{P}\!\left(M_{n,k} \gt \lambda | A_f \right) & \ge \frac{1}{|Q_k|} \int _{Q_k} \mathbb{P}\!\left ( \min _{ j=2,\ldots, \ell } |X_j - x|_\infty \gt \lambda | A_f, X_1=x \right ) d x \\ & \ge \frac{1}{|Q_k|} \int _{Q_k} \prod _{j=2}^\ell \mathbb{P}( |X_j - x|_\infty \gt \lambda | A_f, X_1=x) d x\\ & \ge \frac{1}{|Q_k|} \int _{Q_k} \prod _{j=2}^\ell \left ( 1- \omega _d \lambda ^d/ |Q_{f(j)}| \right )_+ d x \quad \text{by (2.7),}\\ & \ge \left ( 1- \omega _d (\lambda/\delta )^{d} \right )^{N(Q_{k,\delta })-1}_+ = e^{-u \left( N\!\left(Q_{k,\delta }\right)-1\right)}, \end{split} \end{equation*}
where in the last equality we choose
$\lambda = \delta ((1-e^{-u})/ \omega _d)^{1/d}$
with
$u =1/\left(2\cdot 3^d \bar{t}\right)$
. Indeed, this choice ensures that, by (2.16) we bound from above, for
$n$
sufficiently large,
\begin{equation*} \mathbb {P}\!\left ( M_n^\infty \le \lambda | A_f \right ) \le \left ( 1-e^{-u \left( 3^d \bar {t} \log (n)-1\right)} \right )^{(3\delta )^{-d}} \le \left ( 1-\frac {e^{u}}{n^{1/2}} \right )^{n/ \left(3^{d}\eta \log (n)\right)} \le \frac {C}{n^a}. \end{equation*}
Finally, (2.15) follows since
$M_n^\infty \le 1$
, hence, choosing
$a = q/d$
, we bound from above
\begin{equation*} \mathbb {E}\!\left [ \left(M_n^\infty \right)^q \right ] \le \mathbb {P}\!\left( M_n^\infty \gt C ({\log}\,(n)/n)^{1/d} \right) + C^q \left ( \frac { \log n}{n} \right )^{q/d}\le C\!\left ( \frac { \log n}{n} \right )^{q/d},\end{equation*}
for a (possibly different) constant
$C=C(d,q)$
.
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 \ge 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
\begin{equation*} \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.\end{equation*}
Then, for every
$a\gt 0$
, there exists a constant
$C = C(d,\alpha _R, \alpha _B, a)\ge 1$
such that, for every
$n$
sufficiently large,
\begin{equation*} \mathbb {P} \!\left ( C^{-1} \le \frac {\mathsf {d}(R^n, B^n)}{({\log}\,( n)/ n)^{1/d}} \le C \right ) \ge 1 - \frac {C}{n^a}.\end{equation*}
In particular, for every
$q\gt 0$
, there exists
$C =C(d,q,\alpha _R)\gt 0$
such that, for every
$n$
sufficiently large,
\begin{equation*} \mathbb {E}\!\left [ \mathsf {d}(R^n, B^n ) ^q \right ] \le C \!\left ( \frac { \log n}{n} \right )^{q/d}.\end{equation*}
Proof. The proof follows the same argument as the previous one, so we briefly describe the needed minor changes. It is again simpler to argue first in the
$\ell ^\infty$
distance, hence we replace the variable
$M^\infty _n$
with
\begin{equation*} \max _{i=1, \ldots, n_R}\min _{j=1, \ldots, n_B} |X_i -Y_j|_\infty .\end{equation*}
After considering the same partition of
$[0,1]^d$
into cubes
$\left \{ Q_j \right \}_{j \in J}$
, we replace the event
$E$
with
\begin{equation*} \bigcap _{j \in J} \left \{ 2 \le N_{B^n}(Q_j) \le \bar {t} \log n, \, 2 \le N_{R^n}(Q_j) \le \bar {t} \log n \right \} \end{equation*}
which has large probability, using first the independence between
$R^n$
,
$B^n$
and then arguing similarly as in the previous proof. Once reduced to the event
$E$
, we repeat the same arguments replacing the variables
$M_{n,j}$
,
$j \in J$
, with
\begin{equation*} \sup _{\substack { i \le n_R \\ X_i \in Q_j} }\, \inf _{ \substack { \ell \le n_B \\ |X_i- Y_\ell |_\infty \le \delta } } | X_i - Y_\ell |_\infty .\end{equation*}
This eventually yields the bound
\begin{equation*} \mathbb {P} \!\left ( C^{-1} \le \frac { \max _{i=1, \ldots, n_R}\min _{j=1, \ldots, n_B} |X_i -Y_j|}{({\log}\,(n)/n )^{1/d}} \le C \right ) \ge 1 - \frac {C}{n^a}.\end{equation*}
Finally, repeating the overall derivations with the roles of
$R^n$
and
$B^n$
exchanged, we obtain the thesis, because
\begin{equation*} \mathsf {d}(R^n, B^n) = \max \left \{ \max _{i=1, \ldots, n_R}\min _{j=1, \ldots, n_B} |X_i -Y_j|, \max _{j=1, \ldots, n_B}\min _{i=1, \ldots, n_R} |Y_j-X_i| \right \}. \end{equation*}
3. Proof of Theorem 1.1
Throughout this section, for
$n \ge 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
\begin{equation*} \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.\end{equation*}
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 \gt 0$
such that, as
$n \to \infty$
,
\begin{equation*} \mathbb {P}\!\left ( \Delta (T^n) \lt \epsilon \log n \right ) \to 0.\end{equation*}
Proof. For
$n$
sufficiently large, we have
$n_R \ge \alpha _R n/2$
,
$n_B \ge \alpha _B n/2$
. Fix any
$a\gt 0$
and let
$C_1 = C(d,a)\ge 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
\begin{equation*} \min _{j \neq i} |X_i - X_j| \ge C^{-1}_1 \left ( \log (n_R)/n_R \right )^{1/d} \ge C^{-1} \left ( \log (n)/n \right )^{1/d},\end{equation*}
(the second inequality being true if
$n$
is sufficiently large) has probability
$\mathbb{P}(E^n)\ge 1-C/n^a$
as
$n \to \infty$
, for a suitable constant
$C = C(d,\alpha _R, a)\gt 0$
. In particular, every point in the cube
$Q$
centred at
$X_i$
with side length
\begin{equation*} \delta = \left ( \log (n)/n \right )^{1/d}/ \Big(4 \sqrt {d} C\Big)\end{equation*}
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
\begin{equation*} \epsilon = 1/\Big( 2\big(4\sqrt {d} C\big)^d \Big), \quad \text { so that } \quad \Big(4 \sqrt {d} C\Big)^d \epsilon =1/2,\end{equation*}
and writing
$N_{B^n}(Q)$
for the number of elements in
$B^n \cap Q$
, we have
\begin{equation*} \begin{split} \mathbb{P}\!\left( \Delta (T_n) \lt \epsilon \log (n) \right) & \le \mathbb{P}\!\left(\left(E^n\right)^c\right) + \mathbb{P}\!\left( N_{B^n}(Q) \lt n|Q|/2, E^n\right) \\ & \le \frac{C}{n^a} + \mathbb{E}\!\left [ I_{E^n} \mathbb{P} \!\left ( N_{B^n}(Q) \lt n \delta ^d/2 | \left \{ X_i \right \}_{i=1}^{n_B} \right ) \right ]. \end{split} \end{equation*}
By independence, the conditional law of
$N_{B^n}(Q)$
is Binomial with parameters
$\big( n_B, \delta ^d \big)$
, hence we may use (2.12) to obtain
\begin{equation*} \mathbb {P} \!\left ( N_{B^n}(Q) \lt \epsilon \log (n) | \left \{ X_i \right \}_{i=1}^{n_B} \right ) \le \exp \!\left ( -n_B \delta ^d F(1/2) \right ).\end{equation*}
Since
$n_B \ge \alpha _B n/2$
,
$\delta ^d = \log (n)/ \big(n \big(4 \sqrt{d} C\big)\big)$
and
$F(1/2)\gt 0$
, it follows that, as
$n \to \infty$
,
\begin{equation*} \exp \!\left ( -n_B \delta ^d F(1/2) \right ) \to 0.\end{equation*}
Lemma 3.2.
For every
$a\gt 0$
, there exists
$C = C(d,a, \alpha _R) \gt 0$
such that, for
$n$
sufficiently large,
\begin{equation*} \mathbb {P}\!\left ( \Delta (T^n) \gt C \log (n) \right ) \le \frac {C}{n^a}.\end{equation*}
In particular, for every
$q\gt 0$
, there exists
$C =C(d, q, \alpha _R)\gt 0$
such that, for every
$n$
large enough,
\begin{equation} \mathbb{E}\!\left [ \Delta (T^n) ^q \right ] \le C \!\left ( \log n \right )^q. \end{equation}
Proof. For
$n$
sufficiently large, we have
$n_R \ge \alpha _R n/2$
,
$n_B \ge \alpha _B n/2$
. Fix
$a\gt 0$
and let
$C_1 = C_1(d,a, \alpha _R)\ge 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
\begin{equation*} \left \{ \mathsf {d}\big(R^n,B^n\big) \gt C_1 ({\log}\,(n)/n)^{1/d} \right \}\end{equation*}
has probability smaller than
$C_1/n^a$
. We claim that there exists
$\lambda =\lambda (d,a, \alpha _R) \gt 8 C_1$
and
$C = C(d,a,\alpha _R)$
such that the following conditions hold, for
$n$
sufficiently large:
-
1. letting
$v_1 = \left ( \lambda/4 \right )^d \log (n)/n$
, then
\begin{equation*} \mathbb {P}\!\left ( N^*_{R^n}(v_1) \gt \lambda ^d \log n \right ) \le \frac {C}{n^a} \quad \text {and} \quad \mathbb {P}\!\left ( N^*_{B^n}(v_1) \gt \lambda ^d \log n \right ) \le \frac {C}{n^a};\end{equation*}
-
2. letting
$v_2 = \left [ \left ( \lambda/8 - C_1) \right )/\big(2\sqrt{d}\big) \right ]^{d} \log (n)/n$
, then
\begin{equation*} \mathbb {P}\!\left ( \left ( N_{R^n} \right )_*(v_2) =0 \right ) \le \frac {C}{n^a}, \quad \mathbb {P}\!\left ( \left ( N_{B^n} \right )_*(v_2) =0 \right ) \le \frac {C}{n^a}. \end{equation*}
Once the claim is proved, it is immediate to show that on the event
\begin{equation*} \begin{split} E = \Big \{ \mathsf{d}(R,B) \gt C_1 ({\log}\,(n)/n)^{1/d}, & \max \left \{ N^*_{R^n}(v_1), N^*_{B^n}(v_1) \right \} \le \lambda ^d \log n \\ & \min \left \{ \left ( N_{R^n} \right )_*(v_2), \left ( N_{B^n} \right )_*(v_2) \right \} \ge 1 \Big \} \end{split} \end{equation*}
that satisfies
$\mathbb{P}(E^c) \lt C/n^a$
(with a different constant
$C$
), it must be
$\Delta (T^n) \le \lambda ^d \log (n)$
. Indeed, if
$\Delta (T^n) \gt \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) \le \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$
centred at
$X_i$
. In particular,
\begin{equation*} |Y_j-X_i| \ge \frac {\lambda }{8} \left ( \log (n)/n \right )^{1/d} \gt C_1 \left ( \log (n)/n \right )^{1/d} \ge \mathsf {d}\big(R^n,B^n\big).\end{equation*}
By Lemma 2.7, there exists a cube
$Q$
with
$Q \cap R^n = \emptyset$
and
\begin{equation*} |Q| \ge \left [ \left ( \lambda/8 - C_1) \right )/ \big(2 \sqrt {d}\big) \right ]^{d} \frac {\log (n)}{n} = v_2,\end{equation*}
contradicting
$(N_{R^n})_*(v_2) \gt 0$
.
To prove the claim, we apply Lemma 2.8. Indeed, (2.13) with
$t= 4^d n/n_R \ge 2^{2d}$
gives
\begin{equation*} \begin{split} \mathbb{P}\!\left ( N^*_{R^n}(v_1) \gt \lambda ^d \log n \right ) & = \mathbb{P}\!\left ( N^*_{R^n}(v_1) \gt 4^d (n/n_R) \cdot v_1 n_R \right ) \\ & \le \frac{1}{2^d v_1} \exp \!\left ( -n_R v_1 2^dF(n/n_R) \right ) \\ & \le \frac{2^{d} n }{\lambda ^d \log (n)} \exp \!\left ( - \log (n) (n_R/n) \cdot \lambda ^d2^{-d}F(n/n_R) \right ) \le \frac{C}{n^a}, \end{split} \end{equation*}
provided that
$n$
is sufficiently large and
$\lambda$
is sufficiently large so that
$\lambda ^d \alpha _R 2^{-d-1}F(n/n_R) \ge a+1$
. Conversely, we use (2.14) with
$t = 1/n_R v_2 = \left [ \left ( \lambda/8 - C_1) \right )/\big( 2\sqrt{d}\big) \right ]^{-d} n/(n_R\log (n)) \lt 2^{-2d}$
(if
$n$
is sufficiently large) so that
\begin{equation*} \mathbb {P}\!\left ( N^*_{R^n}(v_2) \lt 1 \right ) \le 2^{2d} \left [ \left.\left ( \lambda/8 - C_1\right) \right )/\big(2 \sqrt {d}\big) \right ]^{-d} \frac {n}{\log n} \exp \!\left ( -n_R v_2 2^{-2d} F\Big(t2^{2d}\Big) \right ) \le \frac {C}{n^a},\end{equation*}
provided that we choose
$\lambda$
large enough such that
\begin{equation*} \left [ \left ( \lambda/8 - C_1) \right )/\big(2 \sqrt {d}\big) \right ]^{d}2^{-2d-2\alpha _R} \ge a+1,\end{equation*}
since for
$n$
sufficiently large, we have
$F\Big(t2^{2d}\Big) \gt 1/2$
. Naturally, the same argument works replacing
$R^n$
with
$B^n$
, thus completing the proof of (1) and (2).
Finally, (3.1) follows since trivially
$\Delta (T^n) \le n$
, hence, choosing
$a = q$
, we bound from above
\begin{equation*} \mathbb {E}\!\left [ \Delta (T^n)^q \right ] \le n^q \mathbb {P}( \Delta (T^n) \gt C \log n) + \left ( C \log n \right )^q \le C+ \left ( C \log n \right )^q. \end{equation*}
4. Proof of Theorem 1.2
We first extend [Reference Avram and Bertsimas1, 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 \ge 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
\begin{equation} C_{G(z)}= \sum _{k=1}^m \sum _{i=1}^{m}\frac{X_{i,k,G(z)}}{k}, \end{equation}
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,
\begin{equation*} C_{k,G(z)}= \sum _{\ell =k}^m \sum _{i=1}^{m}\frac {X_{i,\ell,G(z)}}{\ell },\end{equation*}
To estimate the expectation of
$X_{i,k,G(z)}$
, in [Reference Avram and Bertsimas1] 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 \ge 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 for 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
\begin{equation*} 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$,}\end{equation*}
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
\begin{equation} \mathbb{E}\!\left [ \mathcal{C}_{\text{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 )d z . \end{equation}
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,
\begin{equation*} C^n(z)= C_{G^n(z)}, \quad C^n_{k}(z) = C_{k,G^n(z)},\end{equation*}
\begin{equation*} 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)}.\end{equation*}
For a (pseudo-dimension) parameter
$d \gt 1$
we introduce the following assumptions:
-
a) For any
$k\ge 1$
,
$y\gt 0$
,where convergence is pointwise and dominated in the following sense: for every
\begin{equation*} \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),\end{equation*}
$k\ge 1$
there exists a function
$\ell _{k}$
and
$n_k \ge 1$
such that, for every
$y\gt 0$
,and
\begin{equation*} \sup _{n \ge n_k} P_{k,R}^n\left ( (y/n)^{1/d} \right )+ P_{k,B}^n\left ( (y/n)^{1/d} \right ) \le \ell _k(y)\end{equation*}
\begin{equation*} \int _{0}^{\infty } \ell _{k}(y)y^{\frac {1}{d}-1}dy \lt \infty .\end{equation*}
-
b) It holds
\begin{equation*} \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.\end{equation*}
The following result extends [Reference Avram and Bertsimas1, Theorem 1] to the bipartite case.
Theorem 4.2.
Let
$d \gt 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),
\begin{equation*} \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.\end{equation*}
and such that, for some constant
$\bar{z} \in (0, \infty )$
, it holds
$\mathbb{P}$
-a.s.
\begin{equation*} \sup _{n \ge 1}\sup _{r \in R^n, b\in B^n} w^n(r,b) \le \bar {z}. \end{equation*}
Then,
\begin{equation*} \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 _Rf_{k,R}(y)+ \alpha _B f_{k,B}(y) \right )y^{\frac {1}{d}-1}dy. \end{equation*}
Proof. By (2.2), for any
$n \ge 1$
,
$k \ge 1$
, we decompose
\begin{equation*} \begin{split} \frac{\mathbb{E}\!\left [ \mathcal{C}_{MST}(G^n) \right ]}{n^{1-1/d}} & = \frac{1}{n^{1-1/d}} \int _{0}^{\bar{z}}\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}^{\bar{z}} \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}{n^{1-1/d}}\left ( - \bar{z} + \int _{0}^{\bar{z}} \left ( \mathbb{E}\!\left [ C_{k}^n(z) \right ]-1 \right ) dz \right ), \end{split} \end{equation*}
having used that, for
$z \gt \bar{z}$
the integrand in (2.2) is identically zero. Assumption b) gives that in the limit
$n \to \infty$
,
$k \to \infty$
the last line gives no contribution in the limit. 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{equation*} \begin{split} & \lim _{k \to \infty } \lim _{n\to \infty } n^{1/d} \int _{0}^{\bar{z}} \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 \\[5pt] & \quad = \frac{1}{d}\sum _{\ell =1}^{\infty } \frac{1}{\ell }\int _{0}^{\infty }\left ( \alpha _Rf_{\ell,R}(y)+ \alpha _B f_{\ell,B}(y) \right )y^{1/d-1}dy.\end{split} \end{equation*}
For fixed
$k$
, the limit as
$n \to \infty$
follows by dominated convergence applied to each
$\ell =1, \ldots, k-1$
, yielding
\begin{equation*} \begin{split} & \lim _{n \to \infty } \int _{0}^{\bar{z}} n^{1/d} \left ( \frac{|R^n|}{n}P_{\ell, R}^n(z) + \frac{|B^n|}{n} P_{\ell, B}^n(z) \right ) dz \\[5pt] &\quad = \lim _{n \to \infty } \frac 1 d \int _{0}^{n \bar{z}^d} \left ( \frac{|R^n|}{n}P_{\ell, R}^n\left((y/n)^{1/d}\right) + \frac{|B^n|}{n} P_{\ell, B}^n\left((y/n)^{1/d}\right) \right ) y^{1/d -1} dy\\[5pt] &\quad = \frac 1 d \int _{0}^{\infty }\left ( \alpha _Rf_{\ell,R}(y)+ \alpha _B f_{\ell,B}(y) \right )y^{1/d-1}dy \end{split} \end{equation*}
after the change of variables
$z = (y/n)^{1/d}$
and using Lebesgue’s dominated convergence Theorem, as ensured by assumption a). Finally, the limit as
$k \to \infty$
follows by monotone convergence.
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
\begin{equation*} \mathsf {d}_{\mathbb {T}^d}(x,y) \,:\!=\, \inf _{z \in \mathbb {Z}^d} |x-y+z|.\end{equation*}
This can be seen as an intermediate step towards the proof of Theorem 1.2, where we exploit the additional homogeneity of the torus. In particular, we use the fact that the uniform distribution on
$\mathbb{T}^d$
is invariant with respect to translations. In practice, this means that compared to the case of the cube
$[0,1]^d$
, one does not have to consider whether a point is close or far from the boundary (of course
$\mathbb{T}^d$
has no boundary): a fact that in the limit plays no role also in
$[0,1]^d$
, but it could make a direct derivation much more complicated.
Theorem 4.3.
Let
$d \ge 1$
,
$n\ge 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
\begin{equation*} \lim _{n \to \infty } \frac { n_R }{n} = \alpha _R, \quad \lim _{n \to \infty } \frac { n_B}{n} = \alpha _B = 1-\alpha _R.\end{equation*}
Then, for every
$p \in (0,d)$
,
\begin{equation*} \lim _{n \to \infty } \frac { \mathbb {E}\!\left [ \mathcal {C}_{MST}^p\big(R^n,B^n\big) \right ]}{ n^{1-p/d} }= \beta _{b\text{MST}}(d,p),\end{equation*}
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\big(X_i, Y_j\big) = \mathsf{d}_{\mathbb{T}^d}\big(X_i, Y_j\big)^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\gt 1$
instead of
$d$
.
We introduce some notation: for
$k_R$
,
$k_B \in \mathbb{N}$
,
$z\ge 0$
, let
\begin{equation*} \Theta _{\mathbb {T}^d}(k_R, k_B, z) \subseteq \big(\mathbb {T}^d\big)^{k_R} \times \big(\mathbb {T}^d\big)^{k_B}\end{equation*}
denote the set of (ordered) points
$\left( \left ( r_i \right )_{i=1}^{k_R}, \left ( b_j \right )_{j=1}^{k_B}\right)$
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\ge 0$
, write
\begin{equation*} D_{\mathbb {T}^d}(A,z) = \left \{ x \in \mathbb {T}^d\, : \, \mathsf {d}_{\mathbb {T}^d}(A,x)^p \le z \right \}.\end{equation*}
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. the set
$\left(\left \{ X_i \right \}_{i=1}^{k_R}, \left \{ Y_j \right \}_{j=1}^{k_B}\right)$
belongs to
$\Theta _{\mathbb{T}^d}(k_R, k_B, z)$
, -
2.
$\mathsf{d}_{\mathbb{T}^d}\left(\left \{ Y_j \right \}_{j=1}^{k_B}, X_i \right) \gt z$
, i.e.
$X_i \notin D_{\mathbb{T}^d} \left(\left \{ Y_j \right \}_{j=1}^{n_B}, z\right)$
, for every
$i \gt k_R$
, -
3.
$\mathsf{d}_{\mathbb{T}^d} \left(\left \{ X_i \right \}_{i=1}^{k_R}, Y_j\right) \gt z$
, i.e.
$Y_j \notin D_{\mathbb{T}^d} \left ( \left \{ X_i \right \}_{i=1}^{k_R}, z \right )$
, for every
$j \gt 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 2) and 3), we obtain the following expression for the probability:
\begin{equation} \begin{split} & I_R(k_R, k_B, z) =\\ & \int _{\Theta _{\mathbb{T}^d}(k_R, k_B, z)} \left ( 1 - \left|D_{\mathbb{T}^d}\left(\left \{ b_j \right \}_{j=1}^{k_B}, z\right)\right| \right )^{n_R - k_R}\left ( 1 - \left|D_{\mathbb{T}^d} \left(\left \{ r_i \right \}_{i=1}^{k_R}, z\right)\right| \right )^{n_B - k_B} d r d b, \end{split} \end{equation}
where
$d r d b$
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
different choices of labellings (recall that
$X_1$
is kept fixed) and upon
$k_R \ge 1$
,
$k_B$
with
$k_R+k_B = k$
gives
\begin{equation} P_{k,R}^n(z)= \sum _{\substack{ k_R+k_B = k \\ k_R \ge 1}}\bigg(\begin{array}{c}n_R\\k_R-1\end{array}\bigg)\bigg(\begin{array}{c}n_B\\k_B\end{array}\bigg) I(k_R, k_B, z) . \end{equation}
We now replace integration in (4.3) from
$(\mathbb{T}^{d})^{k}$
to
$\big({\mathbb{R}}^d\big)^k$
. This is possible provided that
$z$
is small enough, so that only the local structure is relevant. We first notice that, since we are considering the flat torus
$\mathbb{T}^d$
, by exploiting the invariance with respect to translations of the uniform distribution, 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 \le 1/(4k)$
, it follows that such tree is contained in a ball of centre
$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_{\mathbb{T}^d}\left(\left \{ b_j \right \}_{j=1}^{k_B}, z\right)$
,
$D_{\mathbb{T}^d}\left(\left \{ r_i \right \}_{i=1}^{k_R},z\right)$
are then contained in a ball of centre
$0$
and radius
$1/2$
, hence their volumes computed on
$\mathbb{T}^d$
coincide with those of their respective lifts on
$(-1/2, 1/2)^d \subseteq{\mathbb{R}}^d$
. To parallel the notation, we therefore define the set
$\Theta _{{\mathbb{R}}^d}(k_R, k_B, z) \subseteq \big({\mathbb{R}}^d\big)^{k_R} \times \big({\mathbb{R}}^d\big)^{k_B}$
, analogous to
$\Theta _{\mathbb{T}^d}(k_R, k_B, z)$
. We notice that
\begin{equation*} \Theta _{{\mathbb {R}}^d}(k_R, k_B, 1) = \Theta \!\left(k_R, k_B\right)\end{equation*}
as defined in (1.3). We write
\begin{equation*} D_{{\mathbb {R}}^d}(A,z) = \left \{ x \in {\mathbb {R}}^d\, : \, \mathsf {d}(A,x)^p \le z \right \},\end{equation*}
for
$A \subseteq{\mathbb{R}}^d$
, and notice that
$D_{{\mathbb{R}}^d}(A,1) = D(A)$
as defined in (1.4). As noticed above, for
$z \le 1/(4k)$
, we have the identity
\begin{equation*} \begin{split} & I_R(k_R, k_B, z) =\\ & \int _{\Theta _{{\mathbb{R}}^d}(k_R, k_B, z)} \left ( 1 - \left|D_{{\mathbb{R}}^d}\left(\left \{ b_j \right \}_{j=1}^{k_B}, z\right)\right| \right )^{n_R - k_R}\left ( 1 - \left|D_{{\mathbb{R}}^d} \left(\left \{ r_i \right \}_{i=1}^{k_R}, z\right)\right| \right )^{n_B - k_B} \delta _0(r_1) d r d b,\end{split} \end{equation*}
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$
and
$z\gt 0$
,
\begin{equation*} D_{{\mathbb {R}}^d}(A, z) = z^{1/p} D_{{\mathbb {R}}^d}\big( z^{-1/p} A\big),\end{equation*}
a change of variable in the integration
$r_i z^{-1/p} \mapsto r_i$
,
$b_i z^{-1/p} \mapsto b_i$
yields, for
$z \le 1/(4k)$
,
\begin{equation*} \begin{split} I_R(k_R, k_B, z) = z^{(k-1)/p} & \int _{\Theta \!\left(k_R, k_B\right)} \left ( 1 - z^{d/p} \left|D\!\left(\left \{ b_j \right \}_{j=1}^{k_B}\right)\right| \right )^{n_R- k_R} \cdot \\ & \quad \cdot \left ( 1 - z^{d/p} \left|D\!\left(\left \{ r_i \right \}_{i=1}^{k_R}\right)\right| \right )^{n_B - k_B} \delta _0(r_1) d r d b,\end{split} \end{equation*}
(notice the exponent
$k-1$
instead of
$k$
because of the different integration for
$r_1$
). Given
$y\gt 0$
, set
$z\,:\!=\,\left ( y/n \right )^{p/d}$
, so that
$z \le 1/(4k)$
if
$n$
is sufficiently large, hence
\begin{equation*} \begin{split} I_R\left(k_R, k_B, \left ( y/n \right )^{p/d}\right) = \frac{y^{(k-1)/d}}{n^{k-1}} & \int _{\Theta \!\left(k_R, k_B\right)} \left ( 1 - \frac{y}{n} \left|D\!\left(\left \{ b_j \right \}_{j=1}^{n_B}\right)\right| \right )^{n_R - k_R} \cdot \\ & \quad \cdot \left ( 1 - \frac{y}{n} \left|D\!\left(\left \{ r_i \right \}_{i=1}^{k_R}\right)\right| \right )^{n_B - k_B} \delta _0(r_1) d r d b,\end{split} \end{equation*}
Since
$\Theta \!\left(k_R, k_B\right)$
has finite measure (with respect to
$\delta _0(r_1)drdb$
), by dominated convergence it follows that
\begin{equation*} \begin{split} \lim _{ n \to \infty } & \int _{\Theta \!\left(k_R, k_B\right)} \left ( 1 - \frac{y}{n} |D\!\left(\left \{ b_j \right \}_{j=1}^{k_B}\right)| \right )^{n_R - k_R} \left ( 1 - \frac{y}{n} \left|D\!\left(\left \{ r_i \right \}_{i=1}^{k_B}\right)\right| \right )^{n_B - k_B} \delta _0(r_1) d r d b\\ & = \int _{\Theta \!\left(k_R, k_B\right)} \exp \!\left ( -y \left ( \alpha _R \left|D\!\left(\left \{ b_j \right \}_{j=1}^{k_B}\right)\right| + \alpha _B \left|D\!\left(\left \{ r_i \right \}_{i=1}^{k_R}\right)\right| \right ) \right ) \delta _0(r_1) d r d b \\ & \,=\!:\, \mathcal{I}_R\left(k_R, k_B, \alpha _R, y\right). \end{split} \end{equation*}
Moreover, we have the limit
\begin{equation} \lim _{ n\to \infty }\left(\begin{array}{c}n_R\\k_R-1\end{array}\right)\left(\begin{array}{c}n_B\\k_B\end{array}\right)\frac{1}{n^{k-1}} = \frac{ \alpha _R^{k_R-1}}{(k_R-1)!}\frac{ \alpha _B^{k_B}}{k_B!}, \end{equation}
so that for every
$y\gt 0$
we have pointwise convergence
\begin{equation*} \lim _{n \to \infty } P_{k,R}^n\big( (y/n)^{p/d} \big) = \sum _{\substack { k_R+k_B = k \\ k_R \ge 1}} \frac { \alpha _R^{k_R-1}}{(k_R-1)!}\frac { \alpha _B^{k_B}}{k_B!} y^{(k-1)/d} \mathcal {I}_R\big(k_R, k_B, \alpha _R, y\big).\end{equation*}
We next prove that the convergence is dominated in the sense of assumption a), with
$d/p$
instead of
$d$
. In view of (4.4) and the limit (4.5) it is sufficient to establish an inequality
\begin{equation} \sup _{n \ge n_k} n^{k-1} I_R\big(k_R, k_B, (y/n)^{p/d} \big) \le \ell _{R, k_R, k_B}(y), \end{equation}
for some
$n_k\ge 1$
and a suitable function
$\ell _{R, k_R, k_B}$
such that
\begin{equation} \int _0^\infty \ell _{R, k_R, k_B}(y) y^{p/d -1} dy \lt \infty . \end{equation}
We begin by noticing that, if
$A \subseteq \mathbb{T}^d$
is not empty, then for
$0\lt z \le 2^{-p}$
we have
$|D_{\mathbb{T}^d}(A, z)| \ge \omega _d z^{d/p}$
, while for
$2^{-p} \lt z \le \sqrt{d}/2$
it holds
$\big|D_{\mathbb{T}^d}(A,z)\big| \ge \omega _d 2^{-d}$
and for
$z \ge \sqrt{d}/2$
we have
$\big|D_{\mathbb{T}^d}(A,z)\big| = 1$
. Therefore, one can find a constant
$c=c(d)\gt 0$
such that
\begin{equation} 1- \big|D_{\mathbb{T}^d}(A,z)\big| \le \exp \big( - c z^{p/d} \big) \quad \text{for every $z\gt 0$.} \end{equation}
Next, we argue that, for every
$z \gt 0$
, one has the inequality
\begin{equation} \big| \Theta _{\mathbb{T}^d}(n_R, n_B, z) \big| \le \left [ (k-1)^d \omega _d z^{d/p} \right ]^{k-1 }. \end{equation}
Indeed, every tree (even not necessarily bipartite) with edge weights smaller than
$z$
can be obtained starting from any given ‘root’
$x_1$
and by recursively choosing a sequence of points such that
\begin{equation*} x_{i+1} \in D_{\mathbb {T}^d}\left(\left \{ x_j \right \}_{j =1}^i, z\right) \subseteq D_{\mathbb {T}^d}(x_1, (j-1)^p z),\end{equation*}
where the second inclusion follows by the triangle inequality and a simple induction. Hence, conditionally upon
$x_1$
, the set
$\Theta _{\mathbb{T}^d}(n_R, n_B, z)$
is contained in the Cartesian product
$\left \{ x_1 \right \}\times D_{\mathbb{T}^d}\big(x_1, (k-1)^pz\big)^{(k-1)}$
, and (4.9) follows. Using the inequalities (4.8) and (4.9) and further assuming that
$k_B \ge 1$
(recall that we already have
$k_R \ge 1$
by hypothesis), we have
\begin{equation*} \begin{split} I_R & (k_R, k_B, z ) \\ & = \int _{\Theta _{\mathbb{T}^d}(k_R, k_B, z)} \left( 1 - \left|D_{\mathbb{T}^d}\left(\left \{ b_j \right \}_{j=1}^{k_B}, z\right)\right|\right)^{n_R - k_R}\left ( 1 - \left|D_{\mathbb{T}^d}\left(\left \{ r_i \right \}_{i=1}^{k_R}, z\right)\right| \right )^{n_B - k_B} d r d b \\ & \le \int _{\Theta _{\mathbb{T}^d}(k_R, k_B, z)} \exp \!\left ( - c (n-k) z^{p/d} \right ) d r d b \\ & = \left|\Theta _{\mathbb{T}^d}(k_R, k_B, z) \right| \exp \!\left ( - c (n-k) z^{d/p} \right ) \\ & \le \left [ (k-1)^d \omega _d z^{d/p} \right ]^{k-1} \exp \!\left ( - c (n-k) z^{d/p} \right ). \end{split} \end{equation*}
Substituting
$z = (y/n)^{p/d}$
yields the domination (4.6) with
\begin{equation*} \ell _{R, k_R, k_B}(y) = \left [ (k-1)^d \omega _d y \right ]^{k-1} \exp \!\left ( - c y/2 \right )\end{equation*}
for
$n \ge 2k$
, and clearly (4.7) holds using that
$c\gt 0$
and
$p/d\lt 1$
. Arguing similarly in the case
$k_B=0$
,
$k_R=1$
, we obtain
\begin{equation*}I_R(1,0, z) \le \exp \!\left ( - (n-1) cz^{d/p} \right ),\end{equation*}
yielding a similar domination also in this case. Finally, in the cases
$k_B = 0$
and
$k_R \ge 2$
, there is actually nothing to prove, since
$\Theta _{\mathbb{T}^d}(k_R, k_B, z)$
is empty.
Performing similar arguments for
$P_{k,B}^n$
yields instead
\begin{equation*} \lim _{n \to \infty } P_{k,B}^n\big( (y/n)^{p/d} \big) = \sum _{\substack { k_R+k_B = k \\ k_B \ge 1}} \frac { \alpha _R^{k_R}}{k_R!}\frac { \alpha _B^{k_B-1}}{(k_B-1)!} y^{(k-1)/d} \mathcal {I}_B\big(k_R, k_B, \alpha _R, y\big),\end{equation*}
with analogous definitions and dominations. Thus, the validity of assumption a) in this case is fully established.
It is convenient to notice here that, by exchanging the order of integration, we have
\begin{equation*} \begin{split} & \int _0^\infty y^{(k-1)/d} \mathcal{I}_R(k_B, k_R, \alpha _R, y) y^{1/d -1} d y \\ &\quad = \int _{\Theta \!\left(k_R, k_B\right)} \int _0^\infty \exp \!\left ( -y \left ( \alpha _R |D\!\left(\left \{ b_j \right \}_{j=1}^{k_B}\right)\left| + \alpha _B D\!\left(\left \{ r_i \right \}_{i=1}^{k_R}\right)\right| \right ) \right ) y^{k/d-1} d y \delta _0(r_1) d r d b \\ & \quad= \Gamma (k/d) \int _{\Theta \!\left(k_R, k_B\right)} \left ( \alpha _R |D\!\left(\left \{ b_j \right \}_{j=1}^{k_B}\right)| + \alpha _B \left| D\!\left(\left \{ r_i \right \}_{i=1}^{k_R}\right)\right| \right )^{-k/d} \delta _0(r_1) d r d b. \end{split} \end{equation*}
This identity, after some simple manipulations and taking into account also the analogous contributions from the terms
$\mathcal{I}_B\big(k_R, k_B, \alpha _R, y\big)$
eventually yields the claimed expression for
$\beta _{b\text{MST}}(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) \gt 0$
, e.g.
$M = d^{p/2}$
), it follows that
$C_k^n(z)=1$
if
$z \ge 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 \ge k$
).
It follows that
\begin{equation*} \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 $.} \end{equation*}
To obtain an upper bound we use Lemma 2.4 on each
$G^n$
– we can assume
$k\ge 2$
and
$n \ge k$
. Given the sets
$C_i$
, for
$i= 1\ldots, m$
with
$m \le 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
\begin{equation*} w(i,j) \le \mathsf {d}_{\mathbb {T}^d}(r_i, b_j)^p,\end{equation*}
hence
\begin{equation*}\frac {1}{n^{1-\frac {1}{d}}}\int _{0}^{\infty }\left ( \mathbb {E}\!\left [ C_{k}^n(z) \right ]-1 \right ) dz \le \mathcal {C}_{\text{MST}}\left(G^n_k\right).\end{equation*}
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)\gt 0$
,
\begin{equation*} \mathcal {C}_{\text{MST}}\left(G^n_k\right) \le C\!\left ( \mathcal {C}_{\text{MST}}\left(R^n_k\right) + \sum _{i=1}^m \mathsf {d}_{\mathbb {T}^d}(r_i, b_i)^p \right ), \end{equation*}
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)\gt 0$
,
\begin{equation*} \mathcal {C}_{\text{MST}}\left(R^n_k\right) + \sum _{i=1}^m \mathsf {d}_{\mathbb {T}^d}(r_i, b_i)^p \le C m^{1-p/d} + \sum _{i=1}^m \min _{j=1,\ldots, n}|r_i - Y_j|^p,\end{equation*}
where we also used that
$b_i = \mathsf{n}_{G^n}(r_i)$
. We finally apply (2.9) 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)\gt 0$
,
\begin{equation*} \mathbb {E}\left [ \mathcal {C}_{\text{MST}}\left(R^n_k, B^n_k\right) \right ] \le C \!\left ( m^{1-p/d} + m n^{-p/d} \right ) \le C \!\left ( \left ( \frac {n}{k} \right )^{1-p/d} + \frac {n}{k} n^{-p/d} \right ).\end{equation*}
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) \le |x-y|$
, so that, for any
$p\gt 0$
,
$R$
,
$B \subseteq [0,1]^d$
,
\begin{equation*} \mathcal {C}_{\text{MST}}^p\big(R,B |\mathbb {T}^d\big) \le \mathcal {C}_{\text{MST}}^p(R,B),\end{equation*}
for any set of points
$R$
,
$B \subseteq [0,1]^d$
, where
$\mathcal{C}_{\text{MST}}^p\left(R,B |\mathbb{T}^d\right)$
denotes the MST cost functional on
$\mathbb{T}^d$
. Letting
$p \to \infty$
yields also
$\mathcal{C}_{\text{MST}}^\infty \left(R,B |\mathbb{T}^d\right) \le \mathcal{C}_{\text{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}_{\text{MST}}^\infty (R,B) \le \delta$
, then, for every
$p\gt 0$
,
\begin{equation*} \mathcal {C}_{\text{MST}}^p(R,B) \le \mathcal {C}_{\text{MST}}^p\big(R,B |\mathbb {T}^d\big) +\mathcal {C}_{\text{MST}}^p(R_\delta, B_\delta ),\end{equation*}
where
$R_\delta = R\setminus [ \delta, 1- \delta ]^d$
,
$B_\delta = B\setminus [ \delta, 1- \delta ]^d$
.
Proof. Indeed, let
$T$
be an MST for
$R$
,
$B$
projected on
$\mathbb{T}^d$
. The assumption gives that for every
$\left \{ r,b \right \} \in T$
, since
$|r-b|\le \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}_{\text{MST}}^p(R,B)$
from above by
$\mathcal{C}_{\text{MST}}^p\left(R,B|\mathbb{T}^d\right)$
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 \ge 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
\begin{equation*} \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.\end{equation*}
Then, for every
$p\gt 0$
, there exists a constant
$C = C(d,p, \alpha _R)\gt 0$
such that, for
$n$
large enough,
\begin{equation*} \mathbb {E}\!\left [ \mathcal {C}_{\text{MST}}^p\left ( R^n \right ) \right ] \le C n^{1-p/d}, \quad \text {and} \quad \mathbb {E}\!\left [ \mathcal {C}_{\text{MST}}^p\left ( R^n, B^n \right ) \right ] \le C n^{1-p/d},\end{equation*}
as well as, for some constant
$C=C(d,p, \alpha _R) \gt 0$
,
\begin{equation*} \mathbb {E}\!\left [ \left ( \mathcal {C}_{\text{MST}}^\infty \left ( R^n \right ) \right )^p \right ]\le C\!\left ( \frac {\log n}{n} \right )^{p/d}, \quad \mathbb {E}\!\left [ \left ( \mathcal {C}_{\text{MST}}^\infty \left ( R^n, B^n \right ) \right )^p \right ]\le C\!\left ( \frac {\log n}{n} \right )^{p/d},\end{equation*}
and finally, for every
$a\gt 0$
, there exists
$C= C(d,a,\alpha _R)\gt 0$
, such that for
$n$
large enough,
\begin{equation} \mathbb{P}\!\left( \mathcal{C}_{\text{MST}}^\infty \left ( R^n \right ) \gt C ( \log (n)/n)^{1/d} \right) \le \frac{C}{n^a}, \quad \mathbb{P}\!\left( \mathcal{C}_{\text{MST}}^\infty \left ( R^n, B^n \right ) \gt C ( \log (n)/n)^{1/d} \right) \le \frac{C}{n^a}. \end{equation}
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.,
\begin{equation*} C_\gamma \,:\!=\, \sup _{s\neq t} \frac { |\gamma (t)-\gamma (s)|}{|t-s|^{1/d}} \lt \infty .\end{equation*}
While many constructions for
$d=2$
are historically well known, the case of general
$d$
is established in detail e.g. in [Reference Milne23]. 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
\begin{equation*} Z_{(1)} = \min _{i=1, \ldots, m} Z_i \le Z_{(2)} \le \ldots \le Z_{(m)} = \max _{i=1, \ldots, m} Z_i\end{equation*}
and let
$T$
be the connected graph on
$\left \{ \gamma (Z_i) \right \}_{i=1}^{m}$
with edges
\begin{equation*} \left \{ \left \{ \gamma \!\left(Z_{(i)}\right), \gamma \!\left(Z_{(i+1)}\right) \right \} : \, i=1, \ldots, m-1 \right \}.\end{equation*}
We have
\begin{equation*} \mathcal {C}_{MST}^p\left ( \left ( \gamma (Z_i) \right )_{i=1}^{m} \right ) \le \sum _{i=1}^{m-1} \left|\gamma \big(Z_{(i+1)}\big)- \gamma \big(Z_{(i)}\big)\right|^p \le C_\gamma \sum _{i=1}^{m-1} \left|Z_{(i+1)}- Z_{(i)}\right|^{p/d}.\end{equation*}
The law of each
$Z_{(i+1)} - Z_{(i)}$
is beta
$B(1,n)$
, so that, for every
$q \in \mathbb{N}$
,
\begin{equation*} \mathbb {E}\!\left [ \left| Z_{(i+1)} - Z_{(i)} \right|^q \right ] = \prod _{r=0}^{q-1}\frac {r+1}{m+r+1} \le C(q) m^{-q}.\end{equation*}
Bounding the
$p/d$
-th moment with the
$\left \lceil p/d \right \rceil$
-th moment gives that, for
$p\gt 0$
, there exists a constant
$C(p)$
such that, for every
$m$
and
$i$
,
\begin{equation*} \mathbb {E}\!\left [ \left| Z_{(i+1)} - Z_{(i)} \right|^{p/d} \right ] \le C(p) m^{-{p/d}}\end{equation*}
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.9). The remaining inequalities follow analogously, noticing that
\begin{equation*} \max _{i=1, \ldots, m-1} \left| Z_{(i+1)} - Z_{(i)} \right| = \max _{i=1, \ldots, m} |Z_i - \mathsf {n}(Z_i)| = M^m,\end{equation*}
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 \ge 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
\begin{equation*} \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.\end{equation*}
Then, for every
$p\gt 0$
, there exists a constant
$C = C(p,d)\gt 0$
such that, for
$n$
large enough,
\begin{equation*} \mathbb {E}\!\left [ \mathcal {C}_{\text{MST}}^p\big(R^n, B^n\big) \right ] -\mathbb {E}\!\left[ \mathcal {C}_{\text{MST}}^p\left(R^n, B^n | \mathbb {T}^d \right)\right] \le C n^{1-(p+1)/d} ({\log}\,n)^{(p+1)/d}. \end{equation*}
In particular, for every
$p \lt d$
,
\begin{equation*} \lim _{n \to \infty } \frac { \mathbb {E}\!\left [ \mathcal {C}_{\text{MST}}^p(R^n, B^n) \right ]}{n^{1-p/d}} = \beta _{b\text{MST}}(p,d)\end{equation*}
with
$\beta _{b\text{MST}}(p,d)$
as in Theorem
1.2
.
Proof. Let
$C\gt 0$
be as in (4.10) with
$a\gt 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\gt 0$
, in particular for
$a\gt p/d$
(and a suitable constant
$C\gt 0$
) all cubes
$Q$
with
$|Q| = \delta ^d$
have non-empty intersections both with
$R^n$
and
$B^n$
. Let
$E$
be the event where both these conditions occur as well as
$\mathcal{C}_{\text{MST}}^\infty (R^n, B^n) \le \delta$
. In the event
$E$
, we may apply Lemma 4.4, otherwise we simply bound
$\mathcal{C}_{\text{MST}}^p(R^n, B^n) \le n d^{p/2}$
and use the fact that
$\mathbb{P}(E^c)\le C/n^a$
for
$a$
arbitrary large.
We are then reduced to bound from above
\begin{equation*} \mathbb {E}\!\left [ \mathcal {C}_{\text{MST}}^p\left ( R^n_\delta, B^n_\delta \right ) I_E \right ]\end{equation*}
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 \le C \delta ^{-(d-1)}$
, for some
$C = C(d)\gt 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$
,
\begin{equation*} \mathcal {C}_{\text{MST}}^p\left ( R^n_\delta, B^n_\delta \right ) \le \sum _{i=1}^m \mathcal {C}_{\text{MST}}^p\left ( R^n_i, B^n_i \right ) + m \delta ^{p}.\end{equation*}
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{equation*} \begin{split} \mathbb{E}\!\left [ \mathcal{C}_{\text{MST}}^p\left ( R^n_i, B^n_i \right ) I_E \right ] & \le \delta ^p \mathbb{E}\!\left [ \mathcal{C}_{\text{MST}}^p\left ( R^n_i, B^n_i \right ) I_{\left \{ N_R(Q_i)\gt 0, N_B(Q_i)\gt 0 \right \}} \right ]\\ & \le 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)\gt 0 \right \}} \right ] \right )\\ & \le C\delta ^p \log n,\end{split} \end{equation*}
having used that
\begin{equation*} \mathbb {E}\!\left [ N_R(Q_i)^{1-p/d} \right ] \le \mathbb {E}\!\left [ N_R(Q_i) \right ]^{1-p/d} \le C ({\log}\,n)^{1-p/d}\end{equation*}
and
\begin{equation*} \mathbb {E}\!\left [ N_R(Q_i)^{-p/d} I_{\left \{ N_R(Q_i)\gt 0 \right \}} \right ] \le 1.\end{equation*}
It follows that, for some (other) constant
$C = C(p,d)\gt 0$
,
\begin{equation*}\mathbb {E}\!\left [ \mathcal {C}_{\text{MST}}^p\left ( R^n_i, B^n_i \right ) I_E \right ] \le C m \delta ^p \log n = C \delta ^{p-d+1}\log n,\end{equation*}
that eventually gives the thesis.
We end the proof of Theorem 1.2 with a concentration result to improve from convergence of expectations to almost sure convergence.
Proposition 4.7.
Let
$d \ge 1$
. For
$n \ge 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
\begin{equation*} \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.\end{equation*}
Then, for every
$p \in (0, d/2)$
if
$d \in \left \{ 1,2 \right \}$
or any
$p\gt 0$
if
$d \ge 3$
, almost sure convergenc holds:
\begin{equation*} \lim _{n \to \infty } \frac { \mathcal {C}_{\text{MST}}^p(R^n, B^n)- \mathbb {E}\!\left [ \mathcal {C}_{\text{MST}}^p(R^n, B^n) \right ]}{n^{1-p/d}} = 0.\end{equation*}
Proof. Consider the function
\begin{equation*} \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}_{\text{MST}}^p\left ( \left \{ x_i \right \}_{i=1}^{n_R}, \left \{ y_j \right \}_{j=1}^{n_B} \right ). \end{equation*}
We argue separately for
$p\lt 1$
and
$p\ge 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^{\prime}_1$
, 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{equation*} \begin{split} f(x^{\prime},y^{\prime}) & \le f(x,y) + \sum _{\left \{ y_j, x_1 \right \} \in T} \left | | y_j-x^{\prime}_1|^p - | y_j-x_1|^p \right |\\ & \le f(x,y) + \sum _{\left \{ y_j, x_1 \right \} \in T} |x_1-x^{\prime}_1 |^p \quad \text{(by the triangle inequality, since $p\le 1$)}\\ & \le f(x,y) + \deg _{T}(x_1) |x_1-x^{\prime}_1|^p \\ & \le f(x,y) + \Delta (T) d^{p/2}, \end{split} \end{equation*}
where
$\Delta (T)$
denote the maximum degree of
$T$
. Arguing symmetrically, we obtain
\begin{equation*} |f(x,y) - f(x^{\prime},y^{\prime})| \le \Delta (T) d^{p/2} + \Delta (T^{\prime}) d^{p/2}.\end{equation*}
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\ge 2$
, that there exists
$C = C(q)\gt 0$
such that
\begin{equation*} \begin{split} \mathbb{E}\!\left [ \left | \mathcal{C}_{\text{MST}}^p\left ( R^n, B^n \right ) - \mathbb{E}\left [ \mathcal{C}_{\text{MST}}^p\left ( R^n, B^n \right ) \right ] \right |^q \right ] & \le C n^{q/2} \mathbb{E}\!\left [ \left ( \Delta (T^n) d^{p/2} \right )^q \right ]\\ & \le C^{\prime} n^{q/2} ({\log}\,n)^q, \end{split} \end{equation*}
where we used (3.1) and
$C^{\prime}= C(d,q,\alpha _R, \alpha _b)\gt 0$
is a constant. Dividing both sides by
$n^{q(1-p/d)}$
and using Markov’s inequality yields, for every
$\epsilon \gt 0$
,
\begin{equation*} \mathbb {P}\!\left ( \left | \mathcal {C}_{\text{MST}}^p\left ( R^n, B^n \right ) - \mathbb {E}\!\left [ \mathcal {C}_{\text{MST}}^p\left ( R^n, B^n \right ) \right ] \right |/n^{1-p/d}\gt \epsilon \right ) \le C^{\prime} \epsilon ^{-q} n^{q(p/d-1/2)} ({\log}\,n)^q,\end{equation*}
that is summable if
$p/d-1/2\lt 0$
, i.e.,
$p\lt d/2$
, and
$q$
is sufficiently large.
In the case
$p \ge 1$
, we use the fact that
$f$
is Lipschitz (being minimum of Lipschitz functions) with a.e. derivative given by
\begin{equation*} \nabla _{x_i} f(x,y) = \sum _{\substack { j=1,\ldots, n_B \\ \left \{ x_i, y_j \right \} \in T}} p |x_i-y_j|^{p-2} (x_i-y_j),\end{equation*}
\begin{equation*} \nabla _{y_j} f(x,y) = \sum _{\substack { i=1,\ldots, n_R \\ \left \{ x_i, y_j \right \} \in T}} p |x_i-y_j|^{p-2} (x_i-y_j),\end{equation*}
We bound from above, using the Cauchy-Schwartz inequality
\begin{equation*} |\nabla _{x_i} f(x,y)|^2 \le p^2 \Delta (T) \sum _{\substack { j=1,\ldots, n_B \\ \left \{ x_i, y_j \right \} \in T}} |x_i-y_j|^{2(p-1)}.\end{equation*}
It follows that the (Euclidean) norm of the derivative is bounded above by
\begin{equation*} |\nabla f(x,y)|^2 \le 2 p^2 \Delta (T) \mathcal {C}_{\text{MST}}^{2(p-1)}(x,y) \le 2 p^2 \Delta (T) \left ( \mathcal {C}_{\text{MST}}^\infty (x,y) \right )^{2(p-1)} n,\end{equation*}
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\gt 0$
Lemma 3.2 and Lemma 4.5 yield that, for some constant
$C = C(d,p,q)\gt 0$
and
$n$
sufficiently large,
\begin{equation*} \begin{split} \mathbb{E}\!\left [ \Delta (T^n)^{q/2} \left ( \mathcal{C}_{\text{MST}}^\infty \big(R^n,B^n\big) \right )^{q(p-1)} \right ] & \le \mathbb{E}\!\left [ \Delta (T^n)^{q} \right ]^{1/2} \mathbb{E}\!\left [ \left ( \mathcal{C}_{\text{MST}}^\infty \big(R^n,B^n\big) \right )^{2q(p-1)} \right ]^{1/2}\\ & \le C \log (n)^{q/2} \left ( \frac{ \log n}{n} \right )^{q(p-1)/d} \end{split} \end{equation*}
It follows that (possibly for a larger constant
$C$
)
\begin{equation*} \mathbb {E}\!\left [ \left|\nabla f\!\left(\left \{ X_i \right \}_{i=1}^n, \left \{ Y_i \right \}_{i=1}\right) \right|^q \right ] \le C \log (n)^{q\!\left ( 1/2+(p-1)/d \right )} n^{q(1/2- (p-1)/d)}.\end{equation*}
Poincaré’s inequality for the uniform measure on the unit cube, see e.g. the argument in [Reference Ledoux21, Prop. 2.8], gives that, for some constant
$C = C(q)\gt 0$
,
\begin{equation*} \mathbb {E}\!\left [ \left | f\!\left( \left \{ X_i \right \}_{i=1}^n, \left \{ Y_i \right \}_{i=1}\right) -\mathbb {E}\!\left [ f\!\left( \left \{ X_i \right \}_{i=1}^n, \left \{ Y_i \right \}_{i=1}\right) \right ] \right |^q \right ] \le C(q) \mathbb {E}\!\left [ |\nabla f\!\left( \left \{ X_i \right \}_{i=1}^n, \left \{ Y_i \right \}_{i=1}\right) |^q \right ],\end{equation*}
thus using Markov’s inequality, for every
$\epsilon \gt 0$
, we have
\begin{equation*} \mathbb {P}\!\left ( \left | \mathcal {C}_{\text{MST}}^p\left ( R^n, B^n \right ) - \mathbb {E}\!\left [ \mathcal {C}_{\text{MST}}^p\left ( R^n, B^n \right ) \right ] \right |/n^{1-p/d}\gt \epsilon \right )\le C \frac { ( \log n)^{q\!\left ( 1/2+(p-1)/d \right )}}{\epsilon ^q n^{q(1/2-1/d)}},\end{equation*}
which is summable if
$q$
is large enough and
$d \ge 3$
.
Acknowledgements
Both authors warmly thank the anonymous referees for their feedback and suggestions, which improved the quality of this paper. D.T. is a member of the INdAM GNAMPA group and was partially supported by GNAMPA project 2020 ‘Problemi di ottimizzazione con vincoli via trasporto ottimo e incertezza’.
Appendix A. A concentration inequality in
$\textit{L}^{\textit{q}}$
McDiarmid inequality [Reference McDiarmid22] is a simple but effective concentration inequality often used in random combinatorial optimisation 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 on concentration inequalities for discrete time exponential martingales. In this appendix we show an analogous result where we replace the Lipschitz condition with a ‘Sobolev’ one and use the 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
\begin{equation*} f\,:\, E \to {\mathbb {R}}, \quad g_i\,:\, E \to [0,\infty ] \quad \text {for $i=1,\ldots, n$,}\end{equation*}
be such that, for every
$i \in \left \{ 1,\ldots, n \right \}$
, for every
$x$
,
$x^{\prime}\in E$
with
\begin{equation*} x= (x_1,\ldots, x_i, \ldots, x_n) \quad x^{\prime}= \left(x_1, \ldots, x^{\prime}_i, \ldots, x_n\right)\end{equation*}
then
\begin{equation*} \left | f(x) - f(x^{\prime}) \right | \le g_i(x) +g_i(x^{\prime}).\end{equation*}
For every
$q \ge 2$
, there exists
$C= C(q)\gt 0$
such that, if
$X = (X_i)_{i=1}^n$
are independent random variables, with
$X_i\,:\, \Omega \to E_i$
, then
\begin{equation*} \mathbb {E}\!\left [ \left| f(X) - \mathbb {E}\!\left [ f(X) \right ]\right|^q \right ] \le C(q) n^{q/2-1} \sum _{i=1}^n \mathbb {E}\!\left [ g_i(X)^q \right ].\end{equation*}
Proof. Write
$\mathbb{E}_{i}$
for the conditional expectation with respect to the variables
$\left ( X_j \right )_{j\le i}$
, i.e., conditioned on the values of these variables. 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
\begin{equation*} 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 ].\end{equation*}
The Burkholder-Gundy inequality [Reference Burkholder and Gundy7] gives, for some constant
$C=C(q) \ge 0$
,
\begin{equation} \mathbb{E}\!\left [ \left| f(X) - \mathbb{E}\!\left [ f(X) \right ]\right|^q \right ] \le 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 ]. \end{equation}
To simplify notation, we introduce a copy of the independent variables
$\big(X^{\prime}_i\big)_{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$
,
\begin{equation*} \mathbb {E}_{ i} \left [ f(X) \right ] = \mathbb {E}^{\prime}\left [ f\!\left(X_1, \ldots, X_i, X^{\prime}_{i+1}, \ldots X^{\prime}_n\right) \right ].\end{equation*}
This leads to
\begin{equation*} \begin{split} & \left | \mathbb{E}_{ i} \left [ f(X) \right ] - \mathbb{E}_{ i-1} \left [ f(X) \right ] \right |\\[5pt] & \quad = \left | \mathbb{E}^{\prime}\left [ f\!\left(X_1, \ldots, X_i, X^{\prime}_{i+1}, \ldots X^{\prime}_n\right) \right ] - \mathbb{E}^{\prime}\left [ f\!\left(X_1, \ldots, X_{i-1}, X^{\prime}_i, \ldots X^{\prime}_n\right) \right ] \right | \\[5pt] & \quad \le \mathbb{E}^{\prime}\left [ \left | f\!\left(X_1, \ldots, X_i, X^{\prime}_{i+1}, \ldots X^{\prime}_n\right) - f\!\left(X_1, \ldots, X_{i-1}, X^{\prime}_i, \ldots X^{\prime}_n\right) \right | \right ]\\[5pt] & \quad \le \mathbb{E}^{\prime}\left [ g_i \left(X_1,\ldots, X_i, X^{\prime}_{i+1}, \ldots, X^{\prime}_n\right) + g_i \left(X_1,\ldots, X_{i-1}, X^{\prime}_i, \ldots, X^{\prime}_n\right) \right ]\\[5pt] & \quad = \mathbb{E}_{ i} \left [ g_i \right ] +\mathbb{E}_{{i-1}} \left [ g_i \right ]. \end{split} \end{equation*}
Using these inequalities in (A.1) yields
\begin{equation*} \begin{split} \mathbb{E}\!\left [ \left| f(X) - \mathbb{E}\!\left [ f(X) \right ]\right|^q \right ] & \le 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 ]\\ & \le 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 ]\\ & \le \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 ]\\ & \le 2 \tilde{C}(q) n^{q/2-1} \sum _{i=1}^n\mathbb{E}\!\left [ g_i^q \right ], \end{split} \end{equation*}
hence the thesis.
