Proof. Good Center.  Set \(m:=|U|\). Since \(\overline{\mathrm{p}}\!\left(U\right)\) is the ordered off-diagonal average, \[\mathrm{p}(0)-\overline{\mathrm{p}}\!\left(U\right) = \frac{1}{m(m-1)} \sum_{\substack{u,v\in U\\u\neq v}} \left[ \mathrm{p}(0)-\mathrm{p}\!\bigl({\rm d}({X_u},{X_v})\bigr) \right].\] Averaging over the first coordinate, there exists \(u_U\in U\) such that \[\begin{align} \frac{1}{m-1}\sum_{\substack{v\in U\\v\neq u_U}} \left[\mathrm{p}(0)-\mathrm{p}\!\bigl({\rm d}({X_{u_U}},{X_v})\bigr)\right] \le \mathrm{p}(0)-\overline{\mathrm{p}}\!\left(U\right) \le \Delta. \end{align}\] Let us simply set \(\theta_U:=X_{u_U}\), so that the above average is taken over the distances from \(\theta_U\) to the other points in \(U\). Since the term \(u=u_U\) contributes \(\mathrm{p}(0)\), this also gives \[\frac{1}{m}\sum_{u\in U}\mathrm{p}({\rm d}({X_u},{\theta_U})) \ge \mathrm{p}(0)-\Delta.\] Now relying on the lower Lipschitz bound, we have \[\mathrm{p}(0)-\mathrm{p}\!\bigl({\rm d}({\theta_U},{X_v})\bigr) \ge \mathrm{p}(0) - \mathrm{p}\bigl( \min\{{\rm d}({\theta_U},{X_v}), r_\mathrm{p}\}\bigr) \ge \ell_\mathrm{p}\min\{{\rm d}({\theta_U},{X_v}), r_\mathrm{p}\}\,.\] And hence, \[\begin{align} \label{eq:truncated-average} \frac{1}{m-1}\sum_{\substack{v\in U\\v\neq u_U}} \min\{{\rm d}({\theta_U},{X_v}), r_\mathrm{p}\} \le \tfrac{\Delta}{\ell_\mathrm{p}}\,. \end{align}\tag{2}\]

Markov’s inequality.  From the above truncated average, we can deduce a tail bound as long as \(R\le r_\mathrm{p}\) via Markov’s inequality: \[\left|\{u\in U:X_u\notin B(\theta_U,R)\}\right|R \le \sum_{u\in U}\min\{{\rm d}({X_u},{\theta_U}),r_\mathrm{p}\} \le \sum_{\substack{u\in U\\u\neq u_U}}\min\{{\rm d}({X_u},{\theta_U}),r_\mathrm{p}\} \le |U| \cdot \frac{\Delta}{\ell_\mathrm{p}}.\]

Average radius under \(1\)-window-safety.  Assume that \(U\) is \(1\)-window-safe. Then every distance \({\rm d}({\theta_U},{X_v})\) lies in \([0,r_\mathrm{p}]\), so the truncated average bound 2 is actually an average radius bound. Therefore \[\bar d_U(\theta_U) = \frac{1}{m}\sum_{v\in U}{\rm d}({X_v},{\theta_U}) \le \frac{m-1}{m}\frac{\Delta}{\ell_\mathrm{p}} \le \frac{\Delta}{\ell_\mathrm{p}}.\] ◻

Proof. This is just the combination of the two route-specific propositions below (Propositions 32 and [prop:localized-cluster-separated-seed]). Choose \(A_{\text{\tiny{\ref{prop:link-average-separation}}}}\) so that \[A_{\text{\tiny{\ref{prop:link-average-separation}}}} \ge \max\left\{ L_\mathrm{p}+\frac{L_\mathrm{p}}{\ell_\mathrm{p}}+2, 2(L_\mathrm{p}+M_\mathrm{p})+2 \right\}.\] The lower bound above on \(K\) implies the \(K\)-requirements in Propositions 32 and [prop:localized-cluster-separated-seed] when their \(A\)-parameters are set equal to \(A_{\text{\tiny{\ref{prop:link-average-separation}}}}\). The scale assumption \(Kr\le\tfrac12\min\{1,r_\mathrm{p}\}\) implies the scale assumption in either route-specific proposition.

In the Oracle Route case, apply Proposition 32. In the Local Route case, apply Proposition [prop:localized-cluster-separated-seed] with \(\tau=r\). In both cases, use the same \(A\)-parameter \(A_{\text{\tiny{\ref{prop:link-average-separation}}}}\) and the same outer-radius parameter \(K\). This gives the claimed link-average separation. ◻

Proof. Since \(U\) is \(\lambda_{\mathrm{win}}\)-window-safe and \(\theta_U\in X_U\), every \(u\in U\) satisfies \[{\rm d}({X_u},{\theta_U})\le \lambda_{\mathrm{win}}r_\mathrm{p}.\] Also, \(U\) is \(1\)-window-safe, so Lemma 6 gives \[\bar d_U(\theta_U)\le \frac{r}{\ell_\mathrm{p}}.\]

If \({\rm d}({y},{\theta_U})\le r\), then for every \(u\in U\), \[{\rm d}({X_u},{y}) \le {\rm d}({X_u},{\theta_U})+{\rm d}({\theta_U},{y}) \le \lambda_{\mathrm{win}}r_\mathrm{p}+r \le r_\mathrm{p}.\] The local Lipschitz bound and the triangle inequality give \[\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(y)}\hypersetup{linkcolor=blue} \ge \mathrm{p}({\rm d}({\theta_U},{y}))-L_\mathrm{p}\bar d_U(\theta_U) \ge \mathrm{p}(0)-L_\mathrm{p}r-\frac{L_\mathrm{p}}{\ell_\mathrm{p}}r \ge \widehat{\mathrm{p}}(0)-L_\mathrm{p}r-\frac{L_\mathrm{p}}{\ell_\mathrm{p}}r-r \ge \widehat{\mathrm{p}}(0)-A_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}}r+r.\]

Now suppose \({\rm d}({y},{\theta_U})\ge K_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}}r\). If \({\rm d}({y},{\theta_U})\le (1-\lambda_{\mathrm{win}})r_\mathrm{p}\), then the same link-average approximation gives \[\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(y)}\hypersetup{linkcolor=blue} \le \mathrm{p}({\rm d}({\theta_U},{y}))+L_\mathrm{p}\bar d_U(\theta_U) \le \mathrm{p}(0)-\ell_\mathrm{p}K_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}}r +\frac{L_\mathrm{p}}{\ell_\mathrm{p}}r \le \widehat{\mathrm{p}}(0) -\ell_\mathrm{p}K_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}}r +\frac{L_\mathrm{p}}{\ell_\mathrm{p}}r +r.\] If instead \({\rm d}({y},{\theta_U})>(1-\lambda_{\mathrm{win}})r_\mathrm{p}\), then every \(u\in U\) satisfies \[{\rm d}({X_u},{y}) \ge {\rm d}({y},{\theta_U})-{\rm d}({X_u},{\theta_U}) > (1-2\lambda_{\mathrm{win}})r_\mathrm{p}.\] By monotonicity and the local lower Lipschitz bound, \[\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(y)}\hypersetup{linkcolor=blue} \le \mathrm{p}(0)-\ell_\mathrm{p}(1-2\lambda_{\mathrm{win}})r_\mathrm{p} \le \mathrm{p}(0)-\ell_\mathrm{p}K_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}}r.\] Since \(\mathrm{p}(0)\le\widehat{\mathrm{p}}(0)+r\), both cases give \[\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(y)}\hypersetup{linkcolor=blue} \le \widehat{\mathrm{p}}(0)-\ell_\mathrm{p}K_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}}r +\frac{L_\mathrm{p}}{\ell_\mathrm{p}}r+r.\] The choices of \(A_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}}\) and \(K_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}}\) imply \[\ell_\mathrm{p}K_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}} \ge 2A_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}} \ge A_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}} +\frac{L_\mathrm{p}}{\ell_\mathrm{p}}+2,\] and hence \[\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(y)}\hypersetup{linkcolor=blue} \le \widehat{\mathrm{p}}(0)-A_{\text{\tiny{\ref{prop:window-safe-internal-average-separated-seed}}}}r-r.\] This is exactly the claimed link-average separation. ◻

Proof. Choose \(G\subseteq U\) such that \[|G|\ge(1-\tau)|U|, \qquad X_u\in B(x,\tau)\quad\text{for all }u\in G.\] Let \(C_0:=L_\mathrm{p}+M_\mathrm{p}\). If \({\rm d}({y},{x})\le\tau\), then for every \(u\in G\), \[{\rm d}({X_u},{y})\le2\tau\le r_\mathrm{p},\] and hence \[\mathrm{p}({\rm d}({X_u},{y}))\ge \mathrm{p}(0)-2L_\mathrm{p}\tau.\] The remaining vertices contribute at least \(-M_\mathrm{p}\), while \(\mathrm{p}(0)\le M_\mathrm{p}\). Therefore \[\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(y)}\hypersetup{linkcolor=blue} \ge (1-\tau)(\mathrm{p}(0)-2L_\mathrm{p}\tau)-\tau M_\mathrm{p} \ge \mathrm{p}(0)-2C_0\tau \ge \widehat{\mathrm{p}}(0)-(2C_0+1)\tau \ge \widehat{\mathrm{p}}(0)-A_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}\tau+\tau.\]

Now suppose \({\rm d}({y},{x})\ge K_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}\tau\). For every \(u\in G\), \[{\rm d}({X_u},{y})\ge (K_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}-1)\tau.\] Since \(\mathrm{p}\) is non-increasing and bi-Lipschitz on \([0,r_\mathrm{p}]\), \[\mathrm{p}({\rm d}({X_u},{y})) \le \mathrm{p}((K_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}-1)\tau) \le \mathrm{p}(0)-\ell_\mathrm{p}(K_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}-1)\tau.\] The remaining vertices contribute at most \(\mathrm{p}(0)\). Hence \[\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(y)}\hypersetup{linkcolor=blue} \le (1-\tau)\bigl(\mathrm{p}(0)-\ell_\mathrm{p}(K_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}-1)\tau\bigr) + \tau\mathrm{p}(0) = \mathrm{p}(0)-(1-\tau)\ell_\mathrm{p}(K_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}-1)\tau.\] Since \(\tau\le1/2\) and \[K_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}} \ge 1+\frac{2(A_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}+2)}{\ell_\mathrm{p}},\] we have \[(1-\tau)\ell_\mathrm{p}(K_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}-1)\tau \ge (A_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}+2)\tau.\] \[\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(y)}\hypersetup{linkcolor=blue} \le \mathrm{p}(0)-(A_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}+2)\tau \le \widehat{\mathrm{p}}(0)-A_{\text{\tiny{\ref{prop:localized-cluster-separated-seed}}}}\tau-\tau.\] This is exactly the claimed link-average separation. ◻

Proof. Fix \(x\in M\). On \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(W,\rho)}\hypersetup{linkcolor=blue}\), there exists \(U_x\subseteq W\) with \(|U_x|=m\) such that \[X_u\in B(x,\rho) \qquad\text{for every }u\in U_x.\] Thus \({\rm d}({X_u},{X_v})<2\rho\) for all distinct \(u,v\in U_x\), and hence \[\overline{\mathrm{p}}\!\left(U_x\right)\ge \mathrm{p}(2\rho).\] Using \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(W,L_\mathrm{p}\rho,m)}\hypersetup{linkcolor=blue}\), \[\widehat{\mathrm{p}}(0)\ge\overline{N}\!\left(U_x\right)\ge\overline{\mathrm{p}}\!\left(U_x\right)-L_\mathrm{p}\rho \ge \mathrm{p}(2\rho)-L_\mathrm{p}\rho.\] Since \(2\rho\le r_\mathrm{p}\) and \(\mathrm{p}\) is \(L_\mathrm{p}\)-Lipschitz on \([0,r_\mathrm{p}]\), \[\mathrm{p}(2\rho)\ge \mathrm{p}(0)-2L_\mathrm{p}\rho,\] which gives the lower bound.

For the upper bound, let \(U\subseteq W\) have \(|U|=m\). Since \(\mathrm{p}\) is non-increasing, \(\overline{\mathrm{p}}\!\left(U\right)\le\mathrm{p}(0)\). Again using \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(W,L_\mathrm{p}\rho,m)}\hypersetup{linkcolor=blue}\), \[\overline{N}\!\left(U\right)\le\overline{\mathrm{p}}\!\left(U\right)+L_\mathrm{p}\rho\le\mathrm{p}(0)+L_\mathrm{p}\rho.\] Taking the maximum over all such \(U\) proves the claim. ◻

Proof. By Lemma 7, \[\mathrm{p}(0)-3L_\mathrm{p}\rho \le \widehat{\mathrm{p}}(0) \le \mathrm{p}(0)+L_\mathrm{p}\rho.\] This proves the first assertion.

For every \(x\in M\), the event \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(W,\rho)}\hypersetup{linkcolor=blue}\) gives a set \(U_x\subseteq W\) with \(|U_x|=m_\rho\) and \(X_u\in B(x,\rho)\) for all \(u\in U_x\). As in the proof of Lemma 7, \[\overline{N}\!\left(U_x\right) \ge \mathrm{p}(2\rho)-L_\mathrm{p}\rho \ge \mathrm{p}(0)-3L_\mathrm{p}\rho.\] Since \[\widehat{\mathrm{p}}(0)\le \mathrm{p}(0)+L_\mathrm{p}\rho,\] we have \[\overline{N}\!\left(U_x\right) \ge \widehat{\mathrm{p}}(0)-4L_\mathrm{p}\rho = \widehat{\mathrm{p}}(0)-\Delta_\rho.\] Thus \(U_x\in\mathcal{C}_\rho\), proving the second assertion.

Now let \(U\in\mathcal{C}_\rho\). Then \[\overline{N}\!\left(U\right)\ge \widehat{\mathrm{p}}(0)-\Delta_\rho.\] Using the lower bound \[\widehat{\mathrm{p}}(0)\ge \mathrm{p}(0)-3L_\mathrm{p}\rho\] and the event \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(W,L_\mathrm{p}\rho,m_\rho)}\hypersetup{linkcolor=blue}\), we get \[\overline{\mathrm{p}}\!\left(U\right) \ge \overline{N}\!\left(U\right)-L_\mathrm{p}\rho \ge \mathrm{p}(0)-8L_\mathrm{p}\rho.\] This proves the third assertion. ◻

Proof. This is the combination of the two route-specific propositions below. Choose \(K_{\text{\tiny{\ref{prop:candidate-refinement-net}}}}\) larger than \(4\), larger than \(48L_\mathrm{p}/\ell_\mathrm{p}\), larger than \(8L_\mathrm{p}\), large enough compared with the constants in Propositions 39 and 40, and large enough that \[K_{\text{\tiny{\ref{prop:candidate-refinement-net}}}} \ge 1+\frac{2(A_{\text{\tiny{\ref{prop:link-average-separation}}}}+2)}{\ell_\mathrm{p}}.\] Let \(K\ge K_{\text{\tiny{\ref{prop:candidate-refinement-net}}}}\). The scale condition above then implies the scale assumptions in the corresponding route proposition, including \[Kr_{\rm ref} \le \tfrac12\min\{1,r_\mathrm{p}\}.\] In either case, apply the corresponding route-specific proposition. By the choice of \(K_{\text{\tiny{\ref{prop:candidate-refinement-net}}}}\), the route-specific outer radius is \(Kr_{\rm ref}\), and the route-specific net radius in either case is \[\tfrac13Kr_{\rm ref}.\] ◻

Proof. The first implication gives separation: if two distinct vertices of \(\mathcal{N}\) had representative distance at most \(\delta\), they would be adjacent. For covering, fix \(x\in M\) and choose \(U_x\). By maximality, either \(U_x\in\mathcal{N}\), or \(U_x\stackrel{H}{\sim} U\) for some \(U\in\mathcal{N}\). In the latter case, \[{\rm d}({x},{\theta_U}) \le {\rm d}({x},{\theta_{U_x}})+{\rm d}({\theta_{U_x}},{\theta_U}) \le \rho_{\rm cov}+K_{\rm cmp}\delta.\] ◻

Proof. For every \((u_1,u_2)\in\mathcal{D}(U_1,U_2)\), the assumed diameter bound puts both \({\rm d}({X_{u_1}},{X_{u_2}})\) and \({\rm d}({x_1},{x_2})\) inside \([0,r_\mathrm{p}]\). Therefore the local \(L_\mathrm{p}\)-Lipschitz bound applies: \[\begin{align} \left|\overline{\mathrm{p}}\!\left(U_1,U_2\right) - \mathrm{p}\!\bigl({\rm d}({x_1},{x_2})\bigr)\right| \le& \frac{1}{|\mathcal{D}(U_1,U_2)|} \sum_{(u_1,u_2) \in \mathcal{D}(U_1,U_2)} L_\mathrm{p}\left|{\rm d}({X_{u_1}},{X_{u_2}}) - {\rm d}({x_1},{x_2})\right|\\ \le& \frac{1}{|\mathcal{D}(U_1,U_2)|} \sum_{(u_1,u_2) \in \mathcal{D}(U_1,U_2)} L_\mathrm{p}({\rm d}({X_{u_1}},{x_1})+{\rm d}({X_{u_2}},{x_2}))\\ \le& \frac{1}{|\mathcal{D}(U_1,U_2)|} \sum_{u_1 \in U_1,u_2 \in U_2} L_\mathrm{p}({\rm d}({X_{u_1}},{x_1})+{\rm d}({X_{u_2}},{x_2}))\\ \le& \frac{|U_1||U_2|}{|\mathcal{D}(U_1,U_2)|}\,2L_\mathrm{p}R \le 4L_\mathrm{p}R, \end{align}\] where in the last step we used the fact that \[|\mathcal{D}(U_1,U_2)| \ge |U_1||U_2| - \min\{|U_1|,|U_2|\} \ge m(m-1)\,.\] ◻

Proof. For \(u_i\in U_i\), \[{\rm d}({X_{u_1}},{X_{u_2}}) \ge {\rm d}({x_1},{x_2})-{\rm d}({X_{u_1}},{x_1})-{\rm d}({X_{u_2}},{x_2}) \ge (1-4\lambda_{\mathrm{win}})r_\mathrm{p}.\] Since \(\mathrm{p}\) is non-increasing, \[\mathrm{p}({\rm d}({X_{u_1}},{X_{u_2}})) \le \mathrm{p}((1-4\lambda_{\mathrm{win}})r_\mathrm{p}).\] Averaging gives the first inequality. Since \((1-4\lambda_{\mathrm{win}})r_\mathrm{p}\in[0,r_\mathrm{p}]\), the local lower bi-Lipschitz bound gives the second inequality. ◻

Proof of Proposition 39. Set \[\rho_{\rm sep}:= \sqrt{K}r_{\rm ref},\] which is the separation scale for the comparison graph \(H_{\mathrm{ora}}\). Taking \(K_{\text{\tiny{\ref{prop:oracle-candidate-net}}}}\) large enough, the assumptions on \(r_{\rm ref}\) imply \[8L_\mathrm{p}\rho\le r_{\rm ref}.\]

The oracle-filtered family still covers.  For every \(x\in M\), Proposition 36 gives \(U_x\in\mathcal{C}_\rho\) such that \[X_u\in B(x,\rho) \qquad\text{for every }u\in U_x.\] Thus, for \(u,v\in U_x\), \[{\rm d}({X_u},{X_v})<2\rho\le \alpha_{\mathrm{win}}r_\mathrm{p},\] by the assumption on \(\alpha_{\mathrm{win}}\). The oracle therefore certifies every pair in \(U_x\), so \[U_x\in\mathcal{C}_\rho^{\mathrm{ora}}.\]

Average-radius control.  If \(U\in\mathcal{C}_\rho^{\mathrm{ora}}\), then the oracle implication \(\mathcal{O}_{\mathrm{win}}(u,v)=1\Rightarrow {\rm d}({X_u},{X_v})\le \lambda_{\mathrm{win}}r_\mathrm{p}\) shows that \(U\) is \(\lambda_{\mathrm{win}}\)-window-safe and hence \(1\)-window-safe. Since Proposition 36 gives \[\overline{\mathrm{p}}\!\left(U\right)\ge \mathrm{p}(0)-8L_\mathrm{p}\rho,\] Lemma 6 gives \[\begin{align} \label{eq:oracle-candidate-average-radius-control} \bar d_U(\theta_U) \le \frac{8L_\mathrm{p}}{\ell_\mathrm{p}}\rho \qquad\text{for every }U\in\mathcal{C}_\rho^{\mathrm{ora}}. \end{align}\tag{3}\] Moreover, since \(\theta_U\in X_U\), every \(u\in U\) satisfies \[{\rm d}({X_u},{\theta_U})\le \lambda_{\mathrm{win}}r_\mathrm{p}.\]

Close representatives are adjacent.  Let \(U_1,U_2\in\mathcal{C}_\rho^{\mathrm{ora}}\), and write \[d_{12}:={\rm d}({\theta_{U_1}},{\theta_{U_2}}).\] If \(d_{12}\le\rho_{\rm sep}\), then for every \(u_i\in U_i\), \[{\rm d}({X_{u_1}},{X_{u_2}}) \le {\rm d}({X_{u_1}},{\theta_{U_1}})+d_{12}+{\rm d}({\theta_{U_2}},{X_{u_2}}) \le \lambda_{\mathrm{win}}r_\mathrm{p}+ \rho_{\rm sep} + \lambda_{\mathrm{win}}r_\mathrm{p} \le \tfrac{1}{4}r_\mathrm{p}+ \rho_{\rm sep} \le r_\mathrm{p},\] where the last inequality follows from \(\rho_{\rm sep}=\sqrt{K}r_{\rm ref} \le K^{-2.5}\min\{1,r_\mathrm{p}\}\). Since it holds for every \(u_i\in U_i\), we have \[\operatorname{diam}(X_{U_1}\cup X_{U_2}\cup \{\theta_{U_1},\theta_{U_2}\}) \le r_\mathrm{p}.\] Lemma 9 with \(\bar d_U(\theta_U) \le \frac{8L_\mathrm{p}}{\ell_\mathrm{p}}\rho\) from 3 and the event \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(W,L_\mathrm{p}\rho,m_\rho)}\hypersetup{linkcolor=blue}\) give \[\left| \overline{N}\!\left(U_1,U_2\right) - \mathrm{p}(d_{12}) \right| \le \left| \overline{N}\!\left(U_1,U_2\right) - \overline{\mathrm{p}}\!\left(U_1,U_2\right) \right| + \left| \overline{\mathrm{p}}\!\left(U_1,U_2\right) - \mathrm{p}(d_{12}) \right| \le 4L_\mathrm{p}\cdot \frac{8L_\mathrm{p}}{\ell_\mathrm{p}}\rho + L_\mathrm{p}\rho \le 0.1L_\mathrm{p}\rho_{\rm sep},\] provided \(K_{\text{\tiny{\ref{prop:oracle-candidate-net}}}}\) is large enough. Therefore \[\overline{N}\!\left(U_1,U_2\right) \ge \mathrm{p}(d_{12})-0.1 L_\mathrm{p}\rho_{\rm sep} \ge \mathrm{p}(0)-L_\mathrm{p}\rho_{\rm sep}-0.1 L_\mathrm{p}\rho_{\rm sep} \ge \widehat{\mathrm{p}}(0)- 3L_\mathrm{p}\rho -L_\mathrm{p}\rho_{\rm sep}-0.1 L_\mathrm{p}\rho_{\rm sep} \ge \widehat{\mathrm{p}}(0)- 2L_\mathrm{p}\rho_{\rm sep}\] where the last inequality holds when \(K_{\text{\tiny{\ref{prop:oracle-candidate-net}}}}\) is large enough. Thus \(U_1\stackrel{H_{\mathrm{ora}}}{\sim}U_2\).

Adjacent representatives are not too far.  Assume now that \[d_{12}>K_{\rm cover}\rho_{\rm sep},\] for some \(K_{\rm cover}\) to be chosen later. We show that \(U_1\) and \(U_2\) are not adjacent. First suppose \[d_{12}\le (1-2\lambda_{\mathrm{win}})r_\mathrm{p}.\] Then the same triangle-inequality check as above gives \[\operatorname{diam}(X_{U_1}\cup X_{U_2}\cup \{\theta_{U_1},\theta_{U_2}\}) \le r_\mathrm{p},\] and the same approximation bound gives \[\overline{N}\!\left(U_1,U_2\right) \le \mathrm{p}(d_{12})+0.1 L_\mathrm{p}\rho_{\rm sep} \le \mathrm{p}(0)-\ell_\mathrm{p}d_{12}+0.1 L_\mathrm{p}\rho_{\rm sep} \le \mathrm{p}(0)-\ell_\mathrm{p}K_{\rm cover}\rho_{\rm sep}+0.1 L_\mathrm{p}\rho_{\rm sep} \le \widehat{\mathrm{p}}(0)-2L_\mathrm{p}\rho_{\rm sep},\] where \(K_{\rm cover}\) is chosen large enough depending only on \(L_\mathrm{p}\) and \(\ell_\mathrm{p}\), for example, \[K_{\rm cover} = \tfrac{1}{\ell_\mathrm{p}} \left( 2L_\mathrm{p}+ 0.1 L_\mathrm{p}+ 3L_\mathrm{p} \right)\] suffices, due to \(\rho \le \rho_{\rm sep}\).

Thus \(U_1\) and \(U_2\) are not adjacent.

It remains to consider \[d_{12}>(1-2\lambda_{\mathrm{win}})r_\mathrm{p}.\] Lemma 10, applied with \(x_i=\theta_{U_i}\), gives \[\overline{\mathrm{p}}\!\left(U_1,U_2\right) \le \mathrm{p}(0)-\ell_\mathrm{p}(1-4\lambda_{\mathrm{win}})r_\mathrm{p}.\] Together with \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(W,L_\mathrm{p}\rho,m_\rho)}\hypersetup{linkcolor=blue}\), this yields \[\overline{N}\!\left(U_1,U_2\right) \le \mathrm{p}(0)-\ell_\mathrm{p}(1-4\lambda_{\mathrm{win}})r_\mathrm{p}+L_\mathrm{p}\rho < \widehat{\mathrm{p}}(0)-2L_\mathrm{p}\rho_{\rm sep},\] provided \(K_{\text{\tiny{\ref{prop:oracle-candidate-net}}}}\) is large enough. Thus, in all cases, adjacency implies \[{\rm d}({\theta_{U_1}},{\theta_{U_2}})\le K_{\rm cover}\rho_{\rm sep}.\]

Apply the comparison graph selection lemma.  The oracle-filtered covering step gives, for every \(x\in M\), a candidate \(U_x\in\mathcal{C}_\rho^{\mathrm{ora}}\) with \[{\rm d}({x},{\theta_{U_x}})\le\rho.\] The preceding two steps verify the hypotheses of Lemma 8 with \[\delta=\rho_{\rm sep}, \qquad \rho_{\rm cov}=\rho, \qquad K_{\rm cmp}=K_{\rm cover}.\] Thus the selected representatives are \(\rho_{\rm sep}\)-separated and form a \((\rho+K_{\rm cover}\rho_{\rm sep})\)-net. Since \(\rho\le\rho_{\rm sep}\), this net radius is at most \[(1+K_{\rm cover})\rho_{\rm sep}.\] By increasing \(K_{\text{\tiny{\ref{prop:oracle-candidate-net}}}}\) if necessary, this is at most \(\tfrac{K}{3} r_{\rm ref}\). The separation also implies that the representatives \(\theta_U=X_{u_U}\), \(U\in\mathcal{N}_{\mathrm{ora}}\), are all distinct. Hence the map \(U\mapsto u_U\) injects \(\mathcal{N}_{\mathrm{ora}}\) into \(W\), and \(|\mathcal{N}_{\mathrm{ora}}|\le |W|\).

Separated-seed certificates.  For every selected \(U\), Proposition 36 gives \[\overline{\mathrm{p}}\!\left(U\right)\ge \mathrm{p}(0)-8L_\mathrm{p}\rho,\] and the oracle filter gives \(\lambda_{\mathrm{win}}\)-window-safe. Also \[|\widehat{\mathrm{p}}(0)-\mathrm{p}(0)|\le 3L_\mathrm{p}\rho\le r_{\rm ref}.\] Since \(8L_\mathrm{p}\rho\le r_{\rm ref}\), \(U\) is an \(r_{\rm ref}\)-internal-average candidate. The choice of \(K_{\text{\tiny{\ref{prop:oracle-candidate-net}}}}\) and the assumption \(K^3r_{\rm ref}\le \min\{1,r_\mathrm{p}\}\) give the \(K\)-requirements in Proposition 31. Therefore Proposition 31, in the Oracle Route case, applied with \(r=r_{\rm ref}\), the estimate for \(\widehat{\mathrm{p}}(0)\), and this value of \(K\), gives the required refinement-net certificate. ◻

Proof. For \(i=1,2\), choose \(G_i\subseteq U_i\) such that \[|G_i|\ge(1-\tau)m, \qquad X_u\in B(x_i,\tau)\quad\text{for all }u\in G_i,\] and set \(B_i:=U_i\setminus G_i\). Let \[d_0:={\rm d}({x_1},{x_2}), \qquad \underline A:=\mathrm{p}(d_0+2\tau), \qquad \overline{A}:=\mathrm{p}((d_0-2\tau)_+), \qquad D_{12}:=|\mathcal{D}(U_1,U_2)|.\] For every \((u_1,u_2)\in G_1\times G_2\), \(u_1\neq u_2\), the triangle inequality gives \[(d_0-2\tau)_+\le {\rm d}({X_{u_1}},{X_{u_2}})\le d_0+2\tau.\] Hence the corresponding \(\mathrm{p}\)-values lie between \(\underline A\) and \(\overline{A}\). Let \(\mathcal{B}\subseteq\mathcal{D}(U_1,U_2)\) be the set of ordered pairs for which at least one endpoint lies in \(B_1\cup B_2\). Then \[|\mathcal{B}|\le |B_1|m+|B_2|m\le 2\tau m^2, \qquad D_{12}\ge m(m-1),\] and therefore, since \(m\ge2\) and \(\tau\le1/2\), \[\frac{|\mathcal{B}|}{D_{12}}\le 4\tau.\] Because all \(\mathrm{p}\)-values have absolute value at most \(M_\mathrm{p}\), replacing the good-pair bounds by arbitrary bad-pair values can change the average by at most \(2M_\mathrm{p}|\mathcal{B}|/D_{12}\). Consequently, \[\overline{\mathrm{p}}\!\left(U_1,U_2\right)\ge \underline A-2M_\mathrm{p}\frac{|\mathcal{B}|}{D_{12}} \ge \underline A-8M_\mathrm{p}\tau\] and \[\overline{\mathrm{p}}\!\left(U_1,U_2\right)\le \overline{A}+2M_\mathrm{p}\frac{|\mathcal{B}|}{D_{12}} \le \overline{A}+8M_\mathrm{p}\tau.\] ◻

Proof of Proposition 40. Set \[\rho_{\rm sep}:= \sqrt{K}r_{\rm ref}.\] By Proposition 36 and Remark 34, every \(U\in\mathcal{C}_\rho\) is a \((r_{\rm ref},r_{\rm ref})\)-cluster with center \(\theta_U\). Here we use the scale assumptions above and take \(K_{\text{\tiny{\ref{prop:local-link-candidate-net}}}}\) large enough so that \[\sqrt{\frac{8L_\mathrm{p}\rho}{\ell_\mathrm{p}}}\le r_{\rm ref}, \qquad 3L_\mathrm{p}\rho\le r_{\rm ref}.\]

Let \(U_1,U_2\in\mathcal{C}_\rho\), and write \[d_{12}:={\rm d}({\theta_{U_1}},{\theta_{U_2}}).\] By Lemma 11 and \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(W,L_\mathrm{p}\rho,m_\rho)}\hypersetup{linkcolor=blue}\), \[\overline{N}\!\left(U_1,U_2\right) \ge \mathrm{p}(d_{12}+2r_{\rm ref})-8M_\mathrm{p}r_{\rm ref}-L_\mathrm{p}\rho\] and \[\overline{N}\!\left(U_1,U_2\right) \le \mathrm{p}((d_{12}-2r_{\rm ref})_+)+8M_\mathrm{p}r_{\rm ref}+L_\mathrm{p}\rho.\] Also, Proposition 36 gives \[\mathrm{p}(0)-3L_\mathrm{p}\rho \le \widehat{\mathrm{p}}(0) \le \mathrm{p}(0)+L_\mathrm{p}\rho.\] By choosing \(K_{\text{\tiny{\ref{prop:local-link-candidate-net}}}}\) large enough, the scale assumptions ensure \[L_\mathrm{p}\rho_{\rm sep} \ge 2L_\mathrm{p}r_{\rm ref}+8M_\mathrm{p}r_{\rm ref}+2L_\mathrm{p}\rho, \qquad \ell_\mathrm{p}\rho_{\rm sep} \ge 8M_\mathrm{p}r_{\rm ref}+5L_\mathrm{p}\rho, \qquad \rho_{\rm sep}\ge \max\{r_{\rm ref},\rho\}.\] If \[d_{12}\le \rho_{\rm sep},\] then \(d_{12}+2r_{\rm ref}\le 3\rho_{\rm sep}\le r_\mathrm{p}\), and the Lipschitz bound gives \[\overline{N}\!\left(U_1,U_2\right) \ge \mathrm{p}(0)-L_\mathrm{p}(d_{12}+2r_{\rm ref})-8M_\mathrm{p}r_{\rm ref}-L_\mathrm{p}\rho \ge \widehat{\mathrm{p}}(0)-2L_\mathrm{p}\rho_{\rm sep}.\] Thus \(U_1\stackrel{H_{\mathrm{loc}}}{\sim}U_2\).

If \[d_{12}> 2r_{\rm ref}+ \left(1+2\frac{L_\mathrm{p}}{\ell_\mathrm{p}}\right)\rho_{\rm sep},\] then \(d_{12}-2r_{\rm ref}>(1+2L_\mathrm{p}/\ell_\mathrm{p})\rho_{\rm sep}\). Since \((1+2L_\mathrm{p}/\ell_\mathrm{p})\rho_{\rm sep}\le r_\mathrm{p}\), monotonicity and the lower Lipschitz bound give \[\begin{align} \overline{N}\!\left(U_1,U_2\right) &\le \mathrm{p}\!\left(\left(1+2\frac{L_\mathrm{p}}{\ell_\mathrm{p}}\right)\rho_{\rm sep}\right) +8M_\mathrm{p}r_{\rm ref}+L_\mathrm{p}\rho\\ &\le \mathrm{p}(0)-\ell_\mathrm{p}\rho_{\rm sep}-2L_\mathrm{p}\rho_{\rm sep} +8M_\mathrm{p}r_{\rm ref}+L_\mathrm{p}\rho\\ &< \widehat{\mathrm{p}}(0)-2L_\mathrm{p}\rho_{\rm sep}. \end{align}\] Thus \(U_1\) and \(U_2\) are not adjacent. Therefore adjacency implies \[\begin{align} \label{eq:local-candidate-adjacent-representatives-close} d_{12}\le 2r_{\rm ref}+\left(1+2\frac{L_\mathrm{p}}{\ell_\mathrm{p}}\right)\rho_{\rm sep}. \end{align}\tag{4}\] Apply the comparison graph selection lemma.  Proposition 36 supplies, for every \(x\in M\), a candidate \(U_x\in\mathcal{C}_\rho\) with \[{\rm d}({x},{\theta_{U_x}})\le\rho.\] Since \(r_{\rm ref}\le\rho_{\rm sep}\), 4 gives \[U_1\stackrel{H_{\mathrm{loc}}}{\sim}U_2 \quad\Longrightarrow\quad d_{12}\le \left(3+2\frac{L_\mathrm{p}}{\ell_\mathrm{p}}\right)\rho_{\rm sep}.\] Lemma 8, applied with \[\delta=\rho_{\rm sep}, \qquad \rho_{\rm cov}=\rho, \qquad K_{\rm cmp}=3+2\frac{L_\mathrm{p}}{\ell_\mathrm{p}},\] shows that the selected representatives are \(\rho_{\rm sep}\)-separated and form a net of radius at most \[\rho+\left(3+2\frac{L_\mathrm{p}}{\ell_\mathrm{p}}\right)\rho_{\rm sep} \le 4\left(1+\frac{L_\mathrm{p}}{\ell_\mathrm{p}}\right)\rho_{\rm sep}.\] By increasing \(K_{\text{\tiny{\ref{prop:local-link-candidate-net}}}}\) if necessary, this is at most \(\tfrac13 Kr_{\rm ref}\). The separation also implies that the representatives \(\theta_U=X_{u_U}\), \(U\in\mathcal{N}_{\mathrm{loc}}\), are all distinct. Hence the map \(U\mapsto u_U\) injects \(\mathcal{N}_{\mathrm{loc}}\) into \(W\), and \(|\mathcal{N}_{\mathrm{loc}}|\le |W|\).

Separated-seed certificates.  Each selected \(U\) is a \((r_{\rm ref},r_{\rm ref})\)-cluster with center \(\theta_U\). Furthermore, \[|\widehat{\mathrm{p}}(0)-\mathrm{p}(0)|\le 3L_\mathrm{p}\rho\le r_{\rm ref}.\] By the choice of \(K_{\text{\tiny{\ref{prop:local-link-candidate-net}}}}\), and since \(K^3r_{\rm ref}\le\min\{1,r_\mathrm{p}\}\), the \(K\)-requirements in Proposition 31 hold. Proposition 31, in the Local Route case, applied with \(r=r_{\rm ref}\), the estimate for \(\widehat{\mathrm{p}}(0)\), and this value of \(K\), gives the required refinement-net certificate. ◻

Proof. Define \[V_{\rm in}:=\{v\in V:X_v\in B(x_0,R_{\rm in})\}, \qquad V_{\rm out}:=\{v\in V:X_v\notin B(x_0,R_{\rm out})\},\] and \[\mathcal{I}_{\rm ref} := \left\{ v\in V: |\hypersetup{linkcolor=black}\hyperref[eq:def-normalized-average]{{\rm N}_{U}(v)}\hypersetup{linkcolor=blue}-\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(v)}\hypersetup{linkcolor=blue}|>\gamma/2 \right\}.\] Set \(q:=q_{\rm ref}(m,\gamma)\) and \(b:=b_{\rm ref}\). Conditionally on \(X_U=x_U\) and \(X_V=x_V\), the indicators \(\mathbf{1}_{\{v\in\mathcal{I}_{\rm ref}\}}\), \(v\in V\), are independent, and Lemma 3 bounds each success probability by \(q\). Since \[\left(\sqrt{qn_\star}+\sqrt{L_{\rm fail}}\right)^2\le b,\] Remark 52 gives \[\mathbb{P}\left( |\mathcal{I}_{\rm ref}|>b \;\middle|\;X_U=x_U,\;X_V=x_V \right) \le \exp(-L_{\rm fail}).\] Work on the event \(|\mathcal{I}_{\rm ref}|\le b\).

If \(v\in V_{\rm in}\setminus\mathcal{I}_{\rm ref}\), then \(\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(v)}\hypersetup{linkcolor=blue}\ge t+\gamma\), and hence \[\hypersetup{linkcolor=black}\hyperref[eq:def-normalized-average]{{\rm N}_{U}(v)}\hypersetup{linkcolor=blue}\ge t+\gamma-\gamma/2>t.\] Thus \(V_{\rm in}\setminus\mathcal{I}_{\rm ref}\subseteq\widehat U\). Using \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(V,R_{\rm in})}\hypersetup{linkcolor=blue}\), \[|\widehat U\cap V_{\rm in}| \ge \frac{\phi(R_{\rm in}/3)}{2}n_\star-b.\] Similarly, if \(v\in V_{\rm out}\setminus\mathcal{I}_{\rm ref}\), then \(\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(v)}\hypersetup{linkcolor=blue}\le t-\gamma\), and \[\hypersetup{linkcolor=black}\hyperref[eq:def-normalized-average]{{\rm N}_{U}(v)}\hypersetup{linkcolor=blue}\le t-\gamma+\gamma/2<t,\] so \(v\notin\widehat U\). Therefore \[\widehat U\cap V_{\rm out}\subseteq\mathcal{I}_{\rm ref}, \qquad |\widehat U\cap V_{\rm out}|\le b.\] The bound ?? gives \[|\widehat U| \ge \frac{\phi(R_{\rm in}/3)}{4}n_\star,\] and then \[\frac{|\widehat U\cap V_{\rm out}|}{|\widehat U|} \le \frac{4b_{\rm ref}}{\phi(R_{\rm in}/3)n_\star}.\] This is exactly the asserted cluster bound.

For the exact-inclusion clause, ?? and the union bound give \[\mathbb{P}\left( \mathcal{I}_{\rm ref}\neq\varnothing \;\middle|\;X_U=x_U,\;X_V=x_V \right) \le \exp(-L_{\rm fail}).\] On \(\mathcal{I}_{\rm ref}=\varnothing\), the two pointwise inclusions become \[V_{\rm in}\subseteq\widehat U \qquad\text{and}\qquad \widehat U\cap V_{\rm out}=\varnothing,\] which is the desired exact inclusion. ◻

Proof of Proposition 41. Since \[\min\{\gamma^2/4,1\}\ge \frac{1}{4}\min\{\gamma^2,1\},\] assumption ?? implies, after increasing \(C_{\text{\tiny{\ref{prop:readable-simultaneous-refinement}}}}\), that \[q_{\rm ref}(m,\gamma) \le \frac{1}{16}R_{\rm out}\varphi_{\rm in}.\] Assumption ?? gives \[L_{\rm fail}\le \frac{1}{16}R_{\rm out}\varphi_{\rm in}n_\star\] after decreasing \(c_{\text{\tiny{\ref{prop:readable-simultaneous-refinement}}}}\). Hence \[\begin{align} \label{eq:sim-refinement-bad-budget} b_{\rm ref}:= 2\bigl(q_{\rm ref}(m,\gamma)n_\star+L_{\rm fail}\bigr) &\le \frac{R_{\rm out}\varphi_{\rm in}}{4} n_\star \le \frac{\varphi_{\rm in}}{4} n_\star. \end{align}\tag{5}\] For each \(U\in\mathcal{N}\), apply Proposition 12 with \[x_0=\theta_U,\qquad t=\Theta.\] Since \(|U|\ge m\), monotonicity of \(q_{\rm ref}\) in the first argument gives \(q_{\rm ref}(|U|,\gamma)\le q_{\rm ref}(m,\gamma)\). Hence the corresponding single-seed value \[b_U:=2\bigl(q_{\rm ref}(|U|,\gamma)n_\star+L_{\rm fail}\bigr)\] satisfies \(b_U\le b_{\rm ref}\). The bound 5 implies the size conclusion and the cluster error bound \[\frac{4b_U}{\varphi_{\rm in}n_\star}\le R_{\rm out}\] for every seed. Union bounding over \(|\mathcal{N}|\le M_{\rm net}\) gives the claimed probability.

For the exact-inclusion conclusion, assumption ?? gives \[q_{\rm ref}(m,\gamma)\le n_\star^{-1}e^{-L_{\rm fail}}\] after increasing \(C_{\text{\tiny{\ref{prop:readable-simultaneous-refinement}}}}\) again. Thus, again using \(|U|\ge m\), \[n_\star q_{\rm ref}(m,\gamma)\le e^{-L_{\rm fail}},\] so the exact-inclusion clause of Proposition 12 applies to every seed. The same union bound over the refinement net proves the simultaneous exact-inclusion claim. ◻

Proof. Let \(V_1'\subseteq V_1\) have size \(n_1\), where \(n_1\) is chosen in 6 .

Probability of the first-block event.  The Uniform lower-occupancy Lemma 2 gives \[\mathbb{P}\left(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(V_1',\rho_\circ)}\hypersetup{linkcolor=blue}\right) \ge 1-n_1^{- \tfrac{1}{16}\Lambda}.\] Also, we apply the Uniform concentration of pair averages Lemma 5 with Remark 23 with \[\lambda = \rho_\circ, \qquad m = m_1, \qquad n = n_1, \qquad \phi = \tfrac{\phi(\rho_\circ/3)}{2},\] together with the assumption that \(C_{\rm ext}\) is large enough. The defining inequality 6 gives the condition required by the lemma: \[\mathsf{s}\tfrac{n_1}{\Lambda \log n_1} \cdot \tfrac{\phi(\rho_\circ/3)}{2} \cdot \rho_\circ^2 \ge C_{\text{\tiny{\ref{lem:uniform-pair-average}}}}.\] Then, we have \[\mathbb{P}\left(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(V_1',L_\mathrm{p}\rho_\circ,m_1)}\hypersetup{linkcolor=blue}\, \vert\, X_{V_1'}\right) \ge 1 - \exp \left\{ - c_{\text{\tiny{\ref{lem:uniform-pair-average}}}} \phi(\rho_\circ/3) n_1 \log( e/ \phi(\rho_\circ/3) ) \right\} \ge 1 - n_1^{-c_{\text{\tiny{\ref{lem:uniform-pair-average}}}} \Lambda},\] where the last inequality holds from our assumption on \(n_1\), \(\mathsf{s}\le 1\), and \(\log(e/\phi(\rho_\circ/3)) \ge \log e =1\). Therefore, we conclude that for \(C_{\rm ext}\) and \(\Lambda\) greater than some constants depending on the model parameters, the event holds with \[1-n_1^{-c\Lambda} = 1-o(1).\]

Construction of the refinement net.  Within the event, Proposition 36 gives \[\widehat{\mathrm{p}}(0):=\max\{\overline{N}\!\left(U\right):U\subseteq V_1',\;|U|=m_1\}, \qquad |\widehat{\mathrm{p}}(0)-\mathrm{p}(0)|\le 3L_{\mathrm{p}}\rho_\circ\le r,\] where the last inequality follows from the definition of \(\rho_\circ\), the range assumption, and the lower bound on \(K_\star\). The same proposition also gives the candidate family \[\mathcal{C}_{\rho_\circ}:= \{U\subseteq V_1':\;|U|=m_1,\;\overline{N}\!\left(U\right)\ge \widehat{\mathrm{p}}(0)-4L_{\mathrm{p}}\rho_\circ\}.\]

We now select a refinement net from \(\mathcal{C}_{\rho_\circ}\). Apply Proposition 38 in the appropriate route with \(K=K_\star\). The range assumption and the lower bound on \(K_\star\) imply that \[\rho_\circ\le \min\{r_\mu,r_\mathrm{p}/C_*\}, \qquad K_\star^3r \le \min\{1,r_\mathrm{p}\}.\] In the Oracle Route case, the theorem assumes \[\rho_\circ\le \frac{\alpha_{\mathrm{win}}}{2}r_\mathrm{p},\] and \[K_\star\rho_\circ\le r.\] In the Local Route case, \[K_\star\sqrt{\rho_\circ}\le r.\] Thus the hypotheses of Proposition 38 hold with \(r_{\rm ref}=r\). This gives a refinement net \[\mathfrak N=\{(U,\theta_U):U\in\mathcal{N}\}\] with threshold \[\Theta_2= \widehat{\mathrm{p}}(0)-A_{\text{\tiny{\ref{prop:link-average-separation}}}}r\] and parameters \[\begin{gather} \Theta= \widehat{\mathrm{p}}(0)-A_{\text{\tiny{\ref{prop:link-average-separation}}}}r,\qquad R_{\rm net}=r_{\rm net},\qquad R_{\rm in}=r_1,\\ R_{\rm out}=r_2,\qquad \gamma=r_1,\qquad M_{\rm net}=n_1. \end{gather}\] ◻

Proof. For the first refinement, 7 gives \[\frac{\Lambda\log n}{n_2} \le \frac{\mathsf{s}}{C_{\rm ext}}\phi(r_1/3)r_1^2.\] Since \(\mathsf{s}\le1\), \(r_1\le1\), and \(r_1\le r_2\), increasing \(C_{\rm ext}\) gives \[\begin{align} \label{eq:first-refinement-failure-budget-check} \Lambda\log n &\le c_{\text{\tiny{\ref{prop:readable-simultaneous-refinement}}}} r_2\phi(r_1/3)n_2. \end{align}\tag{8}\] Also, 6 , the identity \(m_1=\lfloor \phi(\rho_\circ/3)n_1/2\rfloor\), and the relation \(\rho_\circ\le r_1\) imply, after increasing \(C_{\rm ext}\) again, that \[\begin{align} \label{eq:first-refinement-approx-concentration-check} \mathsf{s}m_1\min\{r_1^2,1\} &\ge C_{\text{\tiny{\ref{prop:readable-simultaneous-refinement}}}} \log\!\left(\frac{e}{r_2\phi(r_1/3)}\right). \end{align}\tag{9}\] The range assumption gives \(r_2\le1\). Thus 8 and 9 verify the conditions ?? and ?? from [prop:simultaneous-refinement-net], respectively, for \[R_{\rm in}=r_1,\qquad R_{\rm out}=r_2,\qquad \gamma=r_1, \qquad n_\star=n_2.\] On \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(V_2',r_1)}\hypersetup{linkcolor=blue}\), Proposition [prop:simultaneous-refinement-net], applied to \(\mathfrak N\) with \(L_{\rm fail}=\Lambda\log n\), gives for every \(U\in\mathcal{N}\) a set \(U^{(2)}\subseteq V_2'\) with \[|U^{(2)}|\ge \frac{\phi(r_1/3)}{4} n_2\] which is an \((r_2,r_2)\)-cluster with center \(\theta_U\). The event \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(V_2',r_1)}\hypersetup{linkcolor=blue}\) holds with probability \(1-n_2^{-c\Lambda}\), and the simultaneous refinement failure is at most \(n_1\exp(-\Lambda\log n)\), which is harmless once \(\Lambda\ge\Lambda_0\).

For the second refinement, set \[m_2:=\frac{\phi(r_1/3)}{4} n_2.\] Each \(U^{(2)}\) has size at least \(m_2\), and is an \((r_2,r_2)\)-cluster with center \(\theta_U\). Since \(K_\star/2\ge K_{\text{\tiny{\ref{prop:candidate-refinement-net}}}}\), the parameter \(K_\star/2\) is admissible in Proposition 31. Proposition 31, in the Local Route case, applied with \(r=r_2\) and \(K=K_\star/2\), gives the common threshold \[\Theta_3:= \widehat{\mathrm{p}}(0)- A_{\text{\tiny{\ref{prop:link-average-separation}}}}r_2\] such that \[\mathfrak N^{(2)} := \{(U^{(2)},\theta_U):U\in\mathcal{N}\}\] is a refinement net with parameters \[\begin{gather} \Theta=\Theta_3,\qquad R_{\rm net}=r_{\rm net},\qquad R_{\rm in}=r_2,\\ R_{\rm out}=r_3,\qquad \gamma=r_2,\qquad M_{\rm net}=n_1. \end{gather}\] The range assumption ?? from 42 ensures the local-window condition \[\tfrac12K_\star r_2=r_3 \le \frac{1}{2}\min\{1,r_\mathrm{p}\},\] which in particular gives \(r_3\le1\), and the condition \[|\widehat{\mathrm{p}}(0)-\mathrm{p}(0)|\le 3L_\mathrm{p}\rho_\circ\le r_2\] needed to apply that proposition.

7 and the definition of \(m_2\) imply \[\mathsf{s}m_2\min\{r_2^2,1\} \ge C_{\text{\tiny{\ref{prop:readable-simultaneous-refinement}}}} \bigl(\Lambda\log n+\log n\bigr),\] after increasing \(C_{\rm ext}\) and \(\Lambda_0\), since \(r_2=K_\star r_1\) and \(\Lambda\ge\Lambda_0\). This verifies the exact-concentration condition ?? from [prop:simultaneous-refinement-net]. It also verifies the approximate-concentration condition ?? from [prop:simultaneous-refinement-net]: indeed, 7 , \(n_2\le n\), and \(\phi(r_1/3)\le\phi(r_2/3)\) imply, after adjusting constants, that \[r_3\phi(r_2/3)\ge n^{-1} \quad \Rightarrow \quad \log\!\left(\frac{e}{r_3\phi(r_2/3)}\right) \le 2\log n.\] Finally, because \(n_2\le n\), 7 gives \[\frac{\Lambda\log n}{n} \le \frac{\Lambda\log n}{n_2} \le \frac{\mathsf{s}}{C_{\rm ext}}\phi(r_1/3)r_1^2.\] Using \(\phi(r_1/3)\le\phi(r_2/3)\) and \(r_1^2\le r_3\), and increasing \(C_{\rm ext}\) again, we get \[\Lambda\log n \le c_{\text{\tiny{\ref{prop:readable-simultaneous-refinement}}}} r_3\phi(r_2/3)n.\] This verifies the failure-budget condition ?? from [prop:simultaneous-refinement-net]. Hence all three conditions ?? , ?? , and ?? from [prop:simultaneous-refinement-net] hold for \[R_{\rm in}=r_2,\qquad R_{\rm out}=r_3,\qquad \gamma=r_2,\qquad n_\star=n.\] Therefore the exact-inclusion clause of Proposition [prop:simultaneous-refinement-net], applied to \(\mathfrak N^{(2)}\) on \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(V_3,r_2)}\hypersetup{linkcolor=blue}\) with \(L_{\rm fail}=\Lambda\log n\), gives \[V_3\cap B(\theta_U,r_2) \subseteq U^{(3)} \subseteq V_3\cap B(\theta_U,r_3).\] The occupancy event \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(V_3,r_2)}\hypersetup{linkcolor=blue}\) holds with probability \(1-n^{-c\Lambda}\), and the remaining failures are absorbed by the same union bound over the seed family. ◻

Proof of Theorem 42. Choose \(r_1,r_2,r_{\rm net},r_3\) as above and \(n_1,n_2\) by 6 –7 . Apply Lemma 13 on \(V_1'\) to obtain \(\widehat{\mathrm{p}}(0)\), the threshold \(\Theta_2\), and a refinement net \(\mathfrak N\). Then apply Lemma 14 to refine every selected seed first into \(V_2'\) and then into \(V_3\).

For each \(v\in V_3\), choose \(U\in\mathcal{N}\) with \[{\rm d}({X_v},{\theta_U})\le r_{\rm net}<r_2,\] and set \(U_v:=U^{(3)}\). The exact inclusion from Lemma 14 gives \(v\in U_v\), while \[U_v\subseteq B(\theta_U,r_3) \subseteq B(X_v,r_{\rm net}+r_3) \subseteq B(X_v,K_\star^2r).\] On \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(V_3,r_2)}\hypersetup{linkcolor=blue}\), \[|U_v| \ge |V_3\cap B(\theta_U,r_2)| \ge \frac{\phi(r_2/3)}{2}n \ge \frac{\phi(r)}{2}n.\] The estimate for \(\mathrm{p}(0)\) was produced in the first-block step. The number of distinct output sets is bounded by \(|\mathcal{N}|\le n_1\le\binom{n_1}{m_1}\), and the entropy bound in the running-time remark gives the stated estimate. The probability bound follows from the union bound over the first-block event, the two occupancy events, and the two refinement rounds. ◻

Proof. See Appendix 11. ◻

Proof. Set \[r_0:=\sqrt r.\] Fix once and for all an admissible value \[K_\star\ge\max\{3,2K_{\text{\tiny{\ref{prop:candidate-refinement-net}}}}\}\] depending only on the model parameters, and use it for both applications of Theorem 42. All constants below are allowed to depend on this fixed \(K_\star\), hence only on the model parameters.

Round 1: coarse local-route extraction.  Apply Theorem 42 in the local route to \(V_1,V_2,V_3\) at target scale \(r_0\). The internal-average scale in that run is \[\rho_\circ = K_\star^{-2}r_0^2 = K_\star^{-2}r.\] After decreasing \(c_{\text{\tiny{\ref{thm:two-round-extraction}}}}\) and increasing \(C_{\text{\tiny{\ref{thm:two-round-extraction}}}}\), the assumptions ?? and ?? imply the range and scale conditions of Theorem 42 for this local run. Thus, with probability \(1-o(1)\), it outputs \(\widehat{\mathrm{p}}_{\rm coarse}(0)\) and sets \(A_z\subseteq V_3\) such that, for every \(z\in V_3\), \[z\in A_z, \qquad A_z\text{ is a }(K_\star^2r_0,0)\text{-cluster with center }X_z, \qquad |A_z|\ge \frac{1}{2}\phi(r_0)n, \qquad |\widehat{\mathrm{p}}_{\rm coarse}(0)-\mathrm{p}(0)| \le r_0.\]

Construct the fuzzy window oracle.  Set \(C_0:=K_\star^2\) and choose any fixed \(c_0\le1\). The event \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(V_3,C_0r_0)}\hypersetup{linkcolor=blue}\) also holds with probability \(1-o(1)\), by Lemma 2. Indeed, after decreasing \(c_{\text{\tiny{\ref{thm:two-round-extraction}}}}\), the radius \(C_0r_0\) is in range and \(\phi(C_0r_0)\ge \phi(c_{\text{\tiny{\ref{thm:two-round-extraction}}}}r)\); then ?? , together with \(\mathsf{s}r^2\le1\), gives the needed occupancy lower bound. Hence the centers \(\{X_z:z\in V_3\}\) form a \(C_0r_0\)-net of \(M\).

The scale requirements in Lemma 15 are checked in the same way. The bound \(r_0\le c_{\mathrm{ora}}r_\mathrm{p}\) follows from ?? . For the concentration requirement, decrease \(c_{\text{\tiny{\ref{thm:two-round-extraction}}}}\) so that \(\phi(c_0r_0)\ge \phi(c_{\text{\tiny{\ref{thm:two-round-extraction}}}}r)\). Since ?? gives \(r_\mathrm{p}^2\gtrsim r_0^2=r\ge r^2\), ?? implies \[\mathsf{s}n\phi(c_0r_0)r_\mathrm{p}^2\ge C_{\mathrm{ora}}\Lambda\log n\] after increasing \(C_{\text{\tiny{\ref{thm:two-round-extraction}}}}\). Applying the lemma with \(V_0=V_3\), \(W=V_4\), and coarse scale \(r_0\), we obtain a fuzzy window oracle \(\mathcal{O}_{\mathrm{win}}\) on \(V_4\), with fixed margins \[\alpha_{\mathrm{win}}:=\frac{\ell_\mathrm{p}}{128L_\mathrm{p}}, \qquad \lambda_{\mathrm{win}}:=\frac{1}{8}.\]

Round 2: fine oracle extraction.  Apply Theorem 42 in the oracle route to \(V_4,V_5,V_6\) at target scale \(r\), using this oracle on \(V_4\). The internal-average scale is \[\rho_\circ=K_\star^{-1}r.\] The range condition of Theorem 42 follows from ?? , since \(r\le r_0\). Its scale condition follows from ?? after decreasing \(c_{\text{\tiny{\ref{thm:two-round-extraction}}}}\), because then \(\phi(\rho_\circ/3)\ge \phi(c_{\text{\tiny{\ref{thm:two-round-extraction}}}}r)\) and \(\rho_\circ^2=K_\star^{-2}r^2\). Therefore, with probability \(1-o(1)\), the fine run outputs an estimator \(\widehat{\mathrm{p}}(0)\) and, for every \(v\in V_6\), a set \(U_v\subseteq V_6\) satisfying \[v\in U_v, \qquad U_v \text{ is a }(K_\star^2 r,0)\text{-cluster with center }X_v,\] \[|U_v|\ge \frac{1}{2}\phi(r)n, \qquad |\widehat{\mathrm{p}}(0)-\mathrm{p}(0)|\le r.\] Taking \(C'_{\text{\tiny{\ref{thm:two-round-extraction}}}}\ge K_\star^2\) gives the stated cluster-radius form. The running time and the number of distinct sets are the sum of the two three-block costs and the oracle-construction cost, computed over the distinct coarse clusters. Since the coarse run has internal scale comparable to \(r\), and the fine run has internal scale comparable to \(r\), while \(r\le r_0\le1\), these costs are absorbed into the complexity stated in the theorem.

Probability and independence.  The first coarse extraction, the occupancy event on \(V_3\), the oracle construction using edges from \(V_3\) to \(V_4\), and the final oracle extraction each fail with probability \(o(1)\). The edge sets used in these steps are disjoint: the oracle uses \(V_3\)-to-\(V_4\) edges, while the fine oracle extraction uses internal \(V_4\) edges, then \(V_4\)-to-\(V_5\) edges, and finally \(V_5\)-to-\(V_6\) edges. Thus the conditional concentration arguments from the three-block theorem apply without interference. A union bound gives total success probability \(1-o(1)\). ◻

Proof. We may assume \(c_{\text{\tiny{\ref{thm:two-round-extraction}}}}\le1\), and set \[\bar r:=r/c_{\text{\tiny{\ref{thm:two-round-extraction}}}}.\] Split \(\mathbf{V}\) into six blocks of sizes differing by at most one. Apply Theorem 45 six times, cyclically permuting the blocks so that each block is used once as the output block \(V_6\), and use target scale \(\bar r\) in each run. The assumptions of Theorem 45 follow from the assumptions of this theorem after decreasing \(c_{\text{\tiny{\ref{theor:main}}}}\) and increasing \(C_{\text{\tiny{\ref{theor:main}}}}\): indeed \[c_{\text{\tiny{\ref{thm:two-round-extraction}}}}\bar r=r,\] so the scale condition there is exactly the main scale condition, up to the constant change.

The six success events have total failure probability \(o(1)\). The runtime of each call is bounded by the displayed main-theorem runtime because \(c_{\text{\tiny{\ref{thm:two-round-extraction}}}}\bar r=r\), \(\bar r\ge r\), and the factor \(\bar r^{-2}\) differs from \(r^{-2}\) only by a model-dependent constant. The same comparison applies to the number of distinct output sets.

For a vertex in an output block of size at least \(n/6-1\), Theorem 45 gives a cluster of size at least \[\frac{1}{2}\phi(\bar r)(n/6-1) \ge \frac{1}{13}\phi(r)n\] for all large \(n\), after increasing constants if necessary, since \(\bar r\ge r\) and \(\phi\) is nondecreasing. The cluster radius and estimator error are \(O(\bar r)=O(r)\), so they are absorbed into \(C'_{\text{\tiny{\ref{theor:main}}}}r\). Use the estimator from any one of the six runs. ◻

Proof of Lemma 1. Set \(\alpha=\phi(r_0)\), and consider the three-point metric space \[M=\{a,b,c\},\qquad {\rm d}(x,y)=r_0\quad (x\neq y),\] with \[\mu(a)=\mu(b)=\alpha,\qquad \mu(c)=1-2\alpha.\] For \(0<t\le r_0\), each ball \(B(x,t)\) is a singleton, hence has mass at least \(\alpha=\phi(r_0)\ge \phi(t)\). Thus this space is lower-\(\phi\)-regular up to scale \(r_0\).

We use a simple Bernoulli observation model on this space. Fix a sufficiently small universal constant \(\gamma>0\), keep the sparsity parameter \(\mathsf{s}\), and define a non-increasing link by \[\mathrm{p}(t)=\frac{1}{2}+\frac{\gamma r_0}{2}-\gamma\min\{t,r_0\}.\] Since \(r_0\le1\) and \(\gamma\) is small, \(\mathrm{p}\) takes values in \((0,1)\). It is locally bi-Lipschitz on \([0,r_0]\), and the Bernoulli graph model is obtained from Definition 8 by taking \[\mathbf{F}(t,u)={\boldsymbol{1}}\{u\le \mathrm{p}(t)\}.\] Write \[p_0=\mathsf{s}\mathrm{p}(0),\qquad p_1=\mathsf{s}\mathrm{p}(r_0),\] and \[\mathcal{I} = \max\{\operatorname{kl}(p_0,p_1),\operatorname{kl}(p_1,p_0)\},\] where \(\operatorname{kl}\) is the Bernoulli relative entropy. Since \(\mathrm{p}(0),\mathrm{p}(r_0)\in[1/4,3/4]\) and \(|\mathrm{p}(0)-\mathrm{p}(r_0)|=\gamma r_0\), the elementary Taylor bound for Bernoulli relative entropy gives \[\mathcal{I}\le C\mathsf{s} r_0^2\] for a universal constant \(C\). Let \[I=\{i:X_i\in\{a,b\}\}.\] Then \(|I|\sim{\rm Binomial}(n,2\alpha)\). Put \[m=\lceil 3n\alpha\rceil,\qquad \mathcal{E}=\{2\le |I|\le m\}.\] There is a universal \(C_0\) such that, whenever \(n\alpha\ge C_0\), \[\mathbb{P}(\mathcal{E})\ge \frac{3}{4}.\] This is the standard binomial lower-tail and upper-tail estimate, since \(\mathbb{E}|I|=2n\alpha\).

We now work on \(\mathcal{E}\). Choose \(i_\star\) uniformly from \(I\), and let \(X'\) be obtained from \(X\) by changing only \(X_{i_\star}\), swapping \(a\) and \(b\). For fixed \(X=x\), write \(x'\) for the swapped configuration, and let \(P_x,P_{x'}\) be the corresponding conditional laws of the observed graph.

Only edges from \(i_\star\) to \(I\setminus\{i_\star\}\) can change. There are at most \(m\) such edges, and each affected coordinate changes between Bernoulli\((p_0)\) and Bernoulli\((p_1)\), in one direction or the other. Therefore the product relative entropy is at most \(m\mathcal{I}\), and Pinsker’s inequality gives \[{\rm TV}(P_x,P_{x'}) \le \sqrt{\frac{m\mathcal{I}}{2}}.\]

The two latent distance matrices are separated in sup norm by \(r_0\). Indeed, because \(|I|\ge2\), there is \(j\in I\setminus\{i_\star\}\), and the swap changes the distance between \(i_\star\) and \(j\) from \(0\) to \(r_0\), or from \(r_0\) to \(0\). Hence no estimator output can be within \(r_0/2\) of both distance matrices.

Let \(A_x\) be the event that an estimator is within error \(<r_0/2\) of the distance matrix generated by \(x\), and define \(A_{x'}\) similarly. Then \(A_x\cap A_{x'}=\varnothing\), so \[P_x(A_x)+P_{x'}(A_{x'}) \le 1+{\rm TV}(P_x,P_{x'}) \le 1+\sqrt{\frac{m\mathcal{I}}{2}}.\] The random swap preserves the conditional law of the latent sample on \(\mathcal{E}\), because the two small atoms have the same mass and the swap kernel is reversible. Averaging the last display over \(X\) and \(i_\star\) therefore shows that the conditional success probability of any estimator is at most \[\frac{1}{2}\left(1+\sqrt{\frac{m\mathcal{I}}{2}}\right).\] Removing the conditioning gives \[\mathbb{P}\!\left( \max_{u,v}|\widehat d(u,v)-{\rm d}({X_u},{X_v})|\ge r_0/2 \right) \ge \frac{\mathbb{P}(\mathcal{E})}{2} \left(1-\sqrt{\frac{m\mathcal{I}}{2}}\right)_+ .\]

After increasing \(C_0\) if necessary, \(m\le4n\alpha\). Thus, if \[\mathsf{s}n\alpha r_0^2\le c_0\] for a sufficiently small universal \(c_0\), then \(m\mathcal{I}\) is smaller than a universal constant. The last display is therefore bounded below by a universal constant \(c_1>0\). This proves the probability lower bound; the expectation lower bound follows by multiplying this event by \(r_0/2\). ◻

Proof of Lemma 15. Set \[m_0:=\frac{1}{2}\phi(c_0r)n, \qquad \varepsilon_{\rm link}:= \sqrt{\frac{\Lambda\log n}{\mathsf{s}m_0}}.\] The assumption \[\mathsf{s}n\phi(c_0r)r_\mathrm{p}^2\ge C_{\mathrm{ora}}\Lambda\log n\] implies, after increasing \(C_{\mathrm{ora}}\), that \[\varepsilon_{\rm link}\le c_{\mathrm{ora}}r_\mathrm{p}.\] By Lemma 3, a union bound over \(|V_0||W|\le n^2\) gives, with conditional probability \(1-n^{-\Omega(\Lambda)}\), \[\left|\hypersetup{linkcolor=black}\hyperref[eq:def-normalized-average]{{\rm N}_{A_z}(v)}\hypersetup{linkcolor=blue}-\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{A_z}(v)}\hypersetup{linkcolor=blue}\right| \le \varepsilon_{\rm link} \qquad (z\in V_0,\;v\in W).\] We work on this event.

We first record the deterministic inclusions \[\left\{ v\in W: {\rm d}({X_v},{X_z})\le \frac{\ell_\mathrm{p}}{64L_\mathrm{p}}r_\mathrm{p} \right\} \subseteq W_z \subseteq \left\{ v\in W: {\rm d}({X_v},{X_z})<\frac{1}{16}r_\mathrm{p} \right\} \qquad (z\in V_0).\] Fix \(z\in V_0\). Since \(A_z\) is a \((C_0r,0)\)-cluster with center \(X_z\), every \(u\in A_z\) satisfies \({\rm d}({X_u},{X_z})<C_0r\). If \[{\rm d}({X_v},{X_z})\le \frac{\ell_\mathrm{p}}{64L_\mathrm{p}}r_\mathrm{p},\] then, after taking \(c_{\mathrm{ora}}\) small enough, all distances \({\rm d}({X_u},{X_v})\) lie in the local bi-Lipschitz window and \[\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{A_z}(v)}\hypersetup{linkcolor=blue} \ge \mathrm{p}(0)-L_\mathrm{p}C_0r-\frac{\ell_\mathrm{p}}{64}r_\mathrm{p}.\] Using \(|\widehat{\mathrm{p}}(0)-\mathrm{p}(0)|\le C_0r\) and the concentration event, \[\hypersetup{linkcolor=black}\hyperref[eq:def-normalized-average]{{\rm N}_{A_z}(v)}\hypersetup{linkcolor=blue} \ge \widehat{\mathrm{p}}(0) -(L_\mathrm{p}C_0+C_0)r-\varepsilon_{\rm link} -\frac{\ell_\mathrm{p}}{64}r_\mathrm{p}.\] The choices of \(c_{\mathrm{ora}}\) and \(C_{\mathrm{ora}}\) ensure that the last three error terms are at most \(\ell_\mathrm{p}r_\mathrm{p}/32\), so \(v\in W_z\).

Conversely, if \[{\rm d}({X_v},{X_z})\ge \frac{1}{16}r_\mathrm{p},\] then, again taking \(c_{\mathrm{ora}}\) small enough, \[0< \frac{1}{16}r_\mathrm{p}-C_0r \le r_\mathrm{p}.\] For every \(u\in A_z\), monotonicity and the lower local bi-Lipschitz bound give \[\mathrm{p}({\rm d}({X_u},{X_v})) \le \mathrm{p}(0) - \ell_\mathrm{p}\left(\frac{1}{16}r_\mathrm{p}-C_0r\right).\] Averaging and using the estimator and concentration errors, \[\hypersetup{linkcolor=black}\hyperref[eq:def-normalized-average]{{\rm N}_{A_z}(v)}\hypersetup{linkcolor=blue} \le \widehat{\mathrm{p}}(0) -\frac{\ell_\mathrm{p}}{16}r_\mathrm{p} +(\ell_\mathrm{p}C_0+C_0)r+\varepsilon_{\rm link}.\] With \(c_{\mathrm{ora}}\) small and \(C_{\mathrm{ora}}\) large, the final two error terms are at most \(\ell_\mathrm{p}r_\mathrm{p}/64\), and hence \[\hypersetup{linkcolor=black}\hyperref[eq:def-normalized-average]{{\rm N}_{A_z}(v)}\hypersetup{linkcolor=blue} < \widehat{\mathrm{p}}(0)-\frac{\ell_\mathrm{p}}{32}r_\mathrm{p}.\] Thus \(v\notin W_z\), proving the displayed inclusions.

We now verify the fuzzy-oracle property. If \(\mathcal{O}_{\mathrm{win}}(v,w)=1\), then there is \(z\in V_0\) with \(v,w\in W_z\). The outer inclusion gives \[{\rm d}({X_v},{X_z})<\frac{1}{16}r_\mathrm{p}, \qquad {\rm d}({X_w},{X_z})<\frac{1}{16}r_\mathrm{p},\] so \({\rm d}({X_v},{X_w})<r_\mathrm{p}/8=\lambda_{\mathrm{win}}r_\mathrm{p}\). Therefore \[{\rm d}({X_v},{X_w})>\lambda_{\mathrm{win}}r_\mathrm{p} \quad\Longrightarrow\quad \mathcal{O}_{\mathrm{win}}(v,w)=0.\]

Conversely, suppose \[{\rm d}({X_v},{X_w})\le \alpha_{\mathrm{win}}r_\mathrm{p} = \frac{\ell_\mathrm{p}}{128L_\mathrm{p}}r_\mathrm{p}.\] Choose \(z\in V_0\) with \({\rm d}({X_v},{X_z})\le C_0r\), using the \(C_0r\)-net assumption. For \(c_{\mathrm{ora}}\) small enough, \[C_0r\le \frac{\ell_\mathrm{p}}{128L_\mathrm{p}}r_\mathrm{p},\] and hence \[{\rm d}({X_v},{X_z})\le \frac{\ell_\mathrm{p}}{64L_\mathrm{p}}r_\mathrm{p}, \qquad {\rm d}({X_w},{X_z})\le \frac{\ell_\mathrm{p}}{64L_\mathrm{p}}r_\mathrm{p}.\] The inner inclusion gives \(v,w\in W_z\), so \(\mathcal{O}_{\mathrm{win}}(v,w)=1\). This proves that \(\mathcal{O}_{\mathrm{win}}\) is an \(\bigl(\ell_\mathrm{p}/(128L_\mathrm{p}),1/8\bigr)\)-fuzzy window oracle. ◻

Proof. Fix \(v,w\in W\), and set \[d_{vw}:={\rm d}({X_v},{X_w}).\] For every \((u,u')\in\mathcal{D}(U_v,U_w)\), the triangle inequality gives \[\left| {\rm d}({X_u},{X_{u'}})-d_{vw} \right| \le {\rm d}({X_u},{X_v})+{\rm d}({X_{u'}},{X_w}) < 2r_{\rm cl}.\] If \(d_{vw}+2r_{\rm cl}\le r_\mathrm{p}\), then all these distances lie in the local bi-Lipschitz window. Hence the local Lipschitz bound gives \[\left| \mathrm{p}({\rm d}({X_u},{X_{u'}}))-\mathrm{p}(d_{vw}) \right| \le 2L_\mathrm{p}r_{\rm cl}.\] Averaging over \(\mathcal{D}(U_v,U_w)\), we obtain \[\left| \overline{\mathrm{p}}\!\left(U_v,U_w\right) - \mathrm{p}(d_{vw}) \right| \le 2L_\mathrm{p}r_{\rm cl}.\] On \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(W,\lambda,m)}\hypersetup{linkcolor=blue}\), \[\left| \overline{N}\!\left(U_v,U_w\right)-\overline{\mathrm{p}}\!\left(U_v,U_w\right) \right| \le \lambda.\] Combining the two inequalities proves the claim. In the globally Lipschitz case, the same argument applies without the restriction \(d_{vw}+2r_{\rm cl}\le r_\mathrm{p}\). ◻

Proof. Work on the event where Theorem 47 holds and where \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(\mathbf{V},r,m_{\rm pair})}\hypersetup{linkcolor=blue}\) holds. Then every output cluster satisfies \[U_v\text{ is a }(C_{\text{\tiny{\ref{theor:main}}}}'r,0)\text{-cluster with center }X_v,\] and \[|U_v|\ge m_{\rm pair}.\] Applying Lemma 16 with \[r_{\rm cl}=C_{\text{\tiny{\ref{theor:main}}}}'r, \qquad \lambda=r,\] gives \[\left| \overline{N}\!\left(U_v,U_w\right) - \mathrm{p}({\rm d}({X_v},{X_w})) \right| \le C r \qquad (v,w\in\mathbf{V}).\] Since \(\mathrm{p}\) is known and globally bi-Lipschitz, its inverse is \(1/\ell_\mathrm{p}\)-Lipschitz on its range. Define \(\widehat d(v,w)\) by projecting \(\overline{N}\!\left(U_v,U_w\right)\) onto \(\mathrm{p}([0,\operatorname{diam}(M)])\) and then applying \(\mathrm{p}^{-1}\). Projection can only decrease the error to the range, and inversion gives the stated bound. ◻

Proof. Again work on the intersection of the extraction event and \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(\mathbf{V},r,m_{\rm pair})}\hypersetup{linkcolor=blue}\). Set \[r_{\rm cl}:=C'_{\text{\tiny{\ref{theor:main}}}}r, \qquad \varepsilon_{\rm pair}:=2L_\mathrm{p}r_{\rm cl}+r.\] By decreasing \(c_{\text{\tiny{\ref{theor:main}}}}\), we may assume \[2r_{\rm cl}+\frac{2\varepsilon_{\rm pair}}{\ell_\mathrm{p}} \le \frac{1}{4} r_\mathrm{p}.\] Define \[\mathcal{P}_{\mathrm{loc}} := \left\{ (v,w):v\neq w,\; \overline{N}\!\left(U_v,U_w\right) \ge \mathrm{p}(r_\mathrm{p}/2)-\varepsilon_{\rm pair} \right\}.\] For \((v,w)\in\mathcal{P}_{\mathrm{loc}}\), first note that \[{\rm d}({X_v},{X_w}) \le \frac{1}{2} r_\mathrm{p}+\frac{2\varepsilon_{\rm pair}}{\ell_\mathrm{p}}.\] Indeed, if the distance were larger, then every pair \((u,u')\in\mathcal{D}(U_v,U_w)\) would have distance at least slightly above \(r_\mathrm{p}/2\), and the lower bi-Lipschitz bound together with \(\hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(\mathbf{V},r,m_{\rm pair})}\hypersetup{linkcolor=blue}\) would force \[\overline{N}\!\left(U_v,U_w\right)<\mathrm{p}(r_\mathrm{p}/2)-\varepsilon_{\rm pair},\] a contradiction. Thus \[{\rm d}({X_v},{X_w})+2r_{\rm cl}\le r_\mathrm{p},\] and Lemma 16 applies: \[\left| \overline{N}\!\left(U_v,U_w\right) - \mathrm{p}({\rm d}({X_v},{X_w})) \right| \le \varepsilon_{\rm pair}.\] Project \(\overline{N}\!\left(U_v,U_w\right)\) onto \(\mathrm{p}([0,r_\mathrm{p}])\) and invert \(\mathrm{p}\) on \([0,r_\mathrm{p}]\). Since the inverse is \(1/\ell_\mathrm{p}\)-Lipschitz, the distance error is at most \[\frac{\varepsilon_{\rm pair}}{\ell_\mathrm{p}} \le Cr.\]

Finally, if \[{\rm d}({X_v},{X_w})\le r_\mathrm{p}/2,\] then the same pair-average estimate gives \[\overline{N}\!\left(U_v,U_w\right) \ge \mathrm{p}({\rm d}({X_v},{X_w}))-\varepsilon_{\rm pair} \ge \mathrm{p}(r_\mathrm{p}/2)-\varepsilon_{\rm pair},\] so \((v,w)\in\mathcal{P}_{\mathrm{loc}}\). This proves the claim. ◻

Proof. This is the standard shortest-path extension from local metric estimates; see [12]. The added \(\varepsilon\) in each edge weight makes every edge length an upper bound on the true distance, while the chain property supplies a path whose accumulated local errors are controlled by \({\rm diam}(\mathcal{X})/\rho_0\). ◻

Proof. One thing that is subtle besides directly applying the above lemma together with Corollary 49 is to justify that the sampled points \(X_{\mathbf{V}}\) also have the chain property. This is implied by \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(\mathbf{V},()}\hypersetup{linkcolor=blue}r)\), which holds with high probability under the scale condition of Theorem 47, after adjusting constants. This automatically implies the chain property for the sampled points with \(\eta\) increased by \(C\tfrac{{\rm diam}(M)}{r_\mathrm{p}} r\), because every point along the chain has a sampled point within distance \(r\). ◻

Proof. Maximality gives the net property: otherwise a point at distance \(>\delta\) from all points of \(\mathcal{N}\) could be added to \(\mathcal{N}\). If \(\mathcal{N}=\{x_1,\ldots,x_N\}\), then the balls \(B(x_i,\delta/2)\) are pairwise disjoint. Hence \[1=\mu(M) \ge \sum_{i=1}^N \mu(B(x_i,\delta/2)) \ge N\phi(\delta/2),\] which proves the cardinality bound. ◻

Proof of Lemma 2. Let \(\mathcal{N}\) be a maximal \(r/3\)-separated set. By Lemma 20, \[|\mathcal{N}|\le \frac{1}{\phi(r/6)}.\] For \(x_i\in\mathcal{N}\), let \[S_i:=|\{v\in W:X_v\in B(x_i,r/3)\}|.\] Then \(S_i\) is binomial with mean at least \(n_\star\phi(r/3)\). The lower Chernoff bound gives \[\mathbb{P}\left(S_i<\frac{1}{2} n_\star\phi(r/3)\right) \le \exp\left(-\frac{n_\star\phi(r/3)}{8}\right).\] Taking a union bound over \(\mathcal{N}\) and using \(\phi(r/3)\ge\phi(r/6)\ge \Lambda \log n_\star/n_\star\), we get \[\begin{align} \mathbb{P}\left( \exists x_i\in\mathcal{N}:S_i<\frac{1}{2} n_\star\phi(r/3) \right) \le& \frac{1}{\phi(r/6)} \exp\left(-\frac{n_\star\phi(r/3)}{8}\right) \\ \le & \frac{n_\star}{\Lambda\log n_\star} \exp\left(-\frac{\Lambda}{8}\log(n_\star)\right)\\ \le & \exp\left( \log(n_\star) - \tfrac{1}{8}\Lambda \log(n_\star) \right) \le \exp\left(-\frac{\Lambda}{16}\log(n_\star)\right)\,, \end{align}\] provided \(\Lambda\) is large enough than some universal constant.

On the complementary event, fix \(x\in M\). Since \(\mathcal{N}\) is an \(r/3\)-net, choose \(x_i\in\mathcal{N}\) with \({\rm d}({x},{x_i})\le r/3\). Then \[B(x_i,r/3)\subseteq B(x,r),\] because the balls are open. Therefore \[|\{v\in W:X_v\in B(x,r)\}| \ge S_i \ge \frac{1}{2} n_\star\phi(r/3).\] This is exactly \(\hypersetup{linkcolor=black}\hyperref[eq:def-lower-occupancy-event]{\mathcal{E}_{\text{\tiny{\rm pt}}}(W,r)}\hypersetup{linkcolor=blue}\). ◻

Proof of Lemma 3. Fix \(X_U=x_U\) and \(X_v=x_v\), and write \(m:=|U|\), \[a_u:=\mathrm{p}({\rm d}({x_u},{x_v})), \qquad \xi_u:=\widetilde{Z}_{u,v}-a_u, \qquad B_u:=B_{u,v}.\] Then the \(B_u\)’s are independent Bernoulli\((\mathsf{s})\), the \(\xi_u\)’s are independent centered \({\rm K}_{\mathrm{sg}}\)-subgaussian variables, and these two families are independent. Also \(|a_u|\le M_\mathrm{p}\). Since \[Z_{u,v}=B_u(a_u+\xi_u),\] we have \[\hypersetup{linkcolor=black}\hyperref[eq:def-normalized-average]{{\rm N}_{U}(v)}\hypersetup{linkcolor=blue}-\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(v)}\hypersetup{linkcolor=blue} = \frac{1}{\mathsf{s}m}\sum_{u\in U}(Z_{u,v}-\mathsf{s}a_u) =T_1+T_2,\] where \[T_1:=\frac{1}{\mathsf{s}m}\sum_{u\in U}(B_u-\mathsf{s})a_u, \qquad T_2:=\frac{1}{\mathsf{s}m}\sum_{u\in U}B_u\xi_u.\]

For \(T_1\), set \(Y_u=(B_u-\mathsf{s})a_u\). Then the \(Y_u\)’s are independent, mean-zero, \(|Y_u|\le M_\mathrm{p}\), and \[\sum_{u\in U}\operatorname{Var}(Y_u)\le \mathsf{s}m M_\mathrm{p}^2.\] Bernstein’s inequality with \(s=t\mathsf{s}m/2\) gives \[\mathbb{P}\left(|T_1|>\frac{t}{2}\mid X_U=x_U,X_v=x_v\right) \le 2\exp\bigl(-c_1\mathsf{s}m\min\{t^2,1\}\bigr).\]

For \(T_2\), let \(N_B:=\sum_{u\in U}B_u\). By Chernoff, \[\mathbb{P}(N_B>2\mathsf{s}m\mid X_U=x_U,X_v=x_v) \le \exp(-c\mathsf{s}m).\] On the event \(N_B\le2\mathsf{s}m\), conditioning on the \(B_u\)’s, the sum \(\sum_u B_u\xi_u\) is subgaussian with parameter at most \({\rm K}_{\mathrm{sg}}\sqrt{2\mathsf{s}m}\). Thus, again with \(s=t\mathsf{s}m/2\), \[\mathbb{P}\left(|T_2|>\frac{t}{2}\mid X_U=x_U,X_v=x_v\right) \le 3\exp\bigl(-c_2\mathsf{s}m\min\{t^2,1\}\bigr).\] Combining the two bounds and adjusting constants proves the claim. ◻

Proof of Lemma 4. For each fixed \(v\in V\), Lemma 3 gives \[\mathbb{P}\left( \left|\hypersetup{linkcolor=black}\hyperref[eq:def-normalized-average]{{\rm N}_{U}(v)}\hypersetup{linkcolor=blue}-\hypersetup{linkcolor=black}\hyperref[def:latent-empirical-link-averages]{{\mathrm{p}}_{U}(v)}\hypersetup{linkcolor=blue}\right|>\hypersetup{linkcolor=black}\hyperref[eq:def-fluctuation-scale]{\varepsilon_{U}(n_\star)}\hypersetup{linkcolor=blue} \;\middle|\;X_U=x_U,\;X_V=x_V \right) \le C_{\rm link} \exp\left( -c_{\rm link}\mathsf{s}|U| \min\{\hypersetup{linkcolor=black}\hyperref[eq:def-fluctuation-scale]{\varepsilon_{U}(n_\star)}\hypersetup{linkcolor=blue}^2,1\} \right).\] Since \(\mathsf{s}|U|\ge \Lambda \log n_\star\), we have \(\hypersetup{linkcolor=black}\hyperref[eq:def-fluctuation-scale]{\varepsilon_{U}(n_\star)}\hypersetup{linkcolor=blue}\le1\), and the exponent is at most \(-c_{\rm link}\Lambda \log n_\star\). A union bound over \(|V|\le n_\star\) gives \[\mathbb{P}\left( \hypersetup{linkcolor=black}\hyperref[eq:def-navigation-event]{\mathcal{E}_{\rm link}(U,V;n_\star)}\hypersetup{linkcolor=blue}^{\,c} \;\middle|\;X_U=x_U,X_V=x_V \right) \le e^{- \tfrac{1}{2}c_{\rm link}\Lambda \log n_\star}\,,\] provided that \(\Lambda\) is larger than some universal constants depending on \(C_{\rm link}\) and \(c_{\rm link}\). ◻

Proof of Lemma 5. Fix a realization \(X_W=x_W\). Let \(U_1,U_2\subseteq W\) have \[|U_1|=a,\qquad |U_2|=b,\qquad a,b\ge m.\] For each unordered pair \(e=\{u,v\}\subseteq W\), define \[w_e:= \mathbf{1}_{\{u\in U_1,\;v\in U_2\}} + \mathbf{1}_{\{v\in U_1,\;u\in U_2\}}.\] Then \(w_e\in\{0,1,2\}\), and \[D:=\sum_{e\subseteq W}w_e =|U_1||U_2|-|U_1\cap U_2| =|\mathcal{D}(U_1,U_2)|.\] For \(e=\{u,v\}\), write \[a_e:=\mathrm{p}({\rm d}({x_u},{x_v})), \qquad \xi_e:=\widetilde{Z}_{u,v}-a_e, \qquad B_e:=B_{u,v}.\] As in the fixed-vertex proof, \[\overline{N}\!\left(U_1,U_2\right)-\overline{\mathrm{p}}\!\left(U_1,U_2\right) = \frac{1}{\mathsf{s}D}\sum_{e\subseteq W}w_e(Z_e-\mathsf{s}a_e) =T_1+T_2,\] where \[T_1:=\frac{1}{\mathsf{s}D}\sum_{e\subseteq W}w_e(B_e-\mathsf{s})a_e, \qquad T_2:=\frac{1}{\mathsf{s}D}\sum_{e\subseteq W}w_eB_e\xi_e.\]

For \(T_1\), set \(Y_e=w_e(B_e-\mathsf{s})a_e\). Then \[|Y_e|\le2M_\mathrm{p}, \qquad \sum_{e\subseteq W}\operatorname{Var}(Y_e) \le \mathsf{s}M_\mathrm{p}^2\sum_{e\subseteq W}w_e^2 \le 2\mathsf{s}D M_\mathrm{p}^2.\] Bernstein’s inequality with \(s=\lambda\mathsf{s}D/2\) gives \[\mathbb{P}\left(|T_1|>\frac{\lambda}{2}\mid X_W=x_W\right) \le 2\exp(-c_1\lambda^2\mathsf{s}D).\]

For \(T_2\), let \(W_B:=\sum_{e\subseteq W}w_eB_e\). Since \(\mathbb{E}[W_B\mid X_W=x_W]=\mathsf{s}D\) and \(0\le w_eB_e\le2\), Bernstein’s inequality gives \[\mathbb{P}(W_B>2\mathsf{s}D\mid X_W=x_W) \le \exp(-c_2\mathsf{s}D).\] On the event \(W_B\le2\mathsf{s}D\), conditioning on the \(B_e\)’s, \[\sum_{e\subseteq W}w_eB_e\xi_e\] is subgaussian with parameter at most \[{\rm K}_{\mathrm{sg}}\left(\sum_{e\subseteq W}w_e^2B_e\right)^{1/2} \le 2{\rm K}_{\mathrm{sg}}\sqrt{\mathsf{s}D}.\] Therefore \[\mathbb{P}\left(|T_2|>\frac{\lambda}{2}\mid X_W=x_W\right) \le 3\exp(-c_3\lambda^2\mathsf{s}D).\] Combining the two bounds, \[\mathbb{P}\left( \bigl|\overline{N}\!\left(U_1,U_2\right)-\overline{\mathrm{p}}\!\left(U_1,U_2\right)\bigr|>\lambda \;\middle|\;X_W=x_W \right) \le 4\exp(-c_4\lambda^2\mathsf{s}D).\]

It remains to union-bound over \(U_1,U_2\). Since \(m\ge2\), \[D=ab-|U_1\cap U_2|\ge ab-\min\{a,b\}\ge\frac{ab}{2}.\] For \(\alpha=a/n_\star\) and \(\beta=b/n_\star\), the number of pairs \((U_1,U_2)\) with these cardinalities is at most \[\binom{n_\star}{a}\binom{n_\star}{b} \le \exp\left((\alpha+\beta)n_\star\log(e/\varphi)\right),\] because \(\alpha,\beta\ge\varphi\). Also \(\alpha+\beta\le2\alpha\beta/\varphi\). Thus, if \[\mathsf{s}n_\star\ge \frac{C\log(e/\varphi)}{\varphi\lambda^2}\] with \(C\) large enough, then each cardinality class contributes at most \[4\exp(-c_5\lambda^2\mathsf{s}\alpha\beta n_\star^2).\] Summing over at most \(n_\star^2\) cardinality pairs and using \(\alpha\beta\ge\varphi^2\), we obtain \[\mathbb{P}\left( \hypersetup{linkcolor=black}\hyperref[eq:def-pair-average-event]{\mathcal{E}_{\text{\tiny{\rm avg}}}(W,\lambda,m)}\hypersetup{linkcolor=blue}^{\,c} \;\middle|\;X_W=x_W \right) \le 4n_\star^2 \exp(-c_5\lambda^2\mathsf{s}\varphi^2n_\star^2).\] The assumed lower bound on \(\mathsf{s}n_\star\), together with \(m\ge2\), implies that the right-hand side is at most \[\exp\{-c\varphi n_\star\log(e/\varphi)\}\] after increasing \(C\) and decreasing \(c\). This proves the lemma. ◻

High-probability consequence of Lemma 5. The failure probability in Lemma 5 is \[\exp\{-c\varphi n_\star\log(e/\varphi)\}.\] If \(\varphi n_\star\log(e/\varphi)\gg\log n_\star\), this is \(n_\star^{-\omega(1)}\). ◻