5 Gaussian labels and edge correlations
All sweeps of Part I order the vertices by random Gaussian labels and bound the sizes of the frontiers of the resulting order from above with the layout lemma (Lemma 4.1). This section constructs the labels and proves the two properties of them that the rest of Part I uses.
First, the labels of a vertex and of its neighbors form a star. For every vertex \(v\), the vector \((Y_v;Y_u)_{u\in N(v)}\) is a centered Gaussian vector with unit variances (Lemma 5.6), and its incident correlations \(\mathop{\mathrm{Corr}}(Y_v,Y_u)\) are bounded below by explicit constants that depend only on the degrees (Lemmas 5.4 and 5.5). When these constants are positive and \(v\) is not isolated, the vector is therefore a \(d(v)\)-star in the sense of Definition 6.1. The star bounds of Section 6 use nothing else about the labels. They allow arbitrary correlations between two neighbors of \(v\), so short cycles and triangles through \(v\) need no separate treatment.
Second, the labels are local and distinct. Each label depends only on the independent variables in a ball of bounded radius, which makes frontier sizes concentrate (Lemma 4.10). The labels are distinct with probability \(1\), as Lemma 4.1 requires. Both facts are part of Lemma 5.6.
Section 5.1 defines the labels and states the three lemmas, and Sections 5.2, 5.3, 5.4 and 5.5 prove them. The technical overview (Section 2.2) explains why the chosen decay rate is the right one.
Remark 5.1 (optimality for radial labels). On the infinite \(p\)-regular tree, the local limit of \(p\)-regular graphs of large girth, the adjacency operator has norm \(2\sqrt{p-1}\) (Kesten (Kesten 1959); (Woess 2000 Lemma 1.24)). Hence no Gaussian field \(X_v=\sum_wf(\mathop{\mathrm{dist}}(v,w))Z_w\) with radial weights has a neighbor correlation above \(\frac{2\sqrt{p-1}}p=r_{pp}\), since the \(p\) neighbor covariances of \(v\) sum to \(\langle c_v,Ac_v\rangle\), where \(c_v\) is the coefficient vector of \(X_v\). The value \(r_{pp}\) is attained in the limit by the Gaussian wave (Csóka et al. 2015; Harangi and Virág 2015; Backhausz, Szegedy, and Virág 2015), and the padded labels are its finite-radius approximations: their coefficients \((p-1)^{-k/2}\) on spheres are the test functions of Nilli’s proof of the Alon–Boppana bound (Nilli 1991). So Lemma 5.4 is asymptotically sharp for radial labels. For mixed degrees the limiting edge correlation can lie slightly above \(r_{ij}\). On the \((3,4)\)-biregular tree, every generation of the two sides of an edge \(uv\) with \(d(u)=3\) and \(d(v)=4\) carries the same squared mass, and a ball contains \(N_R+O(1)\) generations of each side, with \(N_R=4R/\ln6\); summing over generations gives \(\sigma_u^2=\frac32N_R+O(1)\), \(\sigma_v^2=\frac43N_R+O(1)\) and \(\mathop{\mathrm{Cov}}(X_u,X_v)=(2^{-1/2}+3^{-1/2})N_R+O(1)\), so the correlation tends to \((2^{-1/2}+3^{-1/2})/\sqrt2=\frac12+\frac1{\sqrt6}\approx0.9082\), above \(r_{34}\approx0.9074\).
5.1 The labels
A label is a normalized weighted sum of independent standard normal variables, one for each vertex, with weights that decay exponentially in a weighted distance. An arc is an ordered pair \((x,y)\) with \(xy\in E(G)\), written \(x\to y\).
Definition 5.2 (Gaussian labels). Let \(G\) be a graph, let \((Z_w)_{w\in V(G)}\) be independent \(N(0,1)\) variables, let every arc \(x\to y\) have a length \(\ell(x\to y)>0\), and let \(\hat R>0\). The directed distance \(D(v,w)\) is the minimum of \(\sum_{i<k}\ell(x_i\to x_{i+1})\) over all walks \(v=x_0,x_1,\dots,x_k=w\), with \(D(v,v)=0\) and \(D(v,w)=\infty\) if there is no such walk. Put \(B(v)=\{w:D(v,w)\le\hat R\}\) and \[X_v=\sum_{w\in B(v)}e^{-D(v,w)}Z_w,\qquad \sigma_v^2=\sum_{w\in B(v)}e^{-2D(v,w)},\qquad Y_v=X_v/\sigma_v .\]
(a) Padded labels of degree \(p\), for integers \(p\ge3\) and \(R\ge1\) and graphs with \(\Delta(G)\le p\): every arc has length \(\frac12\ln(p-1)\), and \(\hat R=\frac R2\ln(p-1)\).
(b) Mixed labels, for a real \(R>0\) and graphs with \(\delta(G)\ge3\): \(\ell(x\to y)=\frac12\ln\bigl(d(x)-1\bigr)\), and \(\hat R=R\).
By independence, \(\sigma_v^2=\mathop{\mathrm{Var}}X_v\). For padded labels, \(D(v,w)=\frac12\ln(p-1)\mathop{\mathrm{dist}}(v,w)\) and \(B(v)=B_R(v)\), so \[X_v=\sum_{w\in B_R(v)}(p-1)^{-\mathop{\mathrm{dist}}(v,w)/2}Z_w ;\] for \(p=3\) we call them the geometric labels, with coefficients \(2^{-\mathop{\mathrm{dist}}(v,w)/2}\). Padded labels are used with \(p=3\) for graphs of maximum degree \(3\) (Theorem 8.1) and with \(p=4\) for Theorem 7.1(a). In mixed labels the length of an arc depends on its tail only; they are used for graphs with \(\delta(G)\ge3\) and \(\Delta(G)\le5\) (Theorem 7.1(b),(c) and Theorem 7.2).
A walk of minimum length is a path, because all lengths are positive; since \(G\) is finite, the minimum in the definition of \(D\) is attained. The directed distance satisfies the triangle inequality \(D(u,w)\le D(u,x)+D(x,w)\), and in particular \[\begin{equation*} \tag{5.1} D(u,w)\le\ell(u\to v)+D(v,w)\qquad\text{for every edge }uv\text{ and every }w . \end{equation*}\] In the mixed case \(D\) is not symmetric. Its arc lengths lie between \(\ell_{\min}=\frac12\ln2\) and \(\frac12\ln(\Delta(G)-1)\). The decay rate is chosen so that in both regimes the arcs leaving a vertex, other than one, carry total squared weight at most one: \[\begin{equation*} \tag{5.2} \sum_{y\in N(x)\setminus\{y_0\}}e^{-2\ell(x\to y)}\le1 \qquad\text{for every vertex }x\text{ and every }y_0\in N(x). \end{equation*}\] Indeed the sum has \(d(x)-1\) terms, each equal to \(1/(p-1)\) in case (a), where \(d(x)\le p\), and to \(1/(d(x)-1)\) in case (b). In the mixed case, and in the padded case at vertices of degree \(p\), (5.2) holds with equality. We call this critical decay; Section 2.2 explains its role.
Remark 5.3 (path products). The algorithms of Section 10 describe the same labels by vertex weights instead of arc lengths. Put \(q(x)=p-1\) in case (a) and \(q(x)=d(x)-1\) in case (b), and let \(P(v,w)\) be the minimum of \(\prod_{i<k}q(x_i)\) over all \(v\)–\(w\) paths \(v=x_0,\dots,x_k=w\), with \(P(v,v)=1\). Since every arc \(x\to y\) has length \(\frac12\ln q(x)\), the length of a walk is \(\frac12\ln\) of its product, so \[e^{-D(v,w)}=P(v,w)^{-1/2}\qquad\text{and}\qquad X_v=\sum_{w\in B(v)}P(v,w)^{-1/2}Z_w,\] with \(B(v)=\{w:P(v,w)\le e^{2\hat R}\}\): the hop ball \(B_R(v)\) in case (a), and \(\{w:P(v,w)\le2^h\}\) in case (b) when \(R=\frac h2\ln2\). The two descriptions define identical labels.
The correlation bounds are expressed through the following constants. For integers \(i,j\ge3\) put \[\begin{equation*} \tag{5.3} r_{ij}=\mathop{\mathrm{sech}}\Bigl(\tfrac14\ln\bigl((i-1)(j-1)\bigr)\Bigr) =\frac{2\,g_{ij}}{1+g_{ij}^{2}},\qquad g_{ij}=\bigl((i-1)(j-1)\bigr)^{1/4}. \end{equation*}\] They are symmetric and decrease in each index. On the diagonal, \(r_{pp}=\mathop{\mathrm{sech}}(\frac12\ln(p-1))=2\sqrt{p-1}/p\); so \(r_{33}=r_*=\frac{2\sqrt2}3\), \(r_{44}=\frac{\sqrt3}2\) and \(r_{55}=\frac45\). Table 3 lists the values for \(3\le i\le j\le5\).
Table 3: The edge correlation bounds \(r_{ij}\) of (5.3) for end degrees \(3\le i\le j\le5\).
| \((i,j)\) | \((i-1)(j-1)\) | exact value | decimal |
|---|---|---|---|
| \((3,3)\) | \(4\) | \(\frac{2\sqrt2}{3}\) | \(0.942809\) |
| \((3,4)\) | \(6\) | \(\frac{2\cdot6^{1/4}}{1+\sqrt6}\) | \(0.907430\) |
| \((3,5)\) | \(8\) | \(\frac{2\cdot8^{1/4}}{1+2\sqrt2}\) | \(0.878582\) |
| \((4,4)\) | \(9\) | \(\frac{\sqrt3}{2}\) | \(0.866025\) |
| \((4,5)\) | \(12\) | \(\frac{2\cdot12^{1/4}}{1+2\sqrt3}\) | \(0.833856\) |
| \((5,5)\) | \(16\) | \(\frac45\) | \(0.800000\) |
The main statements of this section are the following two lemmas. The first covers the padded labels, and in particular the geometric labels of the cubic case.
Lemma 5.4 (edge correlations, padded labels). Let \(p\ge3\) and \(R\ge1\) be integers, let \(G\) be a graph with \(\Delta(G)\le p\), and let \((Y_v)\) be the padded labels of degree \(p\) (Definition 5.2(a)). Then every edge \(uv\) satisfies \(\mathop{\mathrm{Corr}}(Y_u,Y_v)\ge r_{pp}(1-\frac1R)\).
Lean proof: Locality.graph_correlation_lower (what is formalised)
The second covers the mixed labels, where the bound depends on the degrees of the two ends of the edge. For \(\Delta_0\ge3\) put \(\ell_{\max}=\frac12\ln(\Delta_0-1)\), so that all arc lengths of a graph with \(\delta(G)\ge3\) and \(\Delta(G)\le\Delta_0\) lie in \([\ell_{\min},\ell_{\max}]\), where \(\ell_{\min}=\frac12\ln2\) as above. For \(R>2\ell_{\max}\) put \[\begin{equation*} \tag{5.4} \varepsilon_R=\frac{2\ell_{\max}^2}{\ell_{\min}\,(R-2\ell_{\max})}. \end{equation*}\]
Lemma 5.5 (edge correlations, mixed labels). Let \(\Delta_0\ge3\) and \(R>2\ell_{\max}\), let \(G\) be a graph with \(\delta(G)\ge3\) and \(\Delta(G)\le\Delta_0\), and let \((Y_v)\) be the mixed labels (Definition 5.2(b)). Then every edge \(uv\) satisfies \(\mathop{\mathrm{Corr}}(Y_u,Y_v)\ge r_{d(u)d(v)}(1-\varepsilon_R)\).
For \(\Delta_0=5\) we have \(\ell_{\max}=\ln2\) and \(2\ell_{\max}^2/\ell_{\min}=4\ln2\), so \(\varepsilon_R=\frac{4\ln2}{R-2\ln2}\); with \(R=\frac h2\ln2\) for an integer \(h>4\), also \(R-2\ell_{\max}=\frac{h-4}2\ln2\) and \(\varepsilon_R=\frac8{h-4}\). Since \(\varepsilon_R\to0\) as \(R\to\infty\), every edge correlation is asymptotically at least the value \(r_{ij}\) determined by the degrees of its ends.
Lemma 5.6 (distinctness and locality). Let \((Y_v)\) be labels as in Definition 5.2, in either regime. Put \(\rho=R\) for padded labels and \(\rho=\lfloor2R/\ln2\rfloor\) for mixed labels. Then:
(i) \((Y_v)_{v\in V(G)}\) is a centered Gaussian vector, \(\mathop{\mathrm{Var}}Y_v=1\) and \(\sigma_v\ge1\) for every \(v\);
(ii) the labels are pairwise distinct with probability \(1\);
(iii) \(B(v)\subseteq B_\rho(v)\), so \(Y_v\) is a function of \((Z_w)_{w\in B_\rho(v)}\);
(iv) for every \(t\in\mathbb{R}\), the events \(\{v\in\partial^{+}S_t\}\) and \(\{v\in\partial^{-}S_t\}\) for the labeling \(Y\) are determined by \((Z_w)_{w\in B_{\rho+1}(v)}\).
So every count of the form \(\sum_v\mathbf{1}\{v\in\partial^{+}S_t\}\) satisfies the hypothesis of Lemma 4.10 with \(A_v=B_{\rho+1}(v)\). The radius \(\rho\) is fixed for fixed \(R\); the sweeps let \(R\) grow slowly with \(n\), so that \(\varepsilon_R\to0\) while the dependence radius stays small enough for concentration.
5.2 Distinctness and locality
Proof of Lemma 5.6. (i) Each \(X_v\) is a finite linear combination of the independent standard normal variables \(Z_w\), so \((X_v)\) and \((Y_v)\) are centered Gaussian vectors. Since \(v\in B(v)\) with coefficient \(e^{-D(v,v)}=1\), \(\sigma_v^2\ge1\), and \(\mathop{\mathrm{Var}}Y_v=1\) by construction.
(ii) Let \(u\ne v\). The coefficient of \(Z_u\) in \(Y_u-Y_v\) is \(1/\sigma_u-\mathbf{1}\{u\in B(v)\}e^{-D(v,u)}/\sigma_v\), and the coefficient of \(Z_v\) is \(\mathbf{1}\{v\in B(u)\}e^{-D(u,v)}/\sigma_u-1/\sigma_v\). If both vanish, then \(u\in B(v)\) and \(\sigma_v=\sigma_ue^{-D(v,u)}\), and \(v\in B(u)\) and \(\sigma_v=\sigma_ue^{D(u,v)}\). Hence \(D(u,v)+D(v,u)=0\), which is impossible because \(u\ne v\) and all arc lengths are positive. So \(Y_u-Y_v\) is a normal variable with positive variance, and \(\mathbb{P}(Y_u=Y_v)=0\). A union bound over the finitely many pairs gives the claim.
(iii) For padded labels \(B(v)=B_R(v)\). For mixed labels, every arc has length at least \(\ell_{\min}=\frac12\ln2\) because \(\delta(G)\ge3\), so a walk of length at most \(R\) has at most \(R/\ell_{\min}\) arcs, and \(D(v,w)\le R\) implies \(\mathop{\mathrm{dist}}(v,w)\le\lfloor R/\ell_{\min}\rfloor=\lfloor2R/\ln2\rfloor\).
(iv) By definition, \(v\in\partial^{+}S_t\) if and only if \(Y_v>t\) and \(Y_u\le t\) for some \(u\in N(v)\), and \(v\in\partial^{-}S_t\) if and only if \(Y_v\le t\) and \(Y_u>t\) for some \(u\in N(v)\). Both are determined by \((Y_x)_{x\in N[v]}\), and by (iii) each such \(Y_x\) is a function of \(Z\) restricted to \(B_\rho(x)\subseteq B_{\rho+1}(v)\). ∎
5.3 A ratio inequality
Both correlation lemmas reduce to the following inequality for the shared part of two labels: the weights \(a_w\) and \(b_w\) that the two labels give to the same variable \(Z_w\).
Lemma 5.7. Let \(\alpha,\beta>0\), let \(I\) be a finite set, and let \(a_w,b_w>0\) (\(w\in I\)) satisfy \(b_w/\alpha\le a_w\le\beta b_w\). Then, with \(A=\sum_{w\in I}a_w^2\) and \(B=\sum_{w\in I}b_w^2\), \[\sum_{w\in I}a_wb_w\ \ge\ \mathop{\mathrm{sech}}\Bigl(\tfrac12\ln(\alpha\beta)\Bigr)\sqrt{AB}.\]
Proof. Since \(1/\alpha\le a_w/b_w\le\beta\), the inequality of Diaz and Metcalf (Diaz and Metcalf 1963 Theorem 1) gives the first inequality below (it is the sum of the inequalities \((a_w-b_w/\alpha)(\beta b_w-a_w)\ge0\)), and the second is the inequality of arithmetic and geometric means: \[\Bigl(\beta+\frac1\alpha\Bigr)\sum_{w\in I}a_wb_w\ \ge\ A+\frac\beta\alpha B\ \ge\ 2\sqrt{\frac\beta\alpha}\,\sqrt{AB}.\] Finally \(2\sqrt{\beta/\alpha}\big/(\beta+1/\alpha)=2\sqrt{\alpha\beta}/(\alpha\beta+1) =2/\bigl(\sqrt{\alpha\beta}+1/\sqrt{\alpha\beta}\bigr)=\mathop{\mathrm{sech}}(\frac12\ln(\alpha\beta))\). ∎
For an edge \(uv\) we apply the lemma to \(a_w=e^{-D(u,w)}\) and \(b_w=e^{-D(v,w)}\) on the common support \(I=B(u)\cap B(v)\). By (5.1) and its counterpart with \(u\) and \(v\) exchanged, \(a_w\ge e^{-\ell(u\to v)}b_w\) and \(b_w\ge e^{-\ell(v\to u)}a_w\); so the hypothesis holds with \(\alpha=e^{\ell(u\to v)}\) and \(\beta=e^{\ell(v\to u)}\), and \(\frac12\ln(\alpha\beta)=\frac12L_{uv}\) with \(L_{uv}=\ell(u\to v)+\ell(v\to u)\). Because coefficients outside \(I\) are paired with zero coefficients, \[\begin{equation*} \tag{5.5} \mathop{\mathrm{Cov}}(X_u,X_v)=\sum_{w\in I}a_wb_w\ \ge\ \mathop{\mathrm{sech}}\bigl(\tfrac12L_{uv}\bigr)\sqrt{AB}, \qquad A=\sum_{w\in I}a_w^2,\quad B=\sum_{w\in I}b_w^2 . \end{equation*}\] For padded labels \(L_{uv}=\ln(p-1)\) and \(\mathop{\mathrm{sech}}(\frac12L_{uv})=r_{pp}\). For mixed labels \(L_{uv}=\frac12\ln((i-1)(j-1))\) with \(i=d(u)\), \(j=d(v)\), and \(\mathop{\mathrm{sech}}(\frac12L_{uv})=r_{ij}\). It remains to show that \(A\) and \(B\) are almost all of \(\sigma_u^2\) and \(\sigma_v^2\): the outer shells \(B(u)\setminus I\) and \(B(v)\setminus I\) carry little squared mass.
5.4 Padded labels: proof of Lemma 5.4
For \(p=3\) these are the geometric labels, and the lemma is Lemma 3.4; the proof of that lemma applies to every \(p\) with the base \(2\) replaced by \(p-1\).
Proof of Lemma 5.4. Write \(q=p-1\ge2\) and let \(uv\) be an edge. As in the proof of Lemma 3.4, a vertex at distance \(j\ge1\) from \(u\) has at most \(q\) neighbors at distance \(j+1\), so the sphere masses \(s_jq^{-j}\) are nonincreasing in \(j\ge1\), and the outermost one carries at most a fraction \(\frac1R\) of \(\sigma_u^2=1+\sum_{j=1}^Rs_jq^{-j}\). Every vertex of \(B_R(u)\setminus B_R(v)\) lies on the sphere of radius \(R\) around \(u\). Hence \(A\ge(1-\frac1R)\sigma_u^2\) in (5.5), and likewise \(B\ge(1-\frac1R)\sigma_v^2\). Since \(\mathop{\mathrm{sech}}(\frac12\ln q)=2\sqrt q/(q+1)=r_{pp}\), (5.5) gives \(\mathop{\mathrm{Corr}}(Y_u,Y_v)\ge r_{pp}(1-\frac1R)\). ∎
No step uses regularity, girth, connectivity or a lower bound on the degrees: vertices of degree less than \(p\) only make the sphere bound \(s_{j+1}\le qs_j\) slack, and vertices in different components have disjoint supports.
5.5 Mixed labels: proof of Lemma 5.5
For mixed labels the balls \(B(v)\) are defined by the directed distance, whose spheres are not layers of the graph. The sphere argument is therefore replaced by a cut argument in a shortest-path tree rooted at one end \(u\) of the edge \(uv\). Step 1 locates the outer shell in a layer of width \(\ell_{\max}\) below the boundary of the ball. Steps 2 and 3 show, using the critical decay (5.2), that the squared mass of the cut at directed distance \(t\) from \(u\) is nonincreasing in \(t\). Step 4 integrates the cut mass over \(t\) and compares the shell with the whole ball.
Proof of Lemma 5.5. Let \(uv\) be an edge with \(d(u)=i\) and \(d(v)=j\). All arc lengths lie in \([\ell_{\min},\ell_{\max}]\), because \(3\le d(x)\le\Delta_0\) for every \(x\). By (5.5), it suffices to show \[\begin{equation*} \tag{5.6} \sum_{w\in B(u)\setminus B(v)}e^{-2D(u,w)}\le\varepsilon_R\,\sigma_u^2 \end{equation*}\] and the same statement with \(u\) and \(v\) exchanged. Indeed, then \(A\ge(1-\varepsilon_R)\sigma_u^2\) and \(B\ge(1-\varepsilon_R)\sigma_v^2\), and (5.5) gives \(\mathop{\mathrm{Corr}}(Y_u,Y_v)\ge r_{ij}(1-\varepsilon_R)\) if \(\varepsilon_R\le1\); if \(\varepsilon_R>1\) the claim holds because \(\mathop{\mathrm{Cov}}(X_u,X_v)\ge0\), all coefficients being nonnegative. We prove (5.6); the other statement is symmetric, using \(\ell(u\to v)\le\ell_{\max}\). Throughout, write \(D(w)=D(u,w)\).
Step 1: the shell is thin. If \(w\in B(u)\setminus B(v)\), then \(D(v,w)>R\), and \(D(v,w)\le\ell(v\to u)+D(w)\) by (5.1); hence \[\begin{equation*} \tag{5.7} R-\ell_{\max}<D(w)\le R . \end{equation*}\]
Step 2: a shortest-path tree. Let \(V_u\) be the set of vertices in the component of \(u\). For \(w\in V_u\setminus\{u\}\) choose a shortest \(u\)–\(w\) path and let \(p(w)\) be the vertex before \(w\) on it. Its initial segment is a walk from \(u\) to \(p(w)\), so \(D(p(w))\le D(w)-\ell(p(w)\to w)\), and the triangle inequality gives the reverse; hence \[D(w)=D(p(w))+\ell\bigl(p(w)\to w\bigr),\qquad D(p(w))<D(w).\] Following \(p\) from any \(w\) strictly decreases \(D\) and therefore reaches \(u\). So the pairs \((p(w),w)\) form a tree \(\mathcal T\) on \(V_u\) rooted at \(u\), in which \(p(w)\) is the parent of \(w\). Write \(\operatorname{ch}(x)=\{w:p(w)=x\}\) for the children of \(x\). For \(x\ne u\), the children of \(x\) are neighbors of \(x\) with larger \(D\), so \(\operatorname{ch}(x)\subseteq N(x)\setminus\{p(x)\}\), and by (5.2) \[\begin{equation*} \tag{5.8} \sum_{c\in\operatorname{ch}(x)}e^{-2D(c)}=e^{-2D(x)}\sum_{c\in\operatorname{ch}(x)}e^{-2\ell(x\to c)}\le e^{-2D(x)}\qquad(x\ne u). \end{equation*}\] Call a set \(\mathcal A\) of vertices an antichain if no element of \(\mathcal A\) is a proper descendant of another in \(\mathcal T\). We claim: for every \(x\ne u\) and every antichain \(\mathcal A\) of descendants of \(x\) (including \(x\) itself), \[\begin{equation*} \tag{5.9} \sum_{w\in\mathcal A}e^{-2D(w)}\le e^{-2D(x)}. \end{equation*}\] We induct on the height of the subtree of \(x\). If \(x\in\mathcal A\), then \(\mathcal A=\{x\}\). Otherwise \(\mathcal A\) is the disjoint union, over \(c\in\operatorname{ch}(x)\), of antichains of descendants of \(c\), and by induction and (5.8) its mass is at most \(\sum_{c}e^{-2D(c)}\le e^{-2D(x)}\).
Step 3: moving cuts. For \(t>0\) let \[\mathcal A_t=\bigl\{w\in V_u\setminus\{u\}:\ D(p(w))<t\le D(w)\bigr\},\qquad m(t)=\sum_{w\in\mathcal A_t}e^{-2D(w)} .\] We show that \(m\) is nonincreasing on \((0,\infty)\). Let \(0<t<t'\) and \(w\in\mathcal A_{t'}\). Along the path \(u=x_0,x_1,\dots,x_k=w\) in \(\mathcal T\), \(D\) increases strictly from \(0<t\) to \(D(w)\ge t'>t\), so there is exactly one index \(s\ge1\) with \(D(x_{s-1})<t\le D(x_s)\); that is, \(w\) has exactly one ancestor-or-self in \(\mathcal A_t\). For \(x\in\mathcal A_t\), the set of \(w\in\mathcal A_{t'}\) whose ancestor-or-self in \(\mathcal A_t\) is \(x\) is an antichain of descendants of \(x\): if \(w'\in\mathcal A_{t'}\) were a proper descendant of \(w\in\mathcal A_{t'}\), then \(D(p(w'))\ge D(w)\ge t'\), contradicting \(w'\in\mathcal A_{t'}\). By (5.9), \[m(t')=\sum_{x\in\mathcal A_t}\ \sum_{\substack{w\in\mathcal A_{t'}\\ w\text{ below }x}}e^{-2D(w)}\le\sum_{x\in\mathcal A_t}e^{-2D(x)}=m(t).\]
Step 4: integrating the cut. Each \(w\in V_u\setminus\{u\}\) belongs to \(\mathcal A_t\) exactly for \(t\) in the interval \(J_w=(D(p(w)),D(w)]\), whose length \(\ell(p(w)\to w)\) lies in \([\ell_{\min},\ell_{\max}]\). Since the sums are finite, for \(0\le a<b\) \[\begin{equation*} \tag{5.10} \int_a^bm(t)\,dt=\sum_{w\in V_u\setminus\{u\}}e^{-2D(w)}\,\bigl|J_w\cap(a,b]\bigr| . \end{equation*}\] Put \(T=R-2\ell_{\max}>0\).
Upper bound on \(m(T)\). A vertex \(w\) contributes to (5.10) with \((a,b]=(0,T]\) only if \(D(p(w))<T\), and then \(D(w)<T+\ell_{\max}\le R\), so \(w\in B(u)\setminus\{u\}\); its contribution is at most \(\ell_{\max}e^{-2D(w)}\). Since \(m\) is nonincreasing, \[T\,m(T)\le\int_0^Tm(t)\,dt\le\ell_{\max}\sum_{w\in B(u)\setminus\{u\}}e^{-2D(w)}\le\ell_{\max}\,\sigma_u^2 .\]
The shell as an integral. Every \(w\) in the shell \(B(u)\setminus B(v)\) satisfies (5.7), so \(w\ne u\) and \(D(p(w))\ge D(w)-\ell_{\max}>R-2\ell_{\max}=T\). Hence \(J_w\subseteq(T,R]\), and \(w\) contributes \(e^{-2D(w)}|J_w|\ge\ell_{\min}e^{-2D(w)}\) to (5.10) with \((a,b]=(T,R]\). All other contributions are nonnegative, and \(m(t)\le m(T)\) for \(t>T\), so \[\ell_{\min}\sum_{w\in B(u)\setminus B(v)}e^{-2D(w)}\le\int_T^Rm(t)\,dt\le2\ell_{\max}\,m(T).\]
Combining the two bounds, \[\sum_{w\in B(u)\setminus B(v)}e^{-2D(w)}\le\frac{2\ell_{\max}}{\ell_{\min}}\cdot\frac{\ell_{\max}\sigma_u^2}{R-2\ell_{\max}}=\varepsilon_R\,\sigma_u^2\] by the definition (5.4) of \(\varepsilon_R\), which is (5.6).
∎
The proof uses the degrees only through the critical decay (5.2) and the bounds \(\ell_{\min}\le\ell\le\ell_{\max}\) on the arc lengths. It therefore applies to any lengths with these two properties.