Proof of 1. Let \(r\) be so that the expected average degree of \(G_M(n;r)\) is equal to \(\Delta\). Set \(G_M^n(r)\) to be the Poisson random geometric graph with the same connectivity radius. For \(\alpha\) small enough, we have that the expected average degree of \(G_M^n(r)\) is \(\Delta' = (1 + o_{\alpha \to 0}(1))\Delta\) by 6 along with 39. Let \(V(G_M^n)\) denote the vertex set of \(G_M^n\). Set \(\mathcal{G} = \{|V(G_M^n)| = n\}\,.\) Since \(|V(G_M^n)|\) is a Poisson variable of mean \(n\), Stirling’s formula shows \(\mathbb{P}(\mathcal{G}) = (1 + o(1)) (2\pi n)^{-1/2}\).

Note that for \(\Delta\) sufficiently large we may use 9 to show \(\overline{\mu}(\Delta') \in[1,1 + \varepsilon/2]\), which will allow us to omit \(\overline{\mu}(\Delta')\) in this regime by only replacing \(\varepsilon\) with \(\varepsilon/2\).

Define the event \[\mathcal{A} = \left\{d_{{\mathrm{GH}}}\left(\left(\mathring{G}_M^n(r), \frac{r}{\overline{\mu}(\Delta')} d_G\right),(M, d_M) \right) > \varepsilon\right\}\] and note that \[\begin{align} \mathbb{P}\left(d_{{\mathrm{GH}}}\left(\left(\mathring{G}_M(n;r), \frac{r}{\overline{\mu}(\Delta')} d_G\right),(M, d_M) \right) > \varepsilon\right) = \mathbb{P}(\mathcal{A} \,|\,\mathcal{G}) \leq 3 \sqrt{n} \mathbb{P}(\mathcal{A}) \leq e^{-\Omega(\log^2 n)} \end{align}\] where in the last inequality we used 2 and 3. Using 10 and recalling that \(\Delta' = (1 + o_{\alpha \to 0}(1))\Delta\) completes the proof. ◻

Proof. Set \(\phi = \log_z = (\exp_z)^{-1}: U \to T_z M \to \mathbb{R}^d\) where we use an orthonormal basis for \(T_zM\) to identify \(T_zM\) with \(\mathbb{R}^d\), and \(\log_z\) is the inverse of the exponential map \(\exp_z:T_zM \to M\) restricted to a small enough neighborhood of \(0\) that it is a diffeomorphism. For a point \(y \in U\) we set \(u = \phi(y)\) and note that in these coordinates the metric satisfies \[\label{eq:normal-coords-error} g_{ij}(u) = \delta_{ij} + O(|u|^2)\tag{1}\] (see, e.g., [17]). Taking \(\delta\) sufficiently small ensures that \(\phi\) is \(e^\eta\)-bi-Lipschitz. The Riemannian volume element \(dM\) is \[dM = \sqrt{\det(g_{ij})} du^1 \wedge \cdots \wedge du^d\] (see [17]) and so combining with 1 shows \(dM = (1 + O(|u|^2)) du^1 \wedge \cdots \wedge du^d\). Taking \(\delta\) small enough forces the \((1 + O(|u|^2))\) coefficient to lie in \([e^{-\eta},e^\eta]\) which then completes the proof. ◻

Proof. We note that the fact that \(\mu(\lambda)\) is non-increasing is a consequence of 8. To see that \(\lim_{\lambda \to \infty} \mu(\lambda) = 1\), let \(C_\infty(\lambda)\) denote the unique infinite cluster of \(G_{\mathbb{R}^d}^\lambda(1)\). For \(x \in \mathbb{R}^d\) let \(\mathring{x}(\lambda) \in C_\infty(\lambda)\) denote the closest point \(C_\infty(\lambda)\) to \(x\). Let \(d_\lambda\) denote the graph distance on \(C_\infty(\lambda)\). The constant \(\mu(\lambda)\) is defined as the almost-sure limit \[\lim_{n \to \infty} \frac{d_\lambda(\mathring{0}(\lambda),\mathring{n}(\lambda))}{n} = \mu(\lambda)\] where we write \(0 = (0,0,\ldots,0) \in \mathbb{R}^d\) and \(n = (n,0,\ldots,0) \in \mathbb{R}^d\). This limit is shown to exist by a subadditive ergodic theorem argument in [5] and so in fact we also have \(\mu(\lambda) \leq \mathbb{E}d_\lambda(\mathring{0}(\lambda),\mathring{1}(\lambda))\). Note that if we take \(\lambda \to \infty\) we almost surely have \(d_\lambda(\mathring{0}(\lambda),\mathring{1}(\lambda)) \to 1.\) By the dominated convergence theorem we see that \(\mathbb{E}d_\lambda(\mathring{0}(\lambda),\mathring{1}(\lambda)) \to 1\) completing the proof. ◻

Proof. Let \(\eta > 0\) be small enough so that \(\lambda_0 e^{-\eta} > \lambda_c.\) For each \(z \in M\) let \(\delta_z \in (0,1)\) and \(u_z\) be guaranteed from 6; we may further reduce \(\delta_z\) so that \([-\delta_z, \delta_z]^d\) lies in the image of \(u_z\). Define \(V_z = u_z^{-1}((-\delta_z,\delta_z)^d)\) and note that \(\{V_z\}_{z \in M}\) forms an open cover of \(M\). By compactness of \(M\) there is a finite set \(\{z_1,\ldots,z_k\}\) so that \(\mathcal{U} = \{V_{z_j}\}_{j = 1}^k\) is an open cover of \(M\).

Define the graph \(H\) with vertex set \(z_1,\ldots,z_k\) with edges defined by \(E(H) = \{\{i,j\} : V_{z_i} \cap V_{z_j} \neq \emptyset\}.\) Note that since \(M\) is connected, the graph \(H\) is connected too. For each pair \(\{i,j\} \in E(H)\) we may find a point \(w_{i,j} \in V_{z_i} \cap V_{z_j}\) and \(\varepsilon_{i,j}\) so that \(B_M(w_{i,j},\varepsilon_{i,j}) \subset V_{z_i} \cap V_{z_j}.\) By potentially further shrinking \(\varepsilon_{i,j}\) we may define \(U_{i,j} = u_{z_i}^{-1}(u_{z_i}(w_{i,j}) + [-\varepsilon_{i,j},\varepsilon_{i,j}]^d)\). Let \(G_i\) and \(G_{i,j}\) denote the induced subgraph of \(G_M^n(r)\) whose vertices lie in \(V_{z_i}\) and \(U_{i,j}\) respectively. Let \(\mathcal{E}_i\) denote the event that \(G_i\) contains exactly one component of \(d_M\)-diameter at least \(r\phi\); define \(\mathcal{E}_{i,j}\) analogously. Note that by 11 we have \[\mathbb{P}\left(\bigcap_{j \in [k]} \mathcal{E}_j \cap \bigcap_{\{i,j\} \in E(H)} \mathcal{E}_{i,j} \right) \geq 1 - C r^{-d} \exp(-c \phi)\] for some \(C,c > 0\) depending on \(\eta,\lambda_0,M\). We will intersect with the event \(\mathcal{E} = \bigcap_{j \in [k]} \mathcal{E}_j \cap \bigcap_{\{i,j\} \in E(H)} \mathcal{E}_{i,j}\) and let \(\mathring{G}_i\) and \(\mathring{G}_{i,j}\) denote the component of largest diameter.

Note that for each \(\{i,j\} \in E(H)\) we have that \(U_{i,j} \subset V_{z_i} \cap V_{z_j}\) and so \(\mathring{G}_{i,j} \subset \mathring{G}_i \cap \mathring{G}_j\). In particular, for each edge \(\{i,j\} \in E(H)\), the largest components in \(V_{z_i}\) and \(V_{z_j}\) are in fact the same component of \(G_M^n(r)\). Since \(H\) is connected, this shows that the components \(\mathring{G}_i\) all lie in the same component of \(G_M^n(r)\) which we may call \(\kappa\).

To see that \(\kappa\) is the only component of large diameter, let \(\alpha > 0\) be the Lebesgue covering number of \(\mathcal{U} = \{V_{z_j}\}_{j = 1}^k\) meaning that if \(d_M(x,y) < \alpha\) then there is some \(i \in [k]\) so that \(x,y \in V_{z_i}\). Note that if there is a component \(\kappa'\) of \(G_M^n(r)\) of \(d_M\)-diameter \(\geq r\phi\), then there are points \(x,y \in \kappa'\) so that \(d_M(x,y) \in [r\phi,r(\phi+1)]\). By restricting \(c\), we have that \(r(\phi + 1) \leq \alpha/2\) and so there is some \(i \in [k]\) so that \(x,y \in V_{z_i}\). We note that either \(x,y\) are connected in \(G_i\) or otherwise the path from \(x,y\) exits \(V_{z_i}\) which would require having two points of distance, \(\alpha/2\) apart. On event \(\mathcal{E}\), this implies that \(\kappa' \cap G_i\) has metric diameter at least \(r\phi\) implying that \(\kappa' \subset \mathring{G}_i\). This shows that \(\kappa' \subset \kappa\), completing the proof. ◻

Proof. First, if \(r \geq n^{-1/d +\beta}\) for some \(\beta > 0\) then 33 shows the graph is connected. Otherwise, applying 12 twice shows that there is one component of \(d_M\) diameter at least \(c\), and all other components have \(d_M\)-diameter larger at most \(r \log^2 n\). Each component of \(d_M\)-diameter at most \(r \log^2 n\) has graph diameter at most \((\log n)^{O_d(1)}\), while the giant component has graph diameter \(\Omega(1/r)\). ◻

Proof. This follows from seeing that if one takes an intensity \(\lambda\) Poisson process on \(\mathbb{R}^d\) and scales by \(t\) then one obtains a \(\lambda t^{-d}\) Poisson process in distribution. ◻

Proof. Define a metric \(\sigma\) on \((e^{-\eta} r)^{-1}S \subset \mathbb{R}^d\) by taking \[\sigma(p,q) := \frac{1}{r}d_M(u^{-1}(e^{-\eta} rp), u^{-1}(e^{-\eta} rq)).\] Note that for all \(p,q \in (e^{-\eta} r)^{-1} S\) we have \[\sigma(p,q) \le \|p - q\| \le e^{2\eta} \sigma(p,q),\] by 6. We take an arbitrary extension of \(\sigma\) to all of \(\mathbb{R}^d\) which still satisfies the above inequalities.³

Next, define a measure \(\nu\) on \(\mathbb{R}^d\) by taking \[\nu(A) := \frac{\lambda}{r^d} dM( u^{-1}((e^{-\eta}r) \cdot A))\] for \(A \subset (e^{-\eta}r)^{-1}S\) and setting \(\nu(A) := \lambda\mathcal{L}(A)\) for \(A \subset (e^{-\eta}r)^{-1}S^c\).⁴ Then by 6 we have \[\lambda e^{-(d+1)\eta}\mathcal{L}(A) \leq \nu(A) \leq \lambda e^{(d+1)\eta}\mathcal{L}(A) \,.\] Define \(G^\nu\) to be the random geometric graph on \(\mathbb{R}^d\) whose vertex set is the Poisson point process with intensity measure \(\nu\), and whose edges are between pairs \(p,q\) of points with \(\sigma(p,q) \le 1\). Then we see that \[\widehat{G}_S \equiv G^\nu \cap (e^{-\eta}r)^{-1}S,\] by 14, as desired. ◻

Proof of 18. First, consider the uniqueness event \[U_r^- = \left\{ \begin{array}{c} \text{at most one component of the graph } G^-(r) \cap [-\delta/L,\delta/L]^d \\ \text{has Euclidean diameter }\geq r \gamma \log^2n \end{array} \right\}\,.\] Note that by our choice of \(L\) we have \([-\delta/L,\delta/L]^d \subset B_{\mathbb{R}^d}(0,e^{-\eta} \delta) \subset S\). Therefore, \[G^-(r) \cap [-\delta/L,\delta/L]^d = (e^{-\eta} r)G^{\underline{\lambda}}_{\mathbb{R}^d} \cap [-\delta/L,\delta/L]^d,\] and so \[\mathbb{P}((U^-_r)^c) \le \exp(-c \gamma \log^2 n)\] for \(c = c(d,\lambda_0,\beta) > 0\) and \(n \geq n_0(d,\lambda_0,\beta)\) by 11.

Now, let \(C_\infty^-\) be the unique infinite component of \(G^{\underline{\lambda}}_{\mathbb{R}^d}\). Note that whenever \(r>0\) is sufficiently small that \(2 \gamma r \log^2 n \le \delta/2L\), we have \[\label{eq:move-to-Cinf} U^-_r \cap \left\{ (e^{-\eta}r)C_\infty^- \cap B_{\mathbb{R}^d}\left(0,\frac{\delta}{2L} + \gamma r \log^2n \right) \ne \emptyset \right\} \subset \left\{ (e^{-\eta}r)C_\infty^- \cap B_{\mathbb{R}^d}\left(0,\frac{\delta}{2L} + \gamma r \log^2 n \right) \subset \kappa \right\}.\tag{8}\] This is because any component of \((e^{-\eta} r)C_\infty^- \cap [-\delta/L,\delta/L]^d\) which intersects \(B_{\mathbb{R}^d}(0,(\delta/2L) + \gamma r \log^2n)\) has Euclidean diameter at least \(\delta/2L - \gamma r \log^2n \ge \gamma r \log^2n\); \(U^-_r\) then implies that such a component must lie in \(\kappa\). Thus, on \(U^-_r\), to find a nearby point in \(\kappa\), it suffices to find a nearby point in \((e^{-\eta}r)C^-_\infty\).

Therefore, using 8 , 14, and 19 we have \[\begin{align} \mathbb{P}(\mathcal{C}_1^c \cap U^-_r) &\le \mathbb{P}\left( \begin{array}{c} \exists p \in B_{\mathbb{R}^d}(0, \delta/(2Le^{-\eta}r)) \text{ such that } \forall p' \in C_\infty^-,\\ \|p - p'\| > e^\eta \gamma \log^2n \end{array} \right) \\ &\le \sum_{\substack{p \in \mathbb{Z}^d \\ \|p\| \le \delta/(2Le^{-\eta}r)}} \mathbb{P}\left( B_{\mathbb{R}^d}(p, \gamma e^\eta \log^2n - \sqrt{d}/2) \cap C^-_\infty = \emptyset \right) \\ &\le C L^d r^{-d} \exp(-c'(\gamma \log^2 n)^{d - 1}) \end{align}\] for \(c' = c'(\underline{\lambda}) > 0\) and \(C = C(d) > 0\). Since \(d \geq 2\), for \(n \geq n_0(\underline{\lambda},d,\lambda_0,\beta)\) and some \(c'' = c''(\underline{\lambda},d,\lambda_0,\beta)\) we have \(\mathbb{P}(\mathcal{C}_1^c) \le \mathbb{P}(\mathcal{C}_1^c \cap U^-_r) + \mathbb{P}((U^-_r)^c) \le \exp(-c'' \gamma \log^2 n)\), as desired. ◻

Proof. Consider the following uniqueness event on \(G_S\): \[U := \left\{ \begin{array}{c}at most one component ofG_S \cap [ -\delta/L, \delta/L ]^d \\has Euclidean diameter at leastr \log^2 n \end{array} \right\},\] Again, our choice of \(L\) ensures that \[G_S \cap [ -\delta/L, \delta/L ]^d = G^\nu \cap [ -\delta/L, \delta/L ]^d\] and therefore \(\mathbb{P}(U^c) \le \exp(-c \log^2n)\) for \(c = c(d,\lambda_0,\beta) > 0\) and \(n \geq n_0(d,\lambda_0,\beta)\) by 11 where we use 15 to verify the hypotheses.

Now we claim that, for \(r>0\) sufficiently small, we have \[\label{eq:LB-E} U \cap \mathcal{C}_1 \subset \mathcal{C}_2\tag{9}\] where we take \(\gamma = 1\) for this instance of \(\mathcal{C}_1\). Assume that \(U \cap \mathcal{C}_1\) holds, and let \(p \in \kappa \cap B_{\mathbb{R}^d}(0, \delta/L)\) and \(q \in u\left(\mathring{G}_M^{n}(r) \cap B_M(x, \delta/2 L)\right)\). If no such \(p\) and \(q\) exist then \(\mathcal{C}_2\) holds vacuously. Recall that \(G^-(r) \subset G_S\), and so there is a unique connected component \(\kappa'\) of \(G_S \cap [-\delta/L,\delta/L]^d\) containing the largest connected component of \(G^- \cap [-\delta/L,\delta/L]^d\). The event \(U \cap \mathcal{C}_1\) implies that the Euclidean diameter of \(\kappa'\) is at least \(\delta/L - 2 \gamma r \log^2 n \geq r \log^2n\), for \(n\) sufficiently large. By \(U\), \(\kappa'\) is the unique connected component of \(G_S \cap [-\delta/L,\delta/L]^d\) of Euclidean diameter at least \(r \log^2 n\).

With this in mind, let \(\xi\) be the connected component of \(u\left(\mathring{G}_M^{n}(r) \cap B_M(x, \delta)\right) \cap [-\delta/L, \delta/L]^d\) containing \(q\). To prove that \(p \xleftrightarrow{G_S} q\), it is sufficient to show that \(\xi\) has Euclidean diameter at least \(r \log^2 n\). For \(n\) sufficiently large we have that \(r \log^2 n < \delta/2L\). Thus if the Euclidean diameter of \(\xi\) is at most \(r \log^2 n\) then \(\xi \subset B(q,r \log^2n)\); since \(u^{-1}(\xi) \subset \mathring{G}_M^n(r)\), this would imply that \(u^{-1}(\xi) = \mathring{G}^{n}_M(r)\). But then the \(d^\lambda_r\)-diameter of \(\mathring{G}_M^{n}(r)\) is at most \(O(\log^{2d}n)\), which contradicts the definition of \(\mathring{G}_M^{n}(r)\) as the largest component of \(G_M^{n}(r)\), since the component of \(G_M^{n}(r)\) containing \(\kappa\) has \(d^\lambda_r\)-diameter at least \(\Omega(1/r)\) by event \(\mathcal{C}_1\). This shows 9 , and so \(\mathbb{P}(\mathcal{C}_2^c) \le \mathbb{P}(U^c) + \mathbb{P}(\mathcal{C}_1^c) = O(\exp(-c \log^2 n))\) by 18. ◻

Proof of 21. Recall that \(\widehat{G}_S = G^\nu \cap (e^{-\eta}r)^{-1} S\) where 15 allows us to identify \(\widehat{G}_S\) in terms of a distorted metric and measure. Therefore, using 7 and 22 and \(\gamma \leq (10\rho)^{-1}\) allows us to bound \[\mathbb{P}(\mathcal{C}_3^c) \le \left[\frac{\lambda e^{d\eta}}{r^d}\mathrm{Vol}_M(B_M(x,\delta))\right]^2 \exp(-c \log^2n) \leq \exp(-c'\log^2 n)\,. \qedhere\] ◻

Proof of 17. Choose \(L' := 4 L\) and \(\gamma\) so that 21 holds. Using the fact that for all \(p,q \in \mathring{G}^{n}_M(r) \cap B_M(x,\delta)\) we have \(d^\lambda_r(p,q) {\leq } d_{G_S}(u(p), u(q))\) and the fact that \(u\) has distortion at most \(e^\eta\), we claim that \[\label{eq:lower-bound-B} \mathcal{C}_1 \cap \mathcal{C}_2 \cap \mathcal{C}_3 \subset \mathcal{C}\tag{10}\] for \(n\) sufficiently large. To see this, let \(p \in \mathring{G}_M^n(r) \cap B_M(x,\delta/L')\). By \(\mathcal{C}_1\), there is some \(p' \in \kappa\) so that \(\|u(p) - p'\| \leq \gamma r \log^2 n\). By \(\mathcal{C}_2\) we have \(p' \xleftrightarrow{G_S} u(p)\). By \(\mathcal{C}_3\) we have \(d_r^\lambda(p,u^{-1}(p')) \leq d_{G_S}(p',u(p)) \leq \log^2 n.\) The desired bound on \(\mathbb{P}(\mathcal{C}^c)\) follows from combining 10 with 18, 20, and 21. ◻

Proof of 16. Recall that \(\mathring{y}\) is equal to the (almost-surely unique) \(z \in \mathring{G}_M^n(r)\) so that \(d_M(y,z) = d_M(y,\mathring{G}_M^n(r))\). It will be sufficient to show that for all \(y \in M\) there is some point \(z \in \mathring{G}_M^n(r)\) so that \(d_M(z,y) \leq r \log^2 n.\) Since \(r \geq \Omega_{d,M}(n^{-1/d})\) we may find an \(r\)-net \(\mathcal{S} \subset M\) in the metric \(d_M\) of size \(|\mathcal{S}| \leq n^{2}\), say, for \(n\) sufficiently large. We then have \[\begin{align} \label{eq:net-for-near-giant} \mathbb{P}\left(\exists~y \in M:d_M(y,\mathring{y}) \geq r \log^2 n \right) \leq \sum_{y \in \mathcal{S}} \mathbb{P}\left(d_M(y,\mathring{y}) \geq (1/2)r \log^2 n \right)\,. \end{align}\tag{11}\] Choose \(\underline{\lambda}\) and \(\eta > 0\) via 3 for some fixed \(\varepsilon\in (0,1)\). We may then use compactness of \(M\) and 6 to choose a finite set of points \(x_1,\ldots,x_k\) along with maps \(u_{j}\) and radii \(\delta_{j}\) so that \(\bigcup_{j = 1}^k B_M(x_j, \delta_j) = M\) and \(u_j,\delta_j\) satisfy the conclusion of 6. By 18 along with 12 we have that \[\mathbb{P}\left(d_M(y,\mathring{y}) \geq (1/2)r \log^2 n \right) \leq \exp(-\Omega_{M,\beta}( \log^2 n))\] for all \(n\) sufficiently large. Combining with 11 completes the proof. ◻

Proof. We handle the bound on \(A^-\) and then indicate how the bound on \(A^+\) follows similarly. We first claim that \[\begin{align} (A^-)^c &\subset \left\{ \begin{array}{c} \exists p,q \in \widehat{G}^- \text{ with } d_{\widehat{G}^-}(p,q) < \infty \text{, } \|p\|,\|q\| \le \frac{\delta}{L}(e^{-\eta}r)^{-1}, \\ \|p - q\| \geq \log^2n, \text{ and } \frac{d_{\widehat{G}^-}(p,q)}{{\mu(\underline{\lambda})}\|p - q\|} \notin [e^{-\eta},e^\eta] \end{array} \right\} \nonumber \\ &\subset \left\{ \begin{array}{c} \exists p,q \in G^{\underline{\lambda}}_{\mathbb{R}^d}(1) \text{ with } d_{G^{\underline{\lambda}}_{\mathbb{R}^d}}(p,q) < \infty \text{, } \|p\|,\|q\| \le \frac{\delta}{L}(e^{-\eta}r)^{-1}, \\ \|p - q\| \geq \log^2n, \text{ and } \frac{d_{G^{\underline{\lambda}}_{\mathbb{R}^d}}(p,q)}{{\mu(\underline{\lambda})}\|p - q\|} \notin [e^{-\eta},e^\eta] \label{eq:Arminus-bound} \end{array} \right\} \end{align}\tag{15}\] where we note that first inclusion follows from \(G^-(r) = (e^{-\eta}r)\widehat{G}^-\) by 6 . To see the second inclusion, suppose that \(p,q \in \widehat{G}^- \cap B(0, (\delta/L)(e^{-\eta}r)^{-1})\) satisfy \(\|p-q\| \ge \log^2 n\), \(d_{\widehat{G}^-}(p,q) < \infty\), and \(d_{\widehat{G}^-}(p,q)/\|p-q\| \notin [e^{-\eta},e^\eta]\). If a \(G^{\underline{\lambda}}_{\mathbb{R}^d}\)-geodesic from \(p\) to \(q\) lies within \({(e^{-\eta} r)^{-1}} \cdot S\), then we have \[d_{G^{\underline{\lambda}}_{\mathbb{R}^d}}(p,q) = d_{\widehat{G}^-}(p,q) \notin [e^{-\eta} \mu(\underline{\lambda})\|p-q\|,e^\eta \mu(\underline{\lambda})\|p-q\|].\] On the other hand, if a \(G^{\underline{\lambda}}_{\mathbb{R}^d}\)-geodesic leaves \({(e^{-\eta} r)^{-1}} \cdot S\), it contains at least two disjoint subpaths connecting \(B(0, (\delta/L)(e^{-\eta}r)^{-1})\) to \(((e^{-\eta} r)^{-1} \cdot S)^c \subset ((e^{-\eta} r)^{-1} \cdot B(0, e^{-\eta} \delta ))^c\), and so we have \[\label{eq:if-geodesic-wanders} d_{G^{\underline{\lambda}}_{\mathbb{R}^d}}(p,q) \ge 2\left(e^{-\eta}\delta - \frac{\delta}{L}\right) (e^{-\eta} r)^{-1} \ge e^{\eta} \mu(\underline{\lambda}) \frac{2\delta}{L} (e^{-\eta} r)^{-1} \ge e^\eta \mu(\underline{\lambda})\|p-q\|\tag{16}\] where the second inequality follows from our choice of \(L\) along with 9. Thus, we have established 15 .

Therefore, by 8 and 7 we may bound \[\begin{align} \mathbb{P}((A^-)^c) &\leq \mathbb{E}\left[ \sum_{\substack{p,q \in G^{\underline{\lambda}}_{\mathbb{R}^d}(1) \cap B(0,r^{-1}): \|p - q\| \geq \log^2 n}} \mathbb{1}\left\{ d_{G^{\underline{\lambda}}_{\mathbb{R}^d}}(p,q)/\|p - q\| \notin [e^{-\eta}\mu(\underline{\lambda}),e^\eta\mu(\underline{\lambda})] \cup \{\infty\} \right\} \right] \\ &\leq C_d \underline{\lambda}^2 r^{-d} \exp(-c_{\underline{\lambda},\eta,d} \log^2n)\,. \end{align}\] Recalling that for fixed \(\varepsilon> 0,\lambda_0 > \lambda_c\) there are only finitely many choices for \(\underline{\lambda}\) and \(r \geq \Omega_d(n^{-1/d})\), we may bound \[C_d \underline{\lambda}^2 r^{-d} \exp(-c_{\underline{\lambda},\eta,d} \log^2n) \leq \exp(-c_{\lambda_0,\varepsilon,d,\beta}' \log^2n )\] for \(n \geq n_0(\lambda_0,\varepsilon,d,\beta)\). This completes the bound on \(A^-\). The proof for \(A^+\) is exactly analogous. ◻

Proof of 23. For \(x \in M, \lambda_0 > \lambda_c\) and \(\varepsilon> 0\), we have chosen parameters \(\delta > 0\) and \(\eta > 0\) in 3; further, we have also chosen \(\underline{\lambda}\) and \(\overline{\lambda}\) for all \(\lambda \geq \lambda_0\) in addition to the map \(u\) from 6 with small distortion. With these choices, we proceed by showing \(A^+ \cap A^- \cap \mathcal{C} \subset \mathcal{G}_{\delta/L',\varepsilon}(x)\) and then our desired result will follow from 24 and 17. So assume \(A^+, A^-,\) and \(\mathcal{C}\) all hold. Let \(p, q \in \mathring{G}^{n}_M(r) \cap B_M(x,\delta/L')\) with \(d_M(p,q) \ge r \log^3 n\). We want to show that \[\label{eq:M-local-need} e^{-\varepsilon} \leq \frac{r d^\lambda_r(p,q)}{\mu(\lambda)d_M(p,q)} \leq e^\varepsilon\tag{17}\] We first show the lower bound. Note that by the distortion bound on \(u\) from 6 we have \(\|u(p) - u(q)\| \ge e^{-\eta}r \log^3 n\). First consider the case where \(d^\lambda_r(p,q) < d_{G_S}(u(p),u(q))\); in this case, we have that each geodesic from \(p\) to \(q\) must wander far enough to contain a vertex outside of \(B_M(x,\delta)\). We must have \(rd^\lambda_r(p,q) \geq 2\delta(1 - 1/L')\). Since \(d_{M}(p,q) \leq 2\delta/L'\), by the choice of \(L'\) we have \(r d_r^\lambda(p,q) \geq e^{-\varepsilon} \mu(\lambda) d_M(p,q).\) Thus we may assume \(d_r^\lambda(p,q) = d_{G_S}(u(p),u(q))\). Now, since \(u(G^n_M(r) \cap B_M(x,\delta)) = G_S \subset G^+\), we have \(u(p), u(q) \in G^+\) and \[d^\lambda_r(p,q) = d_{G_S}(u(p),u(q)) \ge d^+_r(u(p),u(q)) \,.\] Recall that we have defined \(A^+\) separately in the case of \(\lambda \geq \lambda_+e^{(d+1)\eta}\), in which case we note that the lower bound in 17 follows immediately from 4 and 14 . In the case of \(\lambda \leq \lambda_+e^{(d+1)\eta}\) we may use \(A^+\), the distortion bound on \(u\) and 4 to see \[\begin{align} rd^{\lambda}_r(p,q) &\ge rd^+_r(u(p),u(q)) \ge e^{-2\eta} \mu(\overline{\lambda})\|u(p) - u(q)\| \ge e^{-3\eta - (\varepsilon/2)} \mu(\lambda) d_M(p,q) \ge e^{-\varepsilon} {\mu(\lambda)}d_M(p,q) \end{align}\] as desired.

For the upper bound in 17 , use \(\mathcal{C}\) to find \(p',q'\) in the same component of \(G^-\) satisfying \[\label{eq:B-application} d^\lambda_r(p, u^{-1}(p')) \leq \log^2n \quad \text{ and } \quad d^\lambda_r(q, u^{-1}(q')) \le \log^2n\,.\tag{18}\]

Since \(G^- \subset G_S\), we have \(p',q' \in G_S\) and \[\label{eq:d-lam-UB-dr-} d^{\lambda}_r(u^{-1}(p'),u^{-1}(q')) \leq d_{G_S}(p',q') \le d_r^-(p',q').\tag{19}\] By the triangle inequality we have \[\label{eq:p39-q39-LB} \|p' - q'\| \ge \|u(p) - u(q)\| - 2r \log^2 n \ge e^{-\eta}d_M(p,q) - 2r \log^2n \ge e^{-2\eta} r \log^3 n\tag{20}\] where the last bound is for \(n\) sufficiently large since we assumed \(d_M(p,q) \geq r \log^3 n\). Equation 20 ensures we may apply \(A^-\), and so by \(A^-\) along with 18 and 19 to see \[\begin{align} rd^\lambda_r(p,q) &\le rd^\lambda_r(u^{-1}(p'),u^{-1}(q')) + 4r \log^2 n \le rd^-_r(p',q') + 4r \log^2n \le e^\eta \mu(\underline{\lambda})\|p' - q'\| + 4r \log^2 n\,. \label{eq:dlamr-UB} \end{align}\tag{21}\] By the distortion bounds on \(u\) along with 4 we have \[\begin{align} e^\eta \mu(\underline{\lambda})\|p' - q'\| \leq e^{2\eta + (\varepsilon/2)} \mu(\lambda) d_M(u^{-1}(p'),u^{-1}(q')) \leq e^{2\eta + \varepsilon/2} \mu(\lambda) (d_M(p,q) + 2r \log^2 n) \label{eq:patches-UB-time-constant-eq} \end{align}\tag{22}\] where in the last line we used 18 . Recalling that \(d_M(p,q) \geq r \log^3 n\), combining 21 and 22 for \(n\) large enough shows 17 completing the proof. ◻

Proof. Consider a geodesic in \(M\) from \(p\) to \(q\) and let \(p=y_0, y_1,...,y_\ell =q\) be a sequence of (distinct) points along the geodesic such that each consecutive pair of points lies in a common element of \(\mathcal{U}\) and we have \[\label{eq:UB-geodesic} d_M(p,q) = \sum_{i=1}^\ell d_M(y_{i-1},y_i).\tag{23}\] We claim that for sufficiently large \(n\) we have \[\label{eq:UB-containment} \bigcap_{j=1}^N \mathcal{G}_{x_j} \cap \mathcal{B} \subset \{ r d_r^\lambda(\mathring{p}, \mathring{q}) \le e^{\varepsilon} \mu(\lambda) d_M(p,q) \}.\tag{24}\] To begin with, the triangle inequality shows \[\label{eq:2pt-UB-1} d_r^\lambda(\mathring{p}, \mathring{q}) \le \sum_{i=1}^\ell d_r^\lambda(\mathring{y}_{i-1}, \mathring{y}_i)\,.\tag{25}\] On the event \(\mathcal{B}\) the triangle inequality gives the lower bound \[d_M(\mathring{y}_{i-1}, \mathring{y}_i) \ge d_M(y_{i-1}, y_i) - 2r \log^2 n \geq r \log^3 n ,\] for all \(i=1,...,\ell\) when \(n\) is sufficiently large. Therefore the event \(\bigcap_{j=1}^N \mathcal{G}_{x_j}\) gives us \[\label{eq:2pt-UB-2} r d_r^\lambda(\mathring{y}_{i-1}, \mathring{y}_i) \le e^{\varepsilon/2} \mu(\lambda)d_M(\mathring{y}_{i-1}, \mathring{y}_i).\tag{26}\] On the event \(\mathcal{B}\) we have \[\label{eq:2pt-UB-3} d_M(\mathring{y}_{i-1}, \mathring{y}_i) \leq d_M(y_{i-1},y_i) + 2 r \log^2 n\leq e^{\varepsilon/2} d_M(y_{i-1},y_i)\tag{27}\] where the last inequality holds for \(n\) large enough as a function of \(\varepsilon, \beta\) and \(d_M(y_{i-1},y_i)\). Combining 25 , 26 and 27 with 23 shows \[\begin{align} r d_r^\lambda(\mathring{p}, \mathring{q}) \leq e^{\varepsilon} \mu(\lambda) d_M(p,q)\,. \end{align}\] This shows 24 . Combining with 23 and 16 completes the proof. ◻

Proof. We will show that for \(n\) sufficiently large we have \[\label{eq:LB-containment} \bigcap_{j=1}^N \mathcal{G}_{x_j} \cap \mathcal{B} \subset \{r d_r^\lambda(\mathring{p}, \mathring{q}) \ge e^{-\varepsilon} \mu(\lambda) d_M(p,q)\}.\tag{28}\]

To begin with, we first claim that we may find well-separated points along a \(d_r^\lambda\) geodesic from \(\mathring{p}\) to \(\mathring{q}\).

Letting \(v_0,\ldots,v_K\) as in 28, on the event \(\bigcap_{j=1}^N \mathcal{G}_{x_j} \cap \mathcal{B}\) we may bound

\[r d_r^\lambda(v_{k-1},v_k) \geq e^{-\varepsilon/2} \mu(\lambda) d_M(v_{k-1}, v_k)\] and so \[\label{eq:LB-dr-geodesic} r d_r^\lambda(\mathring{p}, \mathring{q}) \geq \sum_{k = 1}^K e^{-\varepsilon/2} \mu(\lambda) d_M(v_{k-1},v_k) \geq e^{-\varepsilon/2} \mu(\lambda) d_M(\mathring{p},\mathring{q})\tag{29}\] where the last inequality is the triangle inequality. On the event \(\mathcal{B}\) and \(n\) sufficiently large we have \[\label{eq:LB-apply-B} d_M(\mathring{p},\mathring{q}) \geq d_M(p,q) - 2 r \log^2 n \geq e^{-\varepsilon/2} d_M(p,q)\,.\tag{30}\] Combining 29 and 30 shows that \[rd_r^\lambda(\mathring{p}, \mathring{q}) \geq e^{-\varepsilon} \mu(\lambda) d_M(p,q)\] thus establishing 28 . Applying 23 and 16 completes the proof. ◻

Proof of 25. Combining 26 and 27 completes the proof. ◻

Proof. Choose \(\gamma > 0\) sufficiently small so that \(\max(1 - e^{-\gamma}, e^\gamma - 1) \mu(\lambda_0) \mathrm{diam}(M) \le \varepsilon/2\). We then see that, for each \(x,z \in X\) we have \[\begin{align} \left\{ \frac{r d^\lambda_r(\mathring{x},\mathring{z})}{\mu(\lambda) d_M(x,z)} \in [e^{-\gamma},e^\gamma] \right\} \subset \left\{ |\mu(\lambda) d_M(x,z) - r d_r^\lambda(f_r(x), f_r(z))| \le \varepsilon/2 \right\}. \end{align}\] Therefore we have that \[\begin{align} \mathbb{P}\left(\sup_{x, x' \in X} |\mu(\lambda)d_M(x,x') - r d^\lambda_r(f_r(x),f_r(x'))| > \varepsilon/2\right) &\le \sum_{x, x' \in X} \mathbb{P}\left( |\mu(\lambda)d_M(x,x') - r d^\lambda_r(f_r(x),f_r(x'))| > \varepsilon/2\right) \\ &\le \sum_{x,x' \in X} \mathbb{P}\left( \frac{r d^\lambda_r(\mathring{x},\mathring{x}')}{\mu(\lambda) d_M(x,x')} \notin [e^{-\gamma},e^\gamma] \right)\,. \end{align}\] Applying 25 completes the proof. ◻

Proof. Let \(\eta > 0\) be chosen as in 3 and note we have \(2 e^\eta (\varepsilon/5) \leq \varepsilon/2\). We may then use 23 along with compactness of \(M\) to find a refinement \(X' \supset X\) so that for each \(x \in X'\) we have \(\delta_x > 0\) so that \(\{B_M(x,\delta_x)\}_{x \in X'}\) covers \(M\) and so that if we define the event \[\mathcal{G}'_{x} := \left\{ \begin{array}{c} \forall p, q \in \mathring{G}^n_M(r) \cap B_M(x,\delta_x)such thatd_M(p,q) \ge r\log^3 n, \\ r d^\lambda_r(p,q)/[\mu(\lambda) d_M(p,q)] \in [e^{-\eta},e^{\eta}] \end{array} \right\}\] then \(\mathbb{P}(\mathcal{G}'_{x}) \geq 1 - \exp(-c \log^2 n)\,.\) For a pair \(x,y \in X'\) we also define \[T_{x,y} = \left\{ \frac{r d_r^\lambda(\mathring{x},\mathring{y})}{\mu(\lambda) d_M(x,y)} \in [e^{-\eta}, e^\eta] \right\}\,.\] By 25, we have that \(\mathbb{P}(T_{x,y}) \geq 1 - \exp(-c \log^2 n)\,.\) Thus, using 16, it is sufficient to show the inclusion \[\bigcap_{x \in X'}\mathcal{G}'_{x}\cap \mathcal{B} \cap \bigcap_{x,y \in X'} T_{x,y} \subset \{f_r(X) \text{ is a }(\varepsilon/2)\text{-net in }(\mathring{G}_M^n(r), r d_r^\lambda)\}\,.\] To see this, let \(y \in \mathring{G}_M^n(r)\) be arbitrary. By requiring all \(\delta_x\) satisfy \(\delta_x \leq \varepsilon/ (5 \mu(\lambda_0))\), we see that there is some \(z \in X'\) so that \(y \in B_M(z,\delta_z)\) and \(\mu(\lambda) d_M(z,y) \leq \varepsilon/5\).

To complete the proof of the lemma, note that there exists \(x \in X\) so that \(\mu(\lambda) d_M(x,z) \leq \varepsilon/5\) and that \(rd_r^\lambda(f_r(x),\mathring{z}) \leq e^\eta \mu(\lambda) d_M(x,z)\) by the event \(T_{x,z}\). This implies \[\begin{align} rd_r^\lambda(f_r(x),y) \leq rd_r^\lambda(f_r(x),\mathring{z}(r)) + rd_r^\lambda(\mathring{z},y) \leq e^{\eta}\left(\varepsilon/5 + \varepsilon/4 + 9 r\log^3 n \right) \leq \varepsilon/2 \end{align}\] where the second inequality is by 32 along with the event \(\mathcal{B}\) showing \(\mu(\lambda) d_M(\mathring{z},y) \leq \varepsilon/4\); the last inequality follows from taking \(n\) sufficiently large. ◻

Proof of 2. Define \(f_r\) as above and \(X\) to be a finite \(\varepsilon/(5 \mu(\lambda_0))\)-net in \((M,d_M)\) and note that \(\mu(\lambda_0) \geq \mu(\lambda)\) by 9. 30 shows \(f_r\) has distortion at most \(\varepsilon/2\) into \((\mathring{G}_M^n(r),rd_r^\lambda)\) with probability at least \(1 - \exp(-\Omega(\log^2n)).\) Defining \(Y = f_r(X)\) we have that \(Y\) is an \(\varepsilon/2\)-net in \((\mathring{G}_M^n(r),rd_r^\lambda)\) with probability at least \(1 - \exp(-\Omega(\log^2 n))\) by 31. Applying 29 completes the proof. ◻

Proof. We will use 7. Set \(\gamma = 1/10\). For two points \(x,y \in M\), consider a sequence of points \(x = x_0,x_1,\ldots,x_K = y\) along a \(d_M\)-geodesic from \(x\) to \(y\) so that \(d_M(x_{j-1},x_j) \leq (1 - 2\gamma) r\). Further, we may choose this sequence of points so that \(K \leq (1 - 2\gamma)^{-1} r^{-1} \mathrm{diam}(M) + 1 \leq O_M(n^\beta)\). Note that for \(x,y \in G_M^n(r)\) we have \[\begin{align} \{x \xleftrightarrow{G_M^n(r)} y\} \supset \bigcap_{j = 1}^{K-1} \{G_M^n(r) \cap B_M(x_j, \gamma r) \neq \emptyset \}\,. \end{align}\] Note that for each \(z \in M\) we have \[\mathbb{P}(G_M^n(r) \cap B_M(x_j, \gamma r) = \emptyset) = \exp(- n \mathrm{Vol}_M(B_M(x_j, \gamma r))) \leq \exp( - \Omega_M( n \gamma^d r^d)) = \exp(-\Omega_M(n^{1 - d\beta}))\,.\] 7 then shows \[\mathbb{P}(G_M^n(r) \text{ is not connected}) \leq O_M( n^\beta \exp(- \Omega(n^{1 - d\beta}))) \leq \exp(- \Omega_M(n^{1 - d\beta}))\,. \qedhere\] ◻

Proof. For the lower bound, first note that \(G = G_M^n(r)\) is connected with probability \(1 - \exp(-cn^{1-d\beta})\) by 33. For \(\gamma > 0\) to be chosen later note that \[\begin{align} \{G \text{ is connected}\} &\cap \{B_M(p, \gamma\varepsilon) \cap G \neq \emptyset\} \cap \{B_M(q, \gamma\varepsilon) \cap G \neq \emptyset\} \\ &\subset \{d_r^\lambda(\mathring{p},\mathring{q}) \geq (d_M(p,q) - 2\gamma \varepsilon)/r + 1\} \end{align}\] For \(\gamma\) small enough as a function of \(\varepsilon\) and taking \(r \leq \alpha\) for \(\alpha\) small as a function of \(\varepsilon> 0\) we see \[\{\infty > d_r^\lambda(\mathring{p},\mathring{q}) \geq (d_M(p,q) - 2\gamma \varepsilon)/r + 1\} \subset \{rd_r^\lambda(\mathring{p},\mathring{q}) \geq e^{-\varepsilon} d_M(p,q)\}\,.\] Noting that \(\mathbb{P}(B_M(z, \gamma\varepsilon) \cap G \neq \emptyset) \geq 1- \exp(-\Omega_{M,\varepsilon}(n))\) uniformly for \(z \in M\) shows \[\mathbb{P}(rd_r^\lambda(\mathring{p},\mathring{q}) \geq e^{-\varepsilon} d_M(p,q)) \geq 1 - \exp(-\Omega_{M,\varepsilon}(n^{1- d\beta}))\,.\]

For the upper bound, fix \(\varepsilon> 0\) and let \(\gamma > 0\) to be chosen later as a function of \(\varepsilon> 0\). For points \(p,q \in G\) with \(d_M(p,q) \geq \varepsilon/100\), choose points \(p = x_0,x_1,\ldots,x_K = q\) along a \(d_M\)-geodesic so that \[\label{eq:K-def} d_M(x_{j-1},x_j) \leq (1 - 4\gamma)r,\quad \left|K - \left((1 - 4\gamma) r\right)^{-1} d_M(p,q) \right| \leq 1\,.\tag{31}\] We now note that \[\begin{align} \label{eq:d-LB-sparse} \mathbb{P}( d_r^\lambda(p,q) \leq K ) \geq \mathbb{P}\left(\bigcap_{j=0}^K \{G_M^n(r) \cap B_M(x_j,\gamma r) \neq \emptyset \}\right)\geq 1- \exp(-\Omega_M(n^{1-d\beta}))\,. \end{align}\tag{32}\] For \(r,\gamma\) small enough as a function of \(\varepsilon\) and \(d_M(p,q)\) we have that \(K \leq r^{-1} e^\varepsilon d_M(p,q)\), completing the proof. ◻

Proof of 3. For fixed \(\varepsilon> 0\), let \(X = X_\varepsilon\subset M\) be a finite \(\varepsilon\)-net in the metric \(d_M\). Note that we may assume that for all \(x,x' \in X\) with \(x \neq x'\) we have \(d_M(x,x') \geq \varepsilon/2\). Define \(f_r(x) = \mathring{x}\). By 34 we have \[\begin{align} \mathbb{P}\left(\sup_{x,x' \in X} |d_M(x,x') - rd_r^\lambda(f_r(x),f_r(x')) | \geq \varepsilon\right)\leq C_{M,\varepsilon} \exp\left( - c_{M,\varepsilon} n^{1 - d\beta} \right) \end{align}\] for \(r \leq \alpha = \alpha(M,\varepsilon,\beta)\) and \(n \geq n_0 = n_0(M,\varepsilon,\beta)\). For any \(x \in X\) and \(z \in B_M(x,\varepsilon) \cap G_M^n(r)\), the proof of 34 (in particular equations 31 and 32 ) shows that \[\mathbb{P}(rd_r^\lambda(\mathring{x},z) \geq 2\varepsilon) \leq C_{M,\varepsilon} \exp\left( - c_{M,\varepsilon} n^{1 - d\beta} \right)\,.\] By 7, this implies that \[\mathbb{P}(rd_r^\lambda(\mathring{x},z) \leq 2\varepsilon\text{ for all }z \in B_M(x,\varepsilon)) \geq 1 - \exp\left( - c_{M,\varepsilon}' n^{1 - d\beta} \right)\] thus showing that \(f_r(X)\) is a \(2\varepsilon\) net with probability \(1 - \exp(-\Omega(n^{1-d\beta}))\). 29 completes the proof. ◻

Proof. We prove the contrapositive. Since \(M_1\) is compact, we may find a countable dense set \(\{x_j\}_{j \geq 1} \subset M_1\). For each \(n\), we may find a sequence \(\{y_j^{(n)}\}_{j = 1}^n\) so that \[d_2(y_i^{(n)},y_j^{(n)}) = d_1(x_i,x_j) \quad \text{ for all }i < j \leq n\,.\] By compactness of \(M_2\), we may find a subsequence of \(\{n_a\}\) so that for each fixed \(i\) we have that \(y_i^{(n_a)} \to y_i\) for some \(y_i \in M_2\). By continuity of \(d_2\) we have that \[\label{eq:embedding} d_2(y_i,y_j) = d_1(x_i,x_j) \qquad \text{ for all } i < j < \infty\tag{33}\] We define an embedding \(f:M_1 \to M_2\) by first defining \(f(x_i) = y_i\). For an arbitrary point \(x \in M_1\), we may find a subsequence \(n_j\) so that \(x_{n_j} \xrightarrow{j \to \infty} x\), and in particular \(\{x_{n_j}\}_j\) is a Cauchy sequence. By 33 this implies \(\{y_{n_j}\}_j\) is a Cauchy sequence; since \(M_2\) is a compact metric space, this implies that \(y_{n_j} \xrightarrow{j \to \infty} y \in M_2\). We define⁵ \(f(x) = y\). For all \(x,z \in M_1\), we have that there are sequences \(x_{n_i} \to x\) and \(x_{m_i} \to z\) and so \[d_2(f(x),f(z)) = \lim_i d_2( f(x_{n_i}), f(x_{m_i})) = \lim_i d_1(x_{n_i}, x_{m_i}) = d_1(x,z)\] implying that \(f:M_1 \to M_2\) is an isometric embedding. Repeating the argument with the roles reversed gives us an isometric embedding \(g:M_2 \to M_1.\) This implies that \(g \circ f:M_1 \to M_1\) is an isometry. Since \(M_1\) is a compact metric space, this implies that \(g \circ f\) is surjective (see e.g.[23]). We claim that \(f\) is also surjective, so take \(y \in M_2\). Set \(x = g(y) \in M_1\), and by surjectivity of \(g \circ f\) there is some \(z \in M_1\) so that \(g(f(z)) = x\). But since \(g\) is an isometry, we have that \(g\) is injective implying \(y = f(z)\). This shows that \(f:M_1 \to M_2\) is a bijective isometry, completing the proof. ◻

Proof. Apply 35 to obtain points \(x_1,\ldots,x_K \in M_1\). Consider the function \(F:M_2^K \to \mathbb{R}_{\geq 0}\) defined by \[F(y_1,\ldots,y_K) = \sum_{i,j} \left|d_1(x_i,x_j) - d_2(y_i,y_j)\right|\,.\] Note that \(F\) is continuous on the compact set \(M_2^K\) and never equal to \(0\), implying it achieves some minimum \(\varepsilon> 0\). ◻

Proof. By the definition of \(d_{{\mathrm{GH}}}\) there is some metric space \((N,d_N)\) along with isometric embeddings \(f:M_1 \to N\) and \(g:M_2 \to N\) so that \(d_N(f(M_1),g(M_2)) \leq 2\varepsilon\,.\) This implies that for each \(x_i\) pick some \(y_i\) so that \(d_N(f(x_i),g(y_i)) \leq 2\varepsilon\). By the triangle inequality we have \[\begin{align} \left|d_1(x_i,x_j) - d_2(y_i,y_j) \right| &= |d_N(f(x_i),f(x_j)) - d_N(g(y_i),g(y_j)) | \\ &\leq d_N(f(x_i),g(y_i)) + d_N(f(x_j),g(y_j)) \\ &\leq 4\varepsilon\,. \qedhere \end{align}\] ◻

Proof. For \(\alpha\) small enough, we have that \(r_j = (\frac{\Delta}{n \alpha_{d_j}})^{1/d_j} (1 + o_{\alpha \to 0}(1))\) for \(j \in \{1,2\}\) where \(\alpha_d\) is the volume of the unit ball in \(\mathbb{R}^d\). In particular, for each \(L > 0\) we may take \(\alpha\) sufficiently small so that \(r_1 / r_2 \geq L\). For each fixed \(\varepsilon> 0\), we may apply 1 to see that with probability at least \(1 - \exp(-\Omega(\log^2n))\) we have \[\label{eq:diameters-bounds} \mathrm{diam}(\mathring{G}_{M_1}(n;r_1)) \leq (1 + \varepsilon)\overline{\mu}_{d_1}(\Delta) \mathrm{diam}(M_1) r_1^{-1} \; \text{ and } \; \mathrm{diam}(\mathring{G}_{M_2}(n;r_2)) \geq (1 - \varepsilon)\overline{\mu}_{d_2}(\Delta) \mathrm{diam}(M_2) r_2^{-1}\tag{34}\] where we write \(\mathrm{diam}(\mathring{G}_{M_1}(n;r_1))\) for the graph diameter and \(\mathrm{diam}(M_1)\) for the metric diameter. In particular, for \(\alpha\) sufficiently small we have \[\frac{\mathrm{diam}(\mathring{G}_{M_1}(n;r_1))}{\mathrm{diam}(\mathring{G}_{M_2}(n;r_2))} \leq \frac{1}{2}\] provided we have 34 . We can find the graph diameter of each graph by running a breadth first search starting from each vertex; this identifies the giant component by 13. Since a breadth first search has run-time \(O(n\Delta)\), the algorithm runs in time \(O(n^2 \Delta)\). Choosing the graph of larger graph diameter provides the algorithm which succeeds with probability at least \(1 - \exp(-c \log^2 n).\) ◻

Proof of 4. First note that if \(d_1 \neq d_2\) then 38 applies and so we may assume \(d_1 = d_2 = d\).

Apply 36 to find \(\varepsilon_1 = \varepsilon_1(M_1,M_2) \in (0,1/2)\) and \(K = K(M_1,M_2)< \infty\) so that (up to possibly swapping \(M_1\) and \(M_2\)) there is \(x_1,\ldots,x_K \in M_1\) so that for all \(y_1,\ldots,y_K \in M_2\) we have \[\label{eq:separation32criterion} \sum_{i,j} \left|d_{M_1}(x_i,x_j) - d_{M_2}(y_i,y_j) \right| \geq \varepsilon_1\,.\tag{35}\] We will apply 1 for \(\varepsilon= \varepsilon_2 := \varepsilon_1 / (16 K^2)\). For \(i \in \{1,2\}\) define the event \(\mathcal{G}_i\) via \[\begin{align} \mathcal{G}_i = \left\{d_{{\mathrm{GH}}}\left((\mathring{G}_{M_i}(n;r_i), \frac{r_i}{\overline{\mu}(\Delta)} d_{G_i}),(M_i, d_{M_i}) \right) \leq \varepsilon_2\right\}\,. \end{align}\] We then note that by 37, this implies that on event \(\mathcal{G}_1\), we may find points \(z_1,\ldots,z_K \in \mathring{G}_1\) so that \[\label{eq:M-1-zs} \sum_{i,j} |d_{M_1}(x_i,x_j) - \frac{r_1}{\overline{\mu}(\Delta)}d_{G_1}(z_i,z_j)| \leq K^2 4 \varepsilon_2 \leq \frac{\varepsilon_1}{4}\,.\tag{36}\] Conversely, on event \(\mathcal{G}_2\), for all \(w_1,\ldots, w_K \in \mathring{G}_2\), there are points \(y_1,\ldots,y_K\) so that \[\sum_{i,j} |d_{M_2}(y_i,y_j) - \frac{r_2}{\overline{\mu}(\Delta)}d_{G_2}(w_i,w_j)| \leq \frac{\varepsilon_1}{4}\,.\] Letting \(\alpha_d\) denote the volume of the unit ball in \(\mathbb{R}^d\), we note that for \(\alpha\) sufficiently small we have \[r_k = (1 + o_{\alpha \to 0}(1))\left(\frac{\Delta}{n \alpha_d} \right)^{1/d}\] for each \(k \in \{1,2\}\). Further, if we apply 39 and define \(r = \left(\frac{2e(G_{M_1}(n;r_1))}{n^2 \alpha_d}\right)^{1/d}\) then note that with probability at least \(1 - \exp(-\Omega(\log^2 n))\) we have \[e^{-\varepsilon_1/100} \leq \frac{r_k}{r} \leq e^{\varepsilon_1/100}\] for \(k \in \{1,2\}\) and \(\alpha\) sufficiently small. We may then use 35 to see that for all \(w_1,\ldots,w_K \in \mathring{G}_2\) we have \[\sum_{i,j} \left|d_{M_1}(x_i,x_j) - \frac{r}{\overline{\mu}(\Delta)}d_{G_2}(w_i,w_j) \right| \geq \frac{3\varepsilon_1}{4}\] and for \(z_1,\ldots,z_K \in G_1\) satisfying 36 we have \[\sum_{i,j} \left|d_{M_1}(x_i,x_j) - \frac{r}{\overline{\mu}(\Delta)}d_{G_1}(z_i,z_j) \right| \leq \frac{\varepsilon_1}{2}\,.\] Our algorithm is defined as follows. First use a breadth-first search started at each vertex to find all pairwise distances in the metrics \(d_{G_i}\) in run-time \(O(n^3)\); this also allows us to find the largest component by 13 simultaneously. We may also compute \(r = \left(\frac{2e(G_{M_1}(n;r_1))}{n^2 \alpha_d}\right)^{1/d}\) and \(\Delta' = 2e(G_{M_1}(n;r_1))/n\) in this time as well. For \(k \in \{1,2\}\) compute \[a_k =\min_{w_1,\dots,w_K \in \mathring{G}_k} \sum_{i,j} \left|d_{M_1}(x_i,x_j) - \frac{r}{\overline{\mu}(\Delta')}d_{G_k}(w_i,w_j) \right|\] in time \(O(n^K)\) by checking all \(K\)-tuples. If \(a_1 \leq a_2\) output that \(G_1\) came from \(M_1\), otherwise output that \(G_2\) came from \(M_1\).

Since \(\Delta' = (1 + o_{\alpha \to 0}(1))\Delta\) and \(\overline{\mu}\) is continuous by 10, we see that for \(\alpha\) small enough we have that \(a_1 \leq 9\varepsilon_1/16\) and \(a_2 \geq 11\varepsilon_1/16\) and so this algorithm outputs the correct outcome with probability at least \(1 - \exp(-c \log^2 n)\,.\) ◻

Proof of 11. We will adapt the proof of its homogeneous analogue, [1]. The key observation is that, since \(\sigma(\cdot,\cdot) \le \|\cdot-\cdot\|\) and \(\frac{d\nu}{d\mathcal{L}} \ge \lambda_0\), the graph \(G_s\) is contains its homogeneous counterpart as a subgraph, allowing us to use monotonicity of certain events. The metric \(\sigma\) is used to determine the edges of \(G_s\), and should be used to define balls in the “crossing events” in [1]. The fact that \(\sigma\) and \(\nu\) are inhomogeneous means that technically all the lemmas have to be stated and proven for \(x + B(s)\) rather than \(B(s)\), with all bounds uniform over \(x\), but this does not change the proofs in an essential way.

Note first that the existence of a component of diameter at least \(\phi_s\) follows from applying [1] at \(\lambda_0\), and so we will focus on the non-existence of other components. We now show how to adapt [1]. The proof of [1] is broken into two cases, of \(d \geq 3\) and \(d = 2\). We describe these separately.

For \(d \geq 3\), we first give a quick overview of the logical chain of implications starting from [1] and working backwards, and then describe the bounds attained. Throughout, we will adhere as closely as possible to the notation in [1] so one may directly translate. The claim [1] follows from [1], which shows that it is rare to have two components \(\kappa\) and \(\kappa'\) so that \(\kappa\) crosses in the \(k\) coordinate and that the (Euclidean) diameter of the projection of \(\kappa'\) to the \(k\) coordinate is at least \(\phi_s\). This is performed by considering a slab decomposition and using [1] to bound the probability of a crossing event on each slab. This is where the lower bound on \(\sigma\) is used: it guarantees that (for a sufficiently large choice of slab width \(K'\)) any component which has vertices in two slabs must have vertices in all the intermediate slabs; this property is necessary to establish the inclusion \[G'_{x,y,s} \subset \bigcap_{j-1}^{[(\phi_s - 1)/K']} A'_j\] where the above events are defined as in [1].

Here, in the statement of [1], in order to account for the inhomogeneity of the metric, the lower bound we want is \[\liminf_{s \to \infty} \inf_{x \in \mathbb{R}^d} \inf_{A, B \subset N_x} \frac{\mathbb{P}\left[C(A; \mathcal{H}_\nu \cap x + S(K',s)) \cap C(B; \mathcal{H}_\nu \cap x + S(K',s)) \ne \emptyset \right] }{\mathbb{P}\left[ C(A; \mathcal{H}_\nu \cap x + S(K',s)) \ne \emptyset; C(B; \mathcal{H}_\nu \cap x + S(K',s) \ne \emptyset \right]} > 0\] where \(\mathcal{H}_\nu\) is the point configuration of the Poisson process with intensity \(\nu\), which we elsewhere refer to as \(X_\nu\); we take \[N_x := \{ y \in x +(-2,0)\times[0,s]^{d-1} : \sigma(y, x + S(K',s)) < 1\};\] and \(S(K',s)\) and \(C(\cdot ; \cdot)\) are defined as in [1].

The only percolation input into [1] is [1] which is in fact a monotone event, and so it directly applies to our inhomogeneous setting. Note also that in the case \(\lambda= \mu\) (borrowing the notation from [1]), the lower bound obtained improves as \(\lambda\to \infty\), and so we get a constant depending only on \(\lambda_0 > \lambda_c\) which holds for all \(\frac{d\nu}{d\mathcal{L}} \ge \lambda_0\).

Putting the pieces together, we note that the proof of [1] yields an upper bound of \[\mathbb{P}\left( \begin{array}{c} the second largest component ofG_s \\has Euclidean diameter at least\phi_s \end{array} \right) \leq C_{d} s^d \exp(-c \phi_s)\] for \(c = c(d,\lambda_0) > 0\).

For the case of \(d = 2\), the proof of [1] is more explicitly monotone: one covers the square with \(O_d(s^2)\) many vertical and horizontal dominoes of aspect ratio \(2\) and side-length \(c_{d} \phi_s\), applies [1] to assert that each horizontal domino has a horizontal crossing and each vertical domino has a vertical crossing with probability at least \(1 - \exp(-c \phi_s)\), and then notes that any component of large metric diameter must intersect the component constructed in this manner. Since the only percolation input to this argument is the monotone event guaranteeing a crossing for each domino, it directly implies the \(d=2\) case of 11. ◻

Proof of 22. We indicate how to extract this statement from the proof of its homogeneous analogue [5]. The proof of [5] is a renormalization technique; we introduce some of their notation here. For a parameter \(M\) which will be fixed but large they define \(B(M) = [-M/2,M/2]^d\) and \(B(5M/4)\) analogously. They then define their boxes \(B_z = B(M) + \{Mz\}\) and \(B_z^+ = B(5M/4) + \{Mz\}\). They define events \(A_z\) depending only on the boxes \(B_z\) and \(B_z^+\). The only properties we need about these events are that: (1) \(A_z\) and \(A_w\) are independent if \(\|z - w\|_\infty \geq 2\); (2) for each fixed \(\delta > 0\) one may make \(M\) large enough so that \(\mathbb{P}(A_z) \geq 1 - \delta\) for each \(z\), uniformly in \(z\). Property (1) holds for us as well (provided \(M\) is large enough). Property (2) is proven in [5] by the homogeneous analogue of Lemma 11 and so Lemma 11 proves property (2) for us as well.

As in [5], by \(O(1)\)-dependence, for any \(p_1\), one may find \(M_0\) so that for all \(M \geq M_0\) the Bernoulli field \(\{\mathbb{1}\{A_z\} \}_{z \in \mathbb{Z}^d}\) stochastically dominates an i.i.d.Bernoulli-\(p_1\) random field.

Following [20], they will alter a path witnessing \(x \stackrel{G}{\longleftrightarrow} y\) in order to upper bound it in the macroscopic scale. To this end, in the macroscopic scale \(z \in \mathbb{Z}^d\) they call a box white if \(A_z\) holds and black otherwise. If \(x \stackrel{G}{\longleftrightarrow}y\) then they let \(a,b \in \mathbb{Z}^d\) be so that \(x \in B_a\) and \(y \in B_b\) and choose a path \(a_0,a_1,\ldots,a_n \in \mathbb{Z}^d\) so that \(a = a_0, a_n = b\) and \(\|a_i - a_{i+1}\|_1 = 1\). For a point \(z \in \mathbb{Z}^d\) they define the cluster \(C(z)\) to consist of \(\{z\}\) if \(z\) is white and the black connected component of \(z\) together with its boundary if it is black. Recall that the black vertices are stochastically dominated by i.i.d.\(1 - p_1\) percolation. They now define \[W = \bigcup_{j = 0}^n \bigcup_{z \in C(a_j)} B_z^+\,.\]

They follow [20] to alter the path witnessing \(x \stackrel{G}{\longleftrightarrow} y\) to lie within \(W\), which in our setting follows from translating [20] verbatim (as [5] does). The next step of [5] shows that if one has a path \(x_1,\ldots,x_t\) of connected points in \(G\) that is minimal that lies in \(B(M)\) then one can upper bound \(t\) in terms of \(\mathcal{L}(B(M+1))\); this follows from noting—as in our case—that by minimality of the path, the balls of radius \(1/2\) centered at \(x_j\) are disjoint and lie in \(B(M+1)\). This guarantees that \(d_G(x,y) \leq C' |W|\) for some \(C'\) depending on \(M\) and the dimension \(d\). They complete the proof by noting that if one takes \(p_1\) large enough, one may bound \(|W|\) by \(O_M(\|x - y\|_2)\) as in [20]; this only depends on having \(1 - p_1\) sufficiently small as a function of \(d\) and so the proof is complete. ◻