(4.15) $a=2\lambda\sqrt{\frac{d-1}{d}}b.$

Taking derivative in $a$ give us,

(4.16) $2a-2\lambda a+\sqrt{\frac{d}{d-1}}b=0.$

Substituting in our previous relation between $a$ and $b$ gives us the
following relationship on $\lambda$.

(4.17) $4\lambda^{2}-4\lambda+1-\frac{d}{d-1}-1=0.$

Thus, $\lambda$ is given by,

(4.18) $\lambda=\frac{1}{2}+\frac{1}{2}\sqrt{\frac{2d-1}{d-1}}.$

We can now substitute this into the relation $a^{2}+b^{2}=1$ to derive,

(4.19)
$b=\frac{1}{\sqrt{1+4\frac{d-1}{d}\lambda^{2}}},a=\frac{2\lambda\sqrt{\frac{d-1}{d}}}{\sqrt{1+4\frac{d-1}{d}\lambda^{2}}}$

The value of $\sqrt{\frac{d}{d-1}}ab+a^{2}$ is now given by,

(4.20)
$\frac{2\lambda\left[1+2\lambda\frac{d-1}{d}\right]}{1+4\frac{d-1}{d}\lambda^{2}}.$

Now the equation for $\lambda$ gives,

(4.21) $4\frac{d-1}{d}\lambda^{2}+1=4\frac{d-1}{d}\lambda+2.$

Thus, the value of $\sqrt{\frac{d}{d-1}}ab+a^{2}$ is now given by $\lambda$.
This $\lambda$ is our upper bound on the sum
$\sum_{y\in\delta(\mathbb{T})}|P_{iy}|$.

∎

Now, with combinatorial estimates for $(P|_{\mathbb{T}})^{-1}$ in hand, we
will be able to return to compute estimates on the difference
$(G|_{\mathbb{T}})^{-1}-(P|_{\mathbb{T}})^{-1}$. This is encompassed in the
following lemma,

######  Lemma 4.7.

Recall the setting of the previous Lemma.

Then

(4.22)
$|(G|_{\mathbb{T}})^{-1}-(P|_{\mathbb{T}})^{-1}|_{xy}\lesssim\epsilon(z,w).$

###### Proof.

Let $E$ be the matrix of differences,

(4.23) $\displaystyle(G|_{\mathbb{T}})^{-1}=(P|_{\mathbb{T}})^{-1}+E$
$\displaystyle G|\mathbb{T}=P|_{\mathbb{T}}+W.$

By our inductive assumption, the entries of $W$ are bounded by
$W_{ab}\leq\epsilon(z,w)$ for all $a,b$ found in $\mathbb{T}$.

Multiplying these equations together give us,

(4.24) $I=I+EP|_{\mathbb{T}}+(P|_{\mathbb{T}})^{-1}W+EW.$

Manipulating this expression gives us,

(4.25)
$E=-(P|_{\mathbb{T}})^{-1}W(P|_{\mathbb{T}})^{-1}-EW(P|_{\mathbb{T}})^{-1}.$

Considering the appearance of $E$ on the right hand side, our hope is to use a
maximum principle argument to show that the entries of $E$ are bounded.

Define $\Lambda:=max_{c,d\in\mathbb{T}}|E_{cd}|$. Then, we see that,

(4.26)
$|[EW(P|_{\mathbb{T}})^{-1}]_{cd}|\leq\sum_{ef}|E_{ce}||W_{ef}||[(P|_{\mathbb{T}})^{-1}]_{fd}|\leq
2(2d-1)^{l}\Lambda\epsilon(z,w)\sum_{f}|[(P|_{\mathbb{T}})^{-1}]_{fd}|.$

Here, we used the fact that the number of possible indices $e$ in $\mathbb{T}$
is $2(2d-1)^{l}$, which satisfies $(2d-1)^{l}\leq(\log N)^{2}$. Furthermore,
one can use Lemma 4.4 to assert

(4.27) $\sum_{f}|[(P|_{\mathbb{T}})^{-1}]_{fd}|\lesssim 1.$

Thus, we can bound the second term as,

(4.28) $|[EW(P|_{\mathbb{T}})^{-1}]_{cd}|\leq o(1)\Lambda.$

Now, we can try to bound the first term, we see that,

(4.29) $\displaystyle|[(P|_{\mathbb{T}})^{-1}W(P|_{\mathbb{T}})^{-1}]_{cd}|$
$\displaystyle\leq\sum_{ef}|[(P|_{\mathbb{T}})^{-1}]_{ce}||W_{ef}||[(P|_{\mathbb{T}})^{-1}]_{fd}|$
$\displaystyle\leq\epsilon(z,w)(\sum_{e}|[(P|_{\mathbb{T}})^{-1}]_{ce}|)(\sum_{f}|[(P|_{\mathbb{T}})^{-1}]_{fd}|)$
$\displaystyle\lesssim\epsilon(z,w).$

The last line is again based on Lemma 4.4.

Combining these estimates together, we see that,

(4.30) $\Lambda\leq o(1)\Lambda+C\epsilon(z,w).$

This gives us our desired statement. ∎

We now return to the proof of Proposition 2.15

###### Proof of Proposition 2.15.

For a specific entry $(a,b)$ , we have that,

We deal with each term in (4.4) separately.

We can bound $|G_{ij}-P_{ij}|$ be $\epsilon(z,w)$ by our induction hypothesis.
We need to perform a little bit more manipulation on our first term
$(G-P)(G|_{\mathbb{T}})^{-1}G$.

We see that we have,

(4.31)
$(G-P)(G|_{\mathbb{T}})^{-1}G=(G-P)(P|_{\mathbb{T}})^{-1}G+(G-P)[(G|_{\mathbb{T}})^{-1}-(P|_{\mathbb{T}})^{-1}]G.$

We now bound the first term appearing above,

(4.32)
$|[(G-P)(P|_{\mathbb{T}})^{-1}G]_{ij}|\leq\sum_{x,y\in\mathbb{T}}|[G-P]_{ix}||[(P|_{\mathbb{T}})^{-1}]_{xy}||G_{yj}|.$

We can bound $[[G-P]_{ix}|$ by $\epsilon(z)$. If we fix $y$ and sum over $x$,
we observe that,

(4.33) $\sum_{x\in\mathbb{T}}|[(P|_{\mathbb{T}})^{-1}]_{xy}|\lesssim 1,$

uniformly over $x$.

Thus, the preceding equation (4.32) is bounded by,

(4.34)
$\epsilon(z,w)\sum_{y\in\mathbb{T}}|G_{yj}|\leq\epsilon(z,w)\sum_{y\in\mathbb{T}}[\epsilon(z,w)+|P_{yj}|]$

We have that, from Lemma 4.5

$\sum_{y\in\mathbb{T}}|P_{yj}|\leq(\log N)^{\mathfrak{j}(d)\mathfrak{a}}.$

The term $(G-P)[(G|\mathbb{T})^{-1}-(P|\mathbb{T})^{-1}]G$ will give an error
of the form $(\log N)^{8\mathfrak{a}}\epsilon^{2}(z,w)$. This is of even
smaller order than our proposed main error term.

Similar logic can be used to estimate the other terms remaining in (4.4).
Ultimately, we can get our desired bound,

(4.35) $|G_{ij}-P_{ij}|\lesssim\epsilon^{\prime}(z,w).$

∎

##  5\. Removal of the switched vertices $W_{S}$: Proof of Proposition 2.16

As one can see from the statement of Proposition 2.16, one needs many
auxiliary notions for optimal estimates. As we will describe later, it is not
good enough to simply use the worst case bound at all time. In general, most
elements will be much smaller than the worst case bound $\epsilon^{\prime}$.
It is this property which we exploit in what follows.

###  5.1. Introduction of Green’s function distance metric

In the past section, we used $\epsilon$ as a control parameter to determine
the maximum value of the distance of the Green’s functions
$|G_{ij}-P_{ij}|\leq\epsilon.$ However, we find that there is a small
difference between this worst case estimate and the average case estimate.

By the Ward Identity, we have that,

(5.1)
$\sum_{i,j}|G^{(\mathbb{T})}_{ij}|^{2}=\frac{\text{Im}[G^{(\mathbb{T})}_{ii}]}{\eta}.$

Thus, for any function $f(N)$, we see that no more than $\frac{N}{f(N)}$
indices $j$ (for a fixed $i$) can satisfy the property that,

(5.2)
$|G^{(\mathbb{T})}_{ij}|\geq\frac{\sqrt{f(N)\text{Im}[G^{(\mathbb{T})}_{ii}]}}{\sqrt{N\eta}}.$

By replacing $\text{Im}[G_{ii}]$ with the deterministic value
$m_{\infty}(z,w)$ with small error, we see that the pigeonhole principle will
assert the concrete estimate that,

(5.3)
$|G^{(\mathbb{T})}_{ij}|\geq\frac{\sqrt{f(N)\text{Im}[m_{\infty}(z,w)]}}{\sqrt{N\eta}},$

for no more than $2\frac{N}{f(N)}$ indices $j$ ( This merely used the fact
that $\text{Im}[G^{(\mathbb{T})}_{ii}]\leq 2\text{Im}[m_{\infty}(z,w)]$ from
our inductive local law estimate on $\text{Im}[G^{(\mathbb{T})}_{ii}]$.)

It might look like this gives very little gain at first; however, we will soon
see that improperly applied stability estimates would ruin the stability
estimates by vastly increasing the prefactor of $(\log N)$ in front of the
epsilon. Namely, instead of $(\log N)^{j(d)\mathfrak{a}}$, we may get $(\log
N)^{C\mathfrak{a}}$ for very large $C$ after our stability iteration.
Unfortunately, the concentration estimate we apply later is not good enough to
cancel out the increase of this multiplicative prefactor.

######  Remark 5.1.

the concentration estimate which we will prove in Section 8 can kill a factor
of say $(\log N)^{\mathfrak{a}}$. Thus, it unfortunately cannot kill a large
multiplicative factor of the form $(\log N)^{K\mathfrak{a}}$. However,
choosing $\mathfrak{a}$ large enough can kill any power of the form $(\log
N)^{p}$ for some constant power $p$. The notions in this section allow us to
reduce the decay in the stability estimate from $(\log N)^{K\mathfrak{a}}$ to
$(\log N)^{p}$.

######  Definition 5.2.

Fix the parameter

(5.4) $\phi(z,w):=\frac{(\log
N)^{\frac{K}{2}\mathfrak{a}}}{N^{1-\mathfrak{c}}}+\frac{(\log
N)^{\frac{K}{2}\mathfrak{a}}\sqrt{\text{Im}[m_{\infty}(z,w)]}}{\sqrt{N\eta}}.$

The important part of $\phi$ is that $\phi\ll(\log
N)^{-\frac{K}{2}\mathfrak{a}}\epsilon(z,w)$. We also use
$(\epsilon^{\prime})^{2}\ll\phi$ many times for convenience of the final
expression.

We say two indices $i$ and $j$ corresponding to vertices in $(\mathbb{T})^{c}$
are Green’s function connected if there is any neighbor $i^{\prime}$ of $i$
and a neighbor $j^{\prime}$ of $j$ such that
$|G^{(\mathbb{T})}_{i^{\prime}j^{\prime}}|\geq\phi$. We will use the notation
$i\sim j$ if this is the case. Note that this is not an equivalence relation
due to lack of transitivity.

We will use the fact that most Green’s function would have the slightly better
error estimate $|G^{(\mathbb{T})}_{ij}-P^{(\mathbb{T})}_{ij}|\leq\phi$ so that
we do not need to worry as much about the decay of the multiplicative factor.
In order to see this, we prove the following lemma, which shows how most
vertices in $\mathbb{T}^{c}$ cannot be Green’s function connected to too many
( more than $O(\log N)$) of the vertices that we want to switch.

######  Lemma 5.3.

Fix our random $d$regular digraph $\mathcal{G}$ as well as a vertex $v$ whose
local $\mathfrak{R}$-like neighborhood is treelike. Consider the local $l$
neighborhood $\mathbb{T}$ around the vertex $v$. Let
$e_{1}=(v_{1},w_{1}),\ldots,e_{\mu}=(v_{\mu},w_{\mu})$ be randomly selected
edges that lie outside $\mathbb{T}$ in $\mathcal{G}$ and $\mu$ is the number
of edges connecting $\mathbb{T}$ to $\mathbb{T}^{c}$. Then, with probability
$1-O(N^{-\mathfrak{q}})$, we have the following two conditions:

  1. (1)

Any index $v$ in $\mathbb{T}^{c}$ is Green’s function connected to no more
than $O(\log N)$ of the indices corresponding to vertices
$\\{b_{1},c_{1},\ldots,b_{\mu},c_{\mu}\\}$.

  2. (2)

The set $\alpha$ such that $\\{b_{\alpha},c_{\alpha}\\}$ is Green’s function
connected to some $\\{b_{\beta},c_{\beta}\\}$ for $\beta\neq\alpha$ is $O(\log
N)$.

Any vertex $v$ in $\mathbb{T}^{c}$ is Green’s function connected to no more
than $O(\log N)$ vertices in $\cup_{i=1}^{m}\\{v_{i},w_{i}\\}$.

###### Proof.

Let $X$ be any vertex in $\mathbb{T}^{c}$ For the vertex $X$, the set $X_{GF}$
of the vertices that are Green’s function connected to is of size less than
$\frac{N}{(logN)^{K\mathfrak{a}}}$. For each $i$ in $\\{1,\ldots,m\\}$, the
chance that $X$ is Green’s function connected to one of $v_{i},w_{i}$is an
independent event. At this point, one can obtain the desired result by
straightforward counting arguments. One can see [12, Prop. 5.14] for details.
∎

At this point, we can finally define the event $S_{G}(\mathcal{G})$ of good
switching events.

######  Definition 5.4.

Consider a graph $\mathcal{G}$ in $\Omega_{g}(z,w)$ as well as a distinguished
vertex $o$ along with its radius $\ell$ neighborhood $\mathbb{T}$. Recall
$\mathbb{S}_{\mathcal{G},o}$, the switching events that correspond to the
graph $\mathcal{G}$ around vertex $o$ as well as the characteristic variables
$\chi_{\alpha}$. We define the event
$S_{G}(\mathcal{G})\subset\mathbb{S}_{\mathcal{G}}$ as follows: a switch $S$
will belong to $S_{G}(\mathcal{G})$ if it satisfies the following conditions,

  1. (1)

All except for $O_{\mathfrak{q}}(1)$ of the vertices
$\\{c_{1},\ldots,c_{\mu}\\}$ have radius $\mathfrak{R}$ tree neighborhoods in
$\mathcal{G}^{(\mathbb{T})}$.

  2. (2)

$\chi_{\alpha}=1$ for all except $O_{\mathfrak{q}}(1)$ many vertices.

  3. (3)

The Green’s function connectivity conditions of Lemma 5.3 hold.

Due to Lemmas 5.3 and Proposition 2.6, the event $S_{G}(\mathcal{G})$ holds
with probability $\mathbb{P}(S_{G}(\mathcal{G}))=1-O(N^{-\mathfrak{q}})$.

In what follows in Sections 5 ,6, and 7, we will always implicitly assume we
are considering a switching even $S$ found in $S_{G}(\mathcal{G})$.

###  5.2. Switching estimates involving the Green’s function distance

We can apply a very similar type of analysis for the removal of the vertices
in $W_{S}$. Given a switching event $S$, where we elect to switch the vertices
on the boundary of $\mathbb{T}$ with arbitrary edges, the vertices $W_{S}$
consist of those vertices $\\{b_{1},\ldots,b_{\mu}\\}$. Again, we introduce,
as a shorthand, the matrix $P:=G(Ext(B_{r}(\\{i,j\\}\cup
W_{S},\mathcal{G}\backslash\mathbb{T}),Q_{I},Q_{O}))$. As before, the point of
this matrix is that we can write $G^{(\mathbb{T})}$ as,

(5.5) $(G^{(\mathbb{T})})^{-1}=\begin{bmatrix}A&B\\\ B^{*}&D\end{bmatrix},$

and

(5.6) $P^{-1}=\begin{bmatrix}A&B\\\ B^{*}&D^{\prime}\end{bmatrix}.$

Here, $A$ is the adjacency matrix of the graph restricted to $W_{S}$ and $B$
will be the adjacency matrix of the edges connecting $W_{S}$ to $W_{S}^{c}$.
At this point, we remark that we can restrict to the event that all the edges
that are chosen for switching are far away from each other; more specifically,
two vertices in $b_{\alpha},b_{\beta}$ in $W_{S}$ are of distance at least
$\mathfrak{r}$ from each other.

Due to this restriction, the matrix $P|_{W_{S}}$ is much easier to understand.
It is a block diagonal matrix (with $2\times 2$ blocks) where the blocks
consist of the indices $b_{\alpha}$ and $b_{\alpha}+N$ of the vertices that
bound the edge used in the switching. For this reason, it is also easy to
describe the matrix $(P|_{W_{S}})^{-1}$.

Another remark that we will have to make is that in addition to proving the
stability of the worst case bound $|G^{(T)}_{ij}-P^{(T)}_{ij}|\leq\epsilon$,
we would further need to prove the stability of the average case bound for
pairs of vertices that are not Green’s function connected. With this remark in
mind, we now return to the proof.

By applying the Schur complement formula, we have that,

(5.7) $\displaystyle G^{(\mathbb{T}\cup
W_{S})}=G^{(\mathbb{T})}-G^{(\mathbb{T})}(G^{(\mathbb{T})}|_{W_{S}})^{-1}G^{(\mathbb{T})},P^{(W_{s})}=P-P(P|_{W_{S}})^{-1}P.$

We can explicitly write out our difference as,

(5.8) $\displaystyle G^{(\mathbb{T}\cup W_{S})}-P^{(W_{S})}$
$\displaystyle=[G^{(\mathbb{T})}-P]-[G^{(\mathbb{T})}-P](G^{(\mathbb{T})}|_{W_{S}})^{-1}G^{(\mathbb{T})}$
$\displaystyle-P[(G^{(\mathbb{T})}|_{W_{S}})^{-1}-(P|_{W_{S}})^{-1}]G^{(\mathbb{T})}-P(P|_{W_{S}})^{-1}[G^{(\mathbb{T})}-P].$

As before, one main issue would be to try to estimate the value of
$(G^{(\mathbb{T})}|_{W_{S}})^{-1}$

######  Lemma 5.5.

We have the following estimates on

$(P|_{W_{S}})_{ij}^{-1}-(G^{(\mathbb{T})}|_{W_{S}})_{ij}^{-1}\lesssim\epsilon^{\prime}(z,w).$

Furthermore, if we know that $i$ and $j$ are not Green’s function connected,
then we are able to get the superior estimate,

(5.9)
$|(P|_{W_{S}})_{ij}^{-1}-(G^{(\mathbb{T})}|_{W_{S}})_{ij}^{-1}|\lesssim\phi,$

for some constant $C$. We remark here that if $i$ and $j$ are not Green’s
function connected, then they would belong to different blocks of
$P|_{W_{S}}$. In this case, $[P|_{W_{S}}]_{ij}$ and $(P|_{W_{S}})^{-1}_{ij}$
are both zero.

###### Proof.

Again, we write,

(5.10) $\displaystyle(G^{(\mathbb{T})}|_{W_{S}})^{-1}=(P|_{W_{S}})^{-1}+E$
$\displaystyle G^{(\mathbb{T})}|_{W_{S}}=P|_{W_{S}}+J.$

Multiplying these equations, we again can derive that,

(5.11) $E=-(P|_{W_{S}})^{-1}J(P|_{W_{S}})^{-1}-EJ(P|_{W_{S}})^{-1}.$

Let us estimate the first term. We have,

(5.12) $|[(P|_{W_{S}})^{-1}J(P|_{W_{S}})^{-1}]_{ij}|\leq\sum_{a,b\in
W_{S}}|(P|_{W_{S}})^{-1}_{ia}||J_{ab}||(P|_{W_{S}})^{-1}_{bj}|.$

We can bound $|J_{ab}|\leq\epsilon^{\prime}(z)$. Furthermore, observe that
there are at most $2$ values $a$ such that $(P|_{W_{S}})^{-1}_{ia}$ is non-
zero and $2$ values $b$ such that $(P|_{W_{S}})^{-1}_{bj}$; this is due to our
assumption that the switched edges in $W_{S}$ are far apart from one another.
Furthermore, these values are $O(1)$ quantities; this can be shown be a direct
application of the Schur complement formula on a pure tree-like neighborhood
combined with some perturbation computations.

Let us define

$P_{\infty}:=G(Ext(B_{r}(\\{i,j\\}\cup
W_{S},\mathcal{G}\backslash\mathbb{T}),m_{\infty}(z,w),m_{\infty}(z,w))).$

By Lemma 3.4, one can show that

$||P|_{W_{S}}-P_{\infty}|_{W_{S}}||_{\infty}\ll 1.$

By $\infty$ norm here, we refer to the supremum over all entries. Furthermore,
since the vertices in $W_{S}$ are chosen so that they have tree-like
neighborhoods, we additionally have that $(P_{\infty}|_{W_{S}})^{-1}$ is
explicitly given by

$\begin{bmatrix}-z-\frac{d}{d-1}m_{\infty}(z,w)&w\\\
\overline{w}&-z-\frac{d}{d-1}m_{\infty}(z,w)\end{bmatrix},$

on each of its diagonal blocks. Clearly, all of these terms are $O(1)$. By the
same analysis we have done earlier, we can argue that
$||(P|_{W_{S}})^{-1}-(P_{\infty}|_{W_{S}})^{-1}||_{\infty}\ll 1$; this is
especially simple since we only have to consider only $2\times 2$ diagonal
blocks. This shows that the entries of $(P_{\infty}|_{W_{S}})^{-1}$ are of
$O(1)$, as desired.

Thus, the sum from equation (5.12) can be bounded by $C|J_{ab}|$ for the
unique possible values of $a$ and $b$ (if they exist), that return a non-zero
quantity in the computation
$|(P|_{W_{S}})^{-1}_{ia}||J_{ab}||(P|_{W_{S}})^{-1}_{bj}|$. This is due to the
fact that we have earlier shown that $|J_{ab}|\leq\epsilon^{\prime}(z,w)$ for
any pair $a$ and $b$.

Now, we estimate the second term from (5.11),

(5.13) $|\sum_{a,b}E_{ia}J_{ab}(P|_{W_{S}})^{-1}_{bj}|\leq
2(\sup_{ab}E_{ab})|W_{S}|\epsilon^{\prime}(z,w).$

We applied the triangle inequality and used the fact that
$(P|_{W_{S}})^{-1}_{bj}$ is zero for all values of $b$ except for $2$ of them.
We can bound $E_{ia}$ by the supremum over all values and $J_{ab}$ by
$\epsilon^{\prime}(z,w)$. Now, $|W_{S}|\epsilon^{\prime}(z,w)\ll 1$. Combining
this inequality and the previous one, we can derive the inequality,

(5.14)
$\sup_{ab}E_{ab}\leq(\sup_{ab}E_{ab})|W_{S}|\epsilon^{\prime}(z,w)+\epsilon^{\prime}(z,w).$

This would imply that $\sup_{ab}E_{ab}\leq 2\epsilon^{\prime}(z,w)$ as
desired.

With the estimate on the supremum in hand, we can improve our estimate for the
difference on terms that are not Green’s function connected. Observe, that we
can bound

(5.15)
$|\sum_{a,b}E_{ia}J_{ab}(P|_{W_{S}})^{-1}_{bj}|\leq(\sup_{ab}E_{ab})|W_{S}|\epsilon^{\prime}(z,w)\leq(\log
N)^{4\mathfrak{a}}\epsilon^{\prime}(z,w)^{2}\ll\phi.$

Furthermore, we have the following improvement when considering the first term
from equation (5.11).

(5.16) $\sum_{a,b\in
W_{S}}|(P|_{W_{S}})^{-1}_{ia}||J_{ab}||(P|_{W_{S}})^{-1}_{bj}|,$

Let $i$ correspond to one of $b_{\alpha},b_{\alpha}+N$ and and $j$ correspond
to one of $b_{\beta},b_{\beta}+N$, where $b_{\alpha}$ and $b_{\beta}$ are
vertices in $W_{S}$. The only non-zero terms $[(P|_{W_{S}})^{-1}]_{ia}$ has
$a=b_{\alpha}$ or $b_{\alpha}+N$ . Similarly, the only nonzero terms
$(P|_{W_{S}})^{-1}_{bj}$ has $b=b_{\beta}$ or $b_{\beta}+N$. For these
indices, we can apply the bound $|J_{ij}|\leq\phi$ due to our assumption that
$i$ and $j$ are not Green’s function connected. ∎

With this inequality in hand, we can start estimating the terms that appear in
equation (5.8). This will complete the proof of Proposition2.16.

###### Proof of 2.16.

The simplest term to estimate is the last one in equation (5.8).

Consider the following expression,

(5.17) $[P(P|_{W_{S}})^{-1}[G^{(\mathbb{T})}-P]]_{ij}=\sum_{a,b\in
W_{S}}|P_{ia}||(P|_{W_{S}})^{-1}_{ab}||[G^{(\mathbb{T})}-P]_{bj}|.$

Let $i$ correspond to one of $b_{\alpha},b_{\alpha}+N$ and $j$ correspond to
one of $b_{\beta},b_{\beta}+N$ for $b_{\alpha},b_{\beta}\in W_{S}$.

As we have argued before, due to the block diagonal structure of $P$, $P_{ia}$
is nonzero for at most $2$ values of $a$. These values can be $b_{\alpha}$ or
$b_{\alpha}+N$. Given this value of $a$, $(P|_{W_{S}})_{ab}^{-1}$ is nonzero
for at most $2$ values of $b$. This $b$ can still be only one of $b_{\alpha}$
or $b_{\alpha}+N$. Finally, we can apply the bound that
$|[G^{(\mathbb{T})}-P]_{bj}|\leq\epsilon^{\prime}(z,w)$ in general, or
$\leq\phi$ if $i$ and $j$ are not Green’s function connected.

Now, let us consider bounding the second term in equation (5.8). This is,

(5.18) $\sum_{a,b\in
W_{S}}|P_{ia}||[(P|_{W_{S}})^{-1}-(G^{(\mathbb{T})}|_{W_{S}})^{-1}]_{ab}||G^{(\mathbb{T})}|_{bj}.$

We first remark that since we know that
$|G^{(\mathbb{T})}_{bj}-P_{bj}|\leq\epsilon^{\prime}(z,w)$, this shows that
$|G^{(\mathbb{T})}|$ will have the worst case bound $O(1)$ for at most $2$
values of the index $b$ (those that are in the same block as $j$ in $P$).
There are a further $O(\log N)$ indices of $b$ where we would need to apply
the worst case bound $|G^{(\mathbb{T})}|_{bj}\leq\epsilon^{\prime}(z,w)$ and
$P_{bj}=0$. Finally, we can bound the Green’s function for all remaining
indices as $|G^{(\mathbb{T})}|_{bj}\leq\phi$, due to our assumption that the
indices are not Green’s function connected.

Further, we also know that for each fixed index $a$, there are at most $O(\log
N)$ indices where we would need to apply the worst case bound
$|[(P|_{W_{S}})^{-1}-(G^{(\mathbb{T})}|_{W_{S}})^{-1}]_{ab}|\leq\epsilon^{\prime}(z,w)$.
These are the indices that $a$ is Green’s function connected to $b$.
Otherwise, we could apply the bound $\phi$. As before, $|P_{ia}|$ is $0$ for
all except for $2$ possible indices $a$.

Now, consider the case that $i$ is not Green’s function connected to $j$.
Then, if $b$ is one of the two indices connected to $j$ in $W_{S}$, then we
would have the improved bound
$|[(P|_{W_{S}})^{-1}-(G^{(\mathbb{T})}|_{W_{S}})^{-1}]_{ab}|\leq\phi$ for
these indices $b$ and all indices $a$ such that $|P_{ia}|\neq 0$.

Thus, we would derive the bound,

$\displaystyle\sum_{a,b\in
W_{S}}|P_{ia}||[(P|_{W_{S}})^{-1}-(G^{(\mathbb{T})}|_{W_{S}})^{-1}]_{ab}||G^{(\mathbb{T})}|_{bj}$
$\displaystyle\lesssim\phi+\log N(\epsilon^{\prime}(z,w))^{2}+\log
N|W_{S}|\epsilon^{\prime}(z,w)\phi(z)+|W_{S}|^{2}\phi.$

Similar techniques allow us to treat the first term in equation (5.8). ∎

##  6\. Relating $G^{(\mathbb{T}\cup W_{S})}$ to $\tilde{G}^{(\mathbb{T})}$ of
the switched graph: Proof of Proposition 2.17

As in the previous sections, we will prove Proposition 2.16 by applying the
Schur complement formula and other Green’s function manipulations. Since we
are adding vertices back into the graph, we will have slightly different
formulas for $\tilde{G}_{ij}^{(\mathbb{T})}$ from $G_{ij}^{(\mathbb{T}\cup
W_{S})}$ depending on whether $i$ or $j$ is in $W_{S}$ or not. The full
conclusion of Proposition 2.16 can be derived from the conclusions of Lemmas
6.1, 6.3, and 6.4.

We consider $P$ given by $G(Ext(B_{r}(\\{i,j\\}\cup
W_{S},\tilde{\mathcal{G}}\backslash\mathbb{T}),Q_{I},Q_{O}))$ where
$\tilde{\mathcal{G}}$ is the graph obtained by switching the edges associated
to the switching set $W_{S}$. We observed that
$P^{(W_{S})}=G(Ext(B_{r}(\\{i,j\\}\cup(\mathbb{T}\cup
W_{S}),\mathcal{G}\backslash\mathbb{T}),Q_{I},Q_{O}))$. Namely, $P^{(W_{S})}$
is exactly the Green’s function we were relating $G$ to in the previous
section.

In this section we will apply the Schur complement formula in the form,

(6.1)
$\displaystyle\tilde{G}^{(\mathbb{T})}|_{W_{S}}=(A-\tilde{B}G^{(\mathbb{T}\cup
W_{S})}\tilde{B}^{*})^{-1},$ $\displaystyle
P|_{W_{S}}=(A-\tilde{B}P^{(W_{S})}\tilde{B}^{*})^{-1},$

where $\tilde{B}$ represents the adjacency matrix between the vertices of
$W_{S}$ to those outside of $W_{S}$.

The Schur complement formula give us

(6.2) $\displaystyle\tilde{G}^{(\mathbb{T})}|_{W_{S}\times
W_{S}^{c}}=-\tilde{G}^{(\mathbb{T})}|_{W_{S}}\tilde{B}G^{(\mathbb{T}\cup
W_{S})}$ $\displaystyle P|_{W_{S}\times
W_{S}^{c}}=-P|_{W_{S}}\tilde{B}P^{(W_{S})},$

and an application of the resolvent identity would give us,

(6.3) $\displaystyle\tilde{G}^{(\mathbb{T})}|_{W_{S}^{c}\times
W_{S}^{c}}=G^{(\mathbb{T}\cup W_{S})}+G^{(\mathbb{T}\cup
W_{S})}\tilde{B}^{*}\tilde{G}^{(\mathbb{T})}|_{W_{S}}\tilde{B}G^{(\mathbb{T}\cup
W_{S})}$ $\displaystyle
P=P^{(W_{S})}+P^{(W_{S})}\tilde{B}^{*}P|_{W_{S}}\tilde{B}P^{(W_{S})}.$

We see first that it is crucial to understand the difference of
$\tilde{G}^{(\mathbb{T})}$ and $P$ on the set $W_{S}$ at the first step. This
can be done by the resolvent identity,

(6.4)
$\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}}=\tilde{G}^{(\mathbb{T})}|_{W_{S}}\tilde{B}(P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})})\tilde{B}^{*}P|_{W_{S}}.$

We can estimate the maximum difference of the right hand side.

######  Lemma 6.1.

For any two indices $i$ and $j$ corresponding to vertices in $W_{S}$, we have,

(6.5)
$|[\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}}]_{ij}|\lesssim\epsilon^{\prime}(z,w).$

Furthermore, if $i$ and $j$ correspond to vertices that are not Green’s
function connected, then we have the improved bound,

(6.6) $|[\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}}]_{ij}|\lesssim\phi.$

.

###### Proof.

Let $\Gamma:=\max_{i,j\in
W_{S}}|[\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}}]_{ij}|.$ Using this
definition inside (6.4), we would derive the relation,

(6.7) $\displaystyle|[\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}}]_{ij}|$
$\displaystyle=([\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}}]\tilde{B}(P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})})\tilde{B}^{*}P|_{W_{S}})_{ij}$
$\displaystyle+(P|_{W_{S}}\tilde{B}(P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})})\tilde{B}^{*}P|_{W_{S}})_{ij}.$

Let $i$ correspond to one of the indices $b_{\alpha}$ or $b_{\alpha}+N$ and
let $j$ correspond to one of the indices $b_{\beta}$ or $b_{\beta}+N$, where
$b_{\alpha}$ and $b_{\beta}$ are vertices that belong to $b_{\beta}$

The first quantity on the right hand size can be bounded by $(\log
N)^{8\mathfrak{a}}\epsilon^{\prime}\Gamma\ll\Gamma$. We write the second term
on the right hand side as,

(6.8) $\displaystyle(P|_{W_{S}}\tilde{B}(P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})})\tilde{B}^{*}P|_{W_{S}})_{ij}$
$\displaystyle=\sum_{x,y,z,w}(P|_{W_{S}})_{ix}\tilde{B}_{xy}(P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})})_{yz}(\tilde{B}^{*})_{zw}(P|_{W_{S}})_{wj}.$

For the second quantity on the right hand size, we remark that
$[P|_{W_{S}}]_{ix}=1$ only if $x$ corresponds to one of the indices
$b_{\alpha}$ or $b_{\alpha}+N$. This is due to the fact that $b_{\alpha}$ and
$b_{\beta}$ for $\alpha\neq\beta$ are still far apart even after $b_{\alpha}$
is connected to $l_{\alpha}$ for all $\alpha$ in $W_{S}$. Thus, $P|_{W_{S}}$
is still a diagonal matrix. Similarly, $w$ must be one of $b_{\beta}$ or
$b_{\beta}+N$ if $(P|_{W_{S}})$ were to be non-zero. Since $B$ and
$B^{\prime}$ are the adjacency matrices for $d$-regular graphs, this would
further imply that there are only finitely many values that $y$ could take and
finitely many values that $z$ could take. By our choice of the construction,
we would know that these $y$ vertices and these $z$ vertices would all have a
local treelike neighborhood.

Since we have the bound $|P^{(W_{S})}_{cd}-G^{(\mathbb{T}\cup
W_{S})}_{cd}|\leq 2\epsilon^{\prime}(z,w)$ for any generic pair $c$,$d$ that
has a tree-like neighborhood, we would apply this bound everywhere and observe
that,

(6.9)
$\sum_{x,y,z,w}(P|_{W_{S}})_{ix}\tilde{B}_{xy}(P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})})_{yz}(\tilde{B}^{*})_{zw}(P|_{W_{S}})_{wj}\lesssim
C\epsilon^{\prime}(z,w).$

From this point, a standard maximum principle argument completes the the proof
of the bound on $P-G$ for general $i$ and $j$.

If $i$ and $j$ are not Green’s function connected, the only observation we
need is that we can improve the bound on $|P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})|}$ in equation (6.9) to $\phi$. The first term in equation (6.7) can be
bounded by $\epsilon^{\prime 2}\ll\phi$. ∎

We can apply these estimates in order to understand the differences of
$\tilde{G}^{(\mathbb{T})}$ and $P$ on the rectangular sub-matrix $W_{S}\times
W_{S}^{c}$. The following lemma encompasses this information. However, we
mention that some of these estimates can improve if we instead consider some
Green’s function connected information on the specific vertices
$\\{c_{\alpha},b_{\alpha}\\}$ that take part in the switching. We introduce a
definition to encompass this information.

######  Definition 6.2.

We define a new set $U$ of switched vertices $b_{\alpha},c_{\alpha}$ that
satisfy some specific properties. The vertices $b_{\alpha},c_{\alpha}$ are
included in the set $U$ if the following properties are satisfied:

  1. (1)

For $\beta\neq\alpha$, the set of vertices $\\{b_{\beta},c_{\beta}\\}$ is not
Green’s function connected to $\\{b_{\alpha},c_{\alpha}\\}$.

  2. (2)

The $\mathfrak{R}$ neighborhood around $c_{\alpha}$ in
$\mathcal{G}\backslash\mathbb{T}$ is tree-like.

######  Lemma 6.3.

Let $i$ and $j$ be two vertices: $i$ belonging to $W_{S}$ and $j$ belonging to
$W_{S}^{c}$. Then, we have the following comparison bound,

(6.10) $|\tilde{G}^{(\mathbb{T})}_{ij}-P_{ij}|\lesssim\epsilon^{\prime}(z,w).$

Recall our notation $\\{a_{\alpha},b_{\alpha},c_{\alpha}\\}$ for the types of
vertices that participate in the switching. Assume that $j$ is $c_{\alpha}$
for $c_{\alpha}$ a vertex in $U$ and that $i=b_{\beta}$ for $\beta\neq\alpha$.

(6.11)
$|\tilde{G}^{(\mathbb{T})}_{b_{\beta}c_{\alpha}}-P_{b_{\beta}c_{\alpha}}|\lesssim\phi+(\epsilon^{\prime})^{2}.$

###### Proof.

General Case:

We start with the identity,

(6.12) $\tilde{G}^{(\mathbb{T})}|_{W_{S}\times W_{S}^{c}}-P|_{W_{S}\times
W_{S}^{c}}=[P|_{W_{S}}-\tilde{G}^{(\mathbb{T})}|_{W_{S}}]\tilde{B}G^{(\mathbb{T}\cup
W_{S})}+P|_{W_{S}}\tilde{B}[P^{(W_{S})}-G^{(\mathbb{T}\cup W_{S})}].$

Let us first deal with the second term
$(P|_{W_{S}}\tilde{B}[P^{(W_{S})}-G^{(\mathbb{T}\cup W_{S})}])_{ij}$. We have,

(6.13) $(P|_{W_{S}}\tilde{B}[P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})}])_{ij}=\sum_{x,y}(P|_{W_{S}})_{ix}\tilde{B}_{xy}[P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})}]_{yj}.$

Now, $(P|_{W_{S}})_{ix}$ can only be non-zero only when $x$ is one of the
indices corresponding to the same vertex as $i$. Thus, there are finitely many
choices for $y$ and all of these $y$ vertices have tree-like neighborhoods. We
can finally apply the bound that $[P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})}]_{yj}$ is less than $2\epsilon^{\prime}(z,w)$.

We can deal with the first term in a similar way, by first writing,

(6.14)
$[P|_{W_{S}}-\tilde{G}^{(\mathbb{T})}|_{W_{S}}]\tilde{B}G^{(\mathbb{T}\cup
W_{S})}=[P|_{W_{S}}-\tilde{G}^{(\mathbb{T})}|_{W_{S}}]\tilde{B}P^{(W_{S})}+[P|_{W_{S}}-\tilde{G}^{(\mathbb{T})}|_{W_{S}}]\tilde{B}[G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})}].$

The second term is quadratic in the error $\epsilon^{\prime}(z,w)^{2}$ and can
compensate for any factor of the form $(\log N)^{4\mathfrak{a}}$ that might
appear. The first term above can be dealt with the exact same way as the
previous bound we considered in this proof.

Specific Case of $i=c_{\alpha}$ and $j=b_{\beta}$ with $\beta\neq\alpha$:

We can apply the same identity detailed in (6.12). We do not need to consider
the contribution of terms with two factors of $G-P$ (as these will give an
error of the form $(\epsilon^{\prime})^{2}$.) There are two terms remaining
using only a single factor of the form $G-P$ and the analysis of both of these
terms is very similar.

Let us consider the term,

(6.15) $(P|_{W_{S}})_{b_{\beta}x}\tilde{B}_{xy}[P^{(W_{S})}-G^{(\mathbb{T}\cup
W_{S})}]_{yc_{\alpha}}.$

We abuse notation slightly as we let $b_{\beta},c_{\alpha}$ refer to any of
the two indices that correspond to the vertex $b_{\beta},c_{\alpha}$ rather
than the vertex itself. Since $P|_{W_{S}}$ is diagonal, $x$ again has to be an
index corresponding to $b_{\beta}$. In addition, $y$ has to correspond to a
vertex adjacent to $b_{\beta}$ using the adjacency properties of the matrix
$\tilde{B}$. Finally, in the last term, we use the fact that $y=b_{\beta}$ and
$c_{\alpha}$ are no longer Green’s function connected to bound
$[P^{(W_{S})}-G^{(\mathbb{T}\cup W_{S})}]_{yc_{\alpha}}$ by $\phi$. This shows
that the above term is bounded by a constant multiple of $\phi$, as desired. ∎

At this point, we can finally continue and prove bounds of the difference when
the indices $i$ and $j$ are both in $W_{S}^{c}$. Furthermore, we can prove
superior bounds on some Green’s function entries if we take into account the
Green’s function connectivity properties.

######  Lemma 6.4.

Let $i$ and $j$ be vertices in $W_{S}^{c}$ in
$\tilde{\mathcal{G}}\backslash\mathbb{T}$. We have the following general
estimate on Green’s function bounds,

(6.16) $|\tilde{G}_{ij}^{(\mathbb{T})}-P_{ij}|\lesssim\epsilon^{\prime}(z,w).$

Recall the notation $c_{\alpha},b_{\alpha},a_{\alpha}$ for the vertices that
participate in the switching. Let $c_{\alpha}$ be a vertex in $U$ and let $j$
be a vertex that is not Green’s function connected to
$\\{c_{\alpha},b_{\alpha}\\}$ in $\mathcal{G}\backslash\mathbb{T}$. Then, we
would have the bound,

(6.17) $|\tilde{G}_{ij}^{(\mathbb{T})}-P_{ij}|\lesssim\phi.$

###### Proof.

General Case:

We see we can write the difference between $\tilde{G}^{(\mathbb{T})}$ and $P$
on $W_{S}^{c}\times W_{S}^{c}$ as,

(6.18) $\displaystyle G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})}+(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})\tilde{B}^{*}P|_{W_{S}}\tilde{B}P^{(W_{S})}$
$\displaystyle+P^{(W_{S})}\tilde{B}^{*}(\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}})\tilde{B}P^{(W_{S})}+P^{(W_{S})}\tilde{B}^{*}P|_{W_{S}}\tilde{B}(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})$ $\displaystyle+(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})\tilde{B}^{*}(\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}})\tilde{B}P^{(W_{S})}$
$\displaystyle+(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})\tilde{B}^{*}P|_{W_{S}}\tilde{B}(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})$ $\displaystyle+(G^{(\mathbb{T}\cup
W_{S}})-P^{(W_{S})})\tilde{B}^{*}(\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}})\tilde{B}(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})$
$\displaystyle+P^{(W_{S})}\tilde{B}^{*}(\tilde{G}^{(\mathbb{T})}|_{W_{S}}-P|_{W_{S}})\tilde{B}(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})$

The terms that involve two differences of $G-P$ would have an error of at most
quadratic order in $\epsilon^{\prime 2}$. This is already much smaller than
$\epsilon^{\prime}$, even with prefactors of the form $(\log
N)^{4\mathfrak{a}}$. To derive the worst case bound that is of order
$\epsilon^{\prime}$, it suffices to understand the term $[(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})\tilde{B}^{*}P|_{W_{S}}\tilde{B}P^{(W_{S})}]_{ij}$, which
we will write as,

(6.19) $\sum_{x,y,z,w}(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})_{ix}(\tilde{B}^{*})_{xy}(P|_{W_{S}})_{yz}(\tilde{B})_{zw}(P^{(W_{S})})_{wj}.$

In the general case, $P^{(W_{S})}_{wj}$ can be nonzero for at most $2d$ values
of $w$ given $j$ (There is at most 1 switched vertex $b_{\alpha}$ such that
$b_{\alpha}$ and $j$ are in the same radius $r$ neighborhood. Furthermore,
there are at most $d$ neighbors $w$ of this $b_{\alpha}$ that would belong to
the same block of $P^{(W_{S})}_{wj}$.) The only nontrivial choice of $z$ is an
index corresponding to this vertex $b_{\alpha}$. Since $P|_{W_{S}}$ is
diagonal, the vertex $y$ must also correspond to $b_{\alpha}$. Finally, there
can be at most $2d$ choices for $x$ ( the vertices adjacent to $b_{\alpha}$).
Thus, we have a finite number of choice for $x,y,z$ and $w$ that give nonzero
values. We can bound $(G^{(\mathbb{T}\cup W_{S})}-P^{(W_{S})})_{ix}$ by
$\epsilon^{\prime}$ for every $x$ in this finite set. In general, we see this
term is bounded by $C\epsilon^{\prime}$. The analysis of terms involving only
a single factor of $G-P$ is similar. Other terms involving two $G-P$’s will be
squared and have decay at least $(\epsilon^{\prime})^{2}$.

Specific case of $i=c_{\alpha}$ and $j$ being Green’s function separated

Now, we give the superior analysis in the case that $i$ is the vertex
$c_{\alpha}$ for some $\alpha$. These superior estimates are necessary when we
reintroduce the tree $\mathbb{T}$ into the switched graph
$\tilde{\mathcal{G}}\backslash\mathbb{T}$.

Let us first consider the case that $j$ is not Green’s function connected to
the vertex $c_{\alpha}$ and that the distance of $j$ to $a_{\alpha}$ is
greater than $r$ in $\tilde{\mathcal{G}}\backslash\mathbb{T}$. We use the same
expansion detailed in equation (6.18). As before, we mention that those terms
that involve two factors of $G-P$ will incur a factor of
$(\epsilon^{\prime})^{2}\ll\phi$. This means that we will only have to deal
with the contributions from those terms involving a single $G-P$ factor. It
would suffice as before to deal with one such term; the analysis from the
contribution of the other terms would be very similar.

Let us consider the term,

(6.20) $\sum_{x,y,z,w}(G^{(\mathbb{T}\cup
W_{S})}-P^{(W_{S})})_{c_{\alpha}x}(\tilde{B}^{*})_{xy}(P|_{W_{S}})_{yz}(\tilde{B})_{zw}(P^{(W_{S})})_{wj}.$

As before, we know that the matrices $P$ are block diagonal. Thus,
$(P^{(W_{S})})_{wj}$ can be non-zero only in the following case. First, we
find the single vertex $b_{\beta}$ that is in the radius $r$ neighborhood of
$j$; by our assumption that $j$ is not Green’s function connected to
$b_{\beta},c_{\beta}$ in $\mathcal{G}$ and that the distance from $j$ to
$b_{\alpha}$ is greater than $r$ in $\tilde{\mathcal{G}}$, we know that
$\beta$ cannot equal $\alpha$. Finally, the only non-trivial values of $w$ are
those indices corresponding to vertices adjacent to $b_{\beta}$. Furthermore,
we see that $y$ and $z$ can only be one of the indices corresponding to the
vertex $b_{\beta}$; for $z$, this comes from the matrix $\tilde{B}$, while for
$y$ it comes from the diagonal matrix $P|_{W_{S}}$. Now, we can say that $x$
is an index corresponding to one of the vertices adjacent to $b_{\beta}$.
Finally, we can use the fact that $c_{\alpha}$ and $b_{\beta}$ are not Green’s
function connected to bound $|G^{(\mathbb{T}\cup W_{S})}-P^{(W_{S})}|$ by
$\phi$. This shows that the above term considered is necessarily less than
some multiple of $\phi$, as desired. ∎

##  7\. Reintroduction of the tree and relating $\tilde{G}^{(\mathbb{T})}$ to
$\tilde{G}$:Proof of Proposition 2.18

As we have done previously, our basic step is to apply the Schur complement
formula and resolvent estimates in order to treat the removal of the subset
$\mathbb{T}$. We make one important remark before proceeding. At the first
step, it is easier to compare $\tilde{G}$ with extensions involving the
parameters $Q_{I}$ and $Q_{O}$ for the original graph $\mathcal{G}$. Lemmas
7.1 and 7.3 do exactly this. It is only later in Lemma 7.4 where we consider
the difference between $Q_{I}$ and $\tilde{Q}_{I}$. A simple perturbation
bound as from Theorem 1.11will complete the proof.

We will decompose the adjacency matrix as,

(7.1) $\tilde{G}^{-1}=\begin{bmatrix}A&B\\\ B^{*}&D\end{bmatrix},$

where $A$ will be the adjacency matrix of the neighborhood $\mathbb{T}$ and
$B$ contains the adjacency information of the boundary of $\mathbb{T}$ and the
vertices they were switched with.

As we have done previously, we will relate the element $\tilde{G}_{ij}$ to the
term $P_{ij}$, where $P$ is defined to be
$G(\text{Ext}(B_{r}(\\{i,j\\}\cup\mathbb{T},\tilde{\mathcal{G}}),Q_{I},Q_{O}))$.
We see that $P^{-1}$ has the adjacency matrix,

(7.2) $P^{-1}=\begin{bmatrix}A&B\\\ B^{*}&D^{\prime}\end{bmatrix}.$

The inverse of the matrix $D^{\prime}$( will be
$G(\text{Ext}(B_{r}(\\{i,j\\}\cup\mathbb{T},\tilde{\mathcal{G}}^{(\mathbb{T})}),Q_{I},Q_{O}))$,
which we have analyzed in the previous section. Here, $B_{r}(\mathbb{T})$
should be understood as the $r$ neighborhood of $\mathbb{T}$ in $\mathcal{G}$
restricted to $\mathbb{T}^{c}$.

For vertices $i$ and $j$ inside $\mathbb{T}$, we can apply the Schur
complement formula and derive,

(7.3)
$\displaystyle\tilde{G}|_{(\mathbb{T})}=(A+B\tilde{G}^{(\mathbb{T})}B^{*})^{-1}$
$\displaystyle P|_{(\mathbb{T})}=(A+BP^{(\mathbb{T})}B^{*})^{-1}.$

We can now use the resolvent formula to compute the difference,

(7.4)
$\tilde{G}|_{(\mathbb{T})}-P|_{(\mathbb{T})}=P|_{(\mathbb{T})}B(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})B^{*}P+(\tilde{G}|_{(\mathbb{T})}-P|_{(\mathbb{T})})B(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})B^{*}.$

Our formal statement on the value of the difference is as follows.

######  Lemma 7.1.

Let $i$ and $j$ be two points found in our neighborhood $\mathbb{T}$. Let
$d_{i}$ denote the distance from $i$ to the root and $d_{j}$ denote the
distance between $j$ and the root. We have the following estimates,

(7.5)
$|\tilde{G}|_{(\mathbb{T})}-P|_{(\mathbb{T})}|\lesssim\epsilon^{\prime}(\log
N)^{2}\Big{(}\frac{1}{\sqrt{d-1}}\Big{)}^{2\ell-
d_{i}-d_{j}}+(1+|d_{j}+d_{i}|)\Big{(}\frac{1}{d-1}\Big{)}^{\frac{|d_{j}-d_{i}|}{2}}\epsilon^{\prime}.$

######  Remark 7.2.

The second error term on the right hand side of (7.5) has the issue that it
does not have a decay of the power $\left(\frac{1}{d-1}\right)^{\ell}$. By
contrast, the first error term on the right hand side of $(\ref{eq:StabEst})$
has the power of $(d-1)^{-2\ell}$, which can suppress powers of $\log$ as long
as we ensure that $d_{i}$ and $d_{j}$ are small relative to $\ell$.

###### Proof.

The computations of the previous section show that entries of
$(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})$ are all bounded by
$C\epsilon^{\prime}(z,w)$ and a few other terms have superior bounds.

We have for (7.4), that

(7.6)
$\displaystyle(PB(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})B^{*}P)_{ij}$
$\displaystyle\leq\frac{1}{d-1}\sum_{l_{\alpha},l_{\beta}}P_{i,l_{\alpha}}(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})_{\tilde{c}_{\alpha},\tilde{c}_{\beta}}P_{l_{\beta},j}$
$\displaystyle\leq\frac{1}{d-1}\sum_{\alpha}P_{i,l_{\alpha}}P_{l_{\alpha},j}(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})_{\tilde{c}_{\alpha},\tilde{c}_{\alpha}}$
$\displaystyle+\frac{1}{d-1}\sum_{\alpha\neq\beta}P_{i,l_{\alpha}}P_{l_{\beta},j}(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})_{\tilde{c}_{\alpha},\tilde{c}_{\beta}}.$

$\alpha$ enumerates the vertices on the boundary of $(\mathbb{T})$. In a
slight abuse of notation, $l_{\alpha}$ and $c_{\alpha}$ actually represent the
possible indices corresponding to the vertices on the boundary rather than the
vertices themselves; we hope that this usage of notation is clear in context.
The sum is split into two parts that will have different estimates based on
whether $\alpha$ is equal to $\beta$ or not. When $\alpha\neq\beta$ we will be
able to get superior estimates when we use the separation of Green’s function
distance.

Let us now treat the second term on which $\alpha\neq\beta$. This can be
divided even further based on whether we are considering an index from the set
$U$ from Definition 6.2. For $\alpha$ corresponding to a vertex in $U$, we can
use the fact that
$|(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})_{\tilde{c}_{\alpha},\tilde{c}_{\beta}}|\leq\phi$.
There are $O((\log N)^{2})$ that have both of their entries from outside $U$.
Furthermore, we can use the bound
$|P_{i,l_{\alpha}}|\leq\left(\frac{1}{\sqrt{d-1}}\right)^{\ell-d_{i}}$.
Applying this, we see that we have the following bound on our cross terms,

(7.7)
$\frac{\phi}{d-1}\sum_{\alpha\neq\beta}|P_{i,l_{\alpha}}||P_{l_{\beta},j}|+\frac{\epsilon^{\prime}(\log
N)^{2}}{d-1}\left(\frac{1}{\sqrt{d-1}}\right)^{\ell-
d_{i}}\left(\frac{1}{\sqrt{d-1}}\right)^{\ell-d_{j}}$

For the terms that are not cross terms ( with $\alpha=\beta$), we merely apply
the bound that
$|\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})}|\leq\epsilon^{\prime}$.

We see that our full bound on the left hand side of equation (7.6) is the
following,

(7.8)
$\displaystyle\frac{\epsilon^{\prime}}{d-1}\sum_{\alpha}|P_{i,l_{\alpha}}||P_{l_{\alpha},j}|+\frac{\phi}{d-1}\sum_{\alpha\neq\beta}|P_{i,l_{\alpha}}||P_{l_{\beta},j}|+\frac{\epsilon^{\prime}(\log
N)^{2}}{d-1}\left(\frac{1}{\sqrt{d-1}}\right)^{\ell-
d_{i}}\left(\frac{1}{\sqrt{d-1}}\right)^{\ell-d_{j}}$

Lemma 4.5 assures us $\sum_{\alpha}|P_{i,l_{\alpha}}|\leq(\log
n)^{\mathfrak{j(d)}\mathfrak{a}}$. Thus, we see that

$\phi\sum_{\alpha\neq\beta}|P_{i,l_{\alpha}}||P_{l_{\beta},j}|\frac{(d-1)^{(2\ell-
d_{i}-d_{j})/2}}{(d-1)^{(2\ell-d_{i}-d_{j})/2}}\leq\frac{\phi(\log
N)^{2\mathfrak{j}(d)\mathfrak{a}+4\mathfrak{a}}}{(d-1)^{(2\ell-
d_{i}-d_{j})/2}}.$

Now, since $\phi\ll\epsilon(\log N)^{-K\mathfrak{a}/2}$, we see that for
sufficiently large, but still finite, values of $d$ we can show that the
factor on the numerator is still less than $\epsilon$.

We finally need to find a bound on
$\sum_{\alpha}|P_{i,l_{\alpha}}||P_{l_{\alpha},j}|$ that depends on the
distance between $i$ and $j$ in $\mathbb{T}$. From the proof of Lemma 3.4, we
see that this decay factor is
$\lesssim(1+\text{dist}(i,j))\left(\frac{1}{\sqrt{d-1}}\right)^{\text{dist}(i,j)}$.
Just to give a brief summary of the method here, we use the factor that
$|P_{i,l_{\alpha}}|$ and $|P_{l_{\alpha},j}|$ can decompose as a product based
on the edges of the path connecting $i$ to $l_{\alpha}$ and $l_{\alpha}$ to
$j$ respectively. Let $r$ be the first common point of these paths.

The product $|P_{i.l_{\alpha}}||P_{l_{\alpha},j}|$ roughly decomposes as
$K_{i,r}K_{r,j}|P_{r,l_{\alpha}}|^{2}$, where $K_{i,r}$ and $K_{r,j}$ are two
quantities that depend on the path between $i$ to $r$ and $j$ to $r$
respectively. A naive bound on $K_{i,r}$ is
$\left(\frac{1}{\sqrt{d-1}}\right)^{\text{dist}(i,r)}$, while a naive bound on
$K_{r,j}$ is $\left(\frac{1}{\sqrt{d-1}}\right)^{\text{dist}(r,j)}$. The
product of these two terms gives the decay
$\left(\frac{1}{\sqrt{d-1}}\right)^{\text{dist}(i,j)}$.

If we fix $r$ and sum over all $l_{\alpha}$ that would be possible descendants
or $r$, the computations in Lemma 3.4 show that
$\sum_{l_{\alpha}}|P_{rl_{\alpha}}|^{2}$ is $O(1)$. Finally, there are
$1+\text{dist}(i,j)$ choices for the first common point $r$. This is the basic
strategy that bound $\sum_{\alpha}|P_{i,l_{\alpha}}||P_{l_{\alpha},j}|$ and
finishes the proof of our bound. ∎

To complete this section, we also include estimates on the differences
$|\tilde{G}_{ij}-P_{ij}|$ when at least one of $i$ and $j$ are outside of
$\mathbb{T}$. First consider the case that $i$ is in $\mathbb{T}$ and $j$ is
in $\mathbb{T}^{c}$. Applying the resolvent identity, we have
$\tilde{G}|_{\mathbb{T}\times\mathbb{T}^{c}}=\tilde{G}|_{\mathbb{T}}B\tilde{G}^{(\mathbb{T})}$.

######  Lemma 7.3.

Let $i$ be a vertex in $\mathbb{T}$ and $j$ be a vertex in $\mathbb{T}^{c}$.
We have the following estimate on $\tilde{G}_{ij}-P_{ij}$.

(7.9)
$|\tilde{G}_{ij}-P_{ij}|\lesssim(logN)^{2}\epsilon^{\prime}\left(\frac{1}{\sqrt{d-1}}\right)^{\ell-
d_{i}}.$

###### Proof.

Applying the resolvent identity and taking the difference, we have,

(7.10)
$\tilde{G}|_{\mathbb{T}\times\mathbb{T}^{c}}-P|_{\mathbb{T}\times\mathbb{T}^{c}}=(G|_{\mathbb{T}}-P|_{\mathbb{T}})BP^{(\mathbb{T})}+P|_{\mathbb{T}}B(G^{(\mathbb{T})}-P^{(\mathbb{T})})+(G|_{\mathbb{T}}-P|_{\mathbb{T}})B(G^{(\mathbb{T})}-P^{(\mathbb{T})}).$

As before, the term with two factors of the form $(G-P)$ would give an error
of the form $(\epsilon^{\prime})^{2}$, which is far smaller than any main term
error we might have to consider.

Now, let us analyze the first term; writing out the indices, it will be,

(7.11)
$\sum_{\alpha}(G|_{\mathbb{T}}-P|_{\mathbb{T}})_{i,l_{\alpha}}P^{(\mathbb{T})}_{\tilde{c}_{\alpha},j}.$

We first remark that $P^{(\mathbb{T})}$ is a diagonal matrix and that $j$
would belong to a block containing at most $O(1)$ elements
$\tilde{c}_{\alpha}$. Thus, $P^{(\mathbb{T})}_{\tilde{c}_{\alpha},j}$ would be
zero for all except for $O(1)$ many elements. Now, we can apply the estimate
from equation (7.5) in order to bound the first error term
$(G|_{\mathbb{T}}-P|_{\mathbb{T}})$.

Now, let us analyze the second error term. Again, in terms of coordinates, we
have,

(7.12)
$\sum_{\alpha}(P|_{(\mathbb{T})})_{il_{\alpha}}(G^{(\mathbb{T})}-P^{(\mathbb{T})})_{\tilde{c}_{\alpha},j}.$

Again, we have to apply the logic of connectedness. We first remark that $j$
cannot be Green’s function connected to more than $O(\log N)$ vertices of the
form $c_{\alpha}$ by the construction of our switching event. For all
$c_{\alpha}$ to which $j$ is not Green’s function connected, we apply the
improved bound
$|G^{(\mathbb{T})}-P^{(\mathbb{T})}|\leq(\epsilon^{\prime})^{2}+\phi$. For the
other $O(\log N)$ terms, we merely use the error bound $\epsilon^{\prime}$
instead.

Our total error can be bounded by,

(7.13)
$\sum_{\alpha}|(P|_{(\mathbb{T})})_{il_{\alpha}}|((\epsilon^{\prime})^{2}+\phi)+C\log
N\left(\frac{1}{\sqrt{d-1}}\right)^{\ell-d_{i}},$

where $d_{i}$ is the distance of the vertex $i$ from the center of the tree
$\mathbb{T}$. From Lemma A.2, we can bound
$\sum_{\alpha}|(P|_{(\mathbb{T})})_{il_{\alpha}}|(d-1)^{\ell/2}\leq(\log
N)^{\mathfrak{j}(d)\mathfrak{a}+\mathfrak{a}/2}$. Even after multiplying this
constant by $\phi$, we obtain a value that is less than $\epsilon$. Therefore,
the error coming from this term is still less than $C\log
N\left(\frac{1}{\sqrt{d-1}}\right)^{\ell-d_{i}}$. ∎

###  7.1. Changing $Q_{I/O}$ to $\tilde{Q}_{I/O}$

Our stability estimates are finally enough to understand the shift of
$\mathcal{G}$ to $\tilde{\mathcal{G}}$ for $Q_{I}$ and $Q_{O}$. The proofs of
these two quantities are similar, so we will only prove the results for the
shift of $Q_{I}$.

######  Lemma 7.4.

We have that,

(7.14)
$|Q_{I/O}(\mathcal{G})-\tilde{Q}_{I/O}|\lesssim\frac{1}{N^{1-\mathfrak{c}}}+(2d-1)^{2\ell}\frac{\text{Im}[m_{\mathcal{T}}^{d}(z,w)]+\epsilon^{\prime}+\frac{\epsilon}{S_{g}^{1}}}{N\eta}.$

###### Proof.

Clearly, once we remove the neighborhood $\mathbb{T}$ and switching set
$W_{S}$, the graphs $\mathcal{G}$ and $\tilde{\mathcal{G}}$ are the same.
Thus, our goal is to relate terms of the form $G^{(i)}_{jj}$ to those of the
form $G^{(\\{i\\}\cup\mathbb{T}\cup W_{S})}_{jj}$ via resolvent estimates. We
will use $i\mathbb{T}W_{S}$ as a shorthand for set $\\{i\\}\cup\mathbb{T}\cup
W_{S}$. Let $\chi(\cdot)$ be the characteristic function indicating whether
the vertex in question is of at least distance $\frac{\mathfrak{R}}{4}$ away
from any of the vertices $a_{\alpha},b_{\alpha},c_{\alpha}$ that take part in
the switching and, furthermore, $j$ has a radius $\frac{\mathfrak{R}}{4}$
tree-like neighborhood. We note that there are $\ll N^{\mathfrak{c}}$ vertices
$j$ such that $\chi(j)\neq 1$.

Namely, our goal is to prove the following two inequalities,

(7.15) $\displaystyle\frac{1}{Nd}\sum_{j\to
i}\chi(j)|G_{jj}^{(i)}-G_{jj}^{(i\mathbb{T}W_{S})}|\leq(2d-1)^{2\ell}\frac{\text{Im}[m^{d}_{\mathcal{T}}(z,w)]+\epsilon^{\prime}+\frac{\epsilon}{S_{g}^{1}}}{N\eta}$
$\displaystyle\frac{1}{Nd}\sum_{j\to
i}\chi(j)|\tilde{G}_{jj}^{(i)}-G_{jj}^{(i\mathbb{T}W_{S})}|\leq(2d-1)^{2\ell}\frac{\text{Im}[m^{d}_{\mathcal{T}}(z,w)]+\epsilon^{\prime}+\frac{\epsilon}{S_{g}^{1}}}{N\eta},$

as the proof is similar, we only give the details for the first inequality.

For those values $j$ such that $\chi(j)=0$, we use the fact that
$G_{jj}^{(i)}$ and $\tilde{G}_{jj}^{(i)}$ are both $O(1)$. Thus,

(7.16) $\frac{1}{Nd}\sum_{j\to
i}(1-\chi(j))|G_{jj}^{(i)}-\tilde{G}_{jj}^{(i)}|\lesssim N^{\mathfrak{c}-1},$

since the sum is non-zero for $\ll N^{\mathfrak{c}}$ many vertices.

By the resolvent identity, we have,

(7.17)
$G_{jj}^{(i)}=G_{jj}^{(i\mathbb{T}W_{S})}+[G^{(i\mathbb{T}W_{S})}B^{*}G|_{i\mathbb{T}W_{S}}BG^{(i\mathbb{T}W_{S})}]_{jj},$

Here, $B$ is the adjacency matrix for the graph $\mathcal{G}$ between
$i\mathbb{T}W_{S}$ and the complement.

We would also have,

(7.18)
$\tilde{G}_{jj}^{(i)}=G_{jj}^{(i\mathbb{T}W_{S})}+[G^{(i\mathbb{T}W_{S})}\tilde{B}^{*}\tilde{G}^{(i)}|_{i\mathbb{T}W_{S}}\tilde{B}G^{(i\mathbb{T}W_{S})}]_{jj}.$

Here, $\tilde{B}$ is the switched adjacency matrix for the matrix
$\tilde{\mathcal{G}}$. We will consider the matrix product that appears in the
end( the $GB^{*}GBG$) to be purely an error term.

We see that we have,

(7.19) $\displaystyle\frac{1}{Nd}\sum_{(j\to i)\in
E}\chi(j)|G_{jj}^{(i)}-G_{jj}^{(i\mathbb{T}W_{S})}|$
$\displaystyle\leq\frac{1}{Nd}\sum_{(j\to i)\in
E}\sum_{x,y\in\delta(\mathbb{T}W_{S}),a,b\in\mathbb{T}W_{S}}|G_{jx}^{(i\mathbb{T}W_{S})}|B_{xa}|[G^{(i)}|_{\mathbb{T}W_{S}}]_{ab}|B_{by}|G_{yj}^{(i\mathbb{T}W_{S})}|.$

$\delta(\mathbb{T}W_{S})$ consists of the boundary vertices in
$\mathcal{G}\backslash\\{i\\}$ that border a vertex of $\mathbb{T}\cup W_{S}$.
Now, for given $x$ and $y$, there are at most $O(1)$ choices for $a$ and $b$
for which one would not have $B_{xa}\neq 0$, and $B_{by}\neq 0$. Now, we argue
that $[G^{(i)}|_{\mathbb{T}W_{S}}]_{ab}$ is $O(1)$ for all pairs of vertices
$a$ and $b$ in $\mathbb{T}\cup W_{S}$.

An application of the resolvent identity would give,

(7.20)
$G_{ab}=G^{(i)}_{ab}+G|_{a\times\\{i,i+N}\\}(G|_{\\{i,i+N\\}})^{-1}G|_{\\{i,i+N\\}\times
b}.$

By applying our induction hypothesis from Definition 2.7 on the terms of $G$,
we would know that $G_{ab}$ and the entries of $G_{a\times\\{i,i+N\\}}$ and
$G_{\\{i,i+N\\}\times b}$ are all $O(1)$ quantities. One can also apply the
induction hypothesis and simple perturbation theory to show that the entries
of $(G|_{\\{i,i+N\\}})^{-1}$ are themselves $O(1)$ quantities. By
rearrangement, this means that

(7.21) $\frac{1}{Nd}\sum_{(j\to i)\in
E}\chi(j)|G_{jj}^{(i)}-G_{jj}^{(i\mathbb{T}W_{S})}|\lesssim\frac{1}{Nd}\sum_{(j\to
i)\in
E}\sum_{x,y\in\delta(\mathbb{T}W_{S})}\chi(j)|G^{(i\mathbb{T}W_{S})}_{jx}||G^{(i\mathbb{T}W_{S})}_{yj}|.$

Now, we apply the Cauchy-Schwarz inequality to bound this by,

(7.22) $\frac{1}{Nd}\sum_{x,y\in\delta(\mathbb{T}W_{S})}\Big{[}\sum_{(j\to
i)\in E}\chi(j)|G_{jx}^{(i\mathbb{T}W_{S})}|^{2}\sum_{(j\to i)\in
E}\chi(j)|G_{yj}^{(i\mathbb{T}W_{S})}|^{2}\Big{]}^{1/2}.$

We apply the resolvent identity again to relate $G^{(i\mathbb{T}W_{S})}$ to
$G^{(\mathbb{T}W_{S})}$, which we do have estimates to control. Namely, we
again see that,

(7.23)
$G_{jx}^{(i\mathbb{T}W_{S})}=G_{jx}^{(\mathbb{T}W_{S})}-G^{(\mathbb{T}W_{S})}|_{j\times\\{i,i+N\\}}(G^{(\mathbb{T}W_{S})}|_{\\{i,i+N\\}})^{-1}G^{(\mathbb{T}W_{S})}|_{\\{i,i+N\\}\times
x}.$

We know that the terms of $G^{(TW_{S})}|_{j\times\\{i,i+N\\}}$ are of $O(1)$
by Proposition 2.16. Now, if the vertex $j$ is far away from the vertices that
take part in the switching, we would also know that $i$ has a radius
$\frac{\mathfrak{R}}{4}$ tree-like neighborhood in the graph
$\mathcal{G}\backslash(\mathbb{T}\cup W_{S})$. This means we have good enough
controls in order to ensure that the terms of
$(G^{(\mathbb{T}W_{S})}|_{\\{i,i+N\\}})^{-1}$ are $O(1)$. From these two
facts, we now can assert that,

(7.24)
$\chi(j)|G_{jx}^{(i\mathbb{T}W_{S})}|^{2}\lesssim|G_{jx}^{(\mathbb{T}W_{S})}|^{2}+|G_{ix}^{(\mathbb{T}W_{S})}|^{2},$

Now, by applying the Ward identity, we see that,

(7.25) $\sum_{(j\to
i)}|G_{jx}^{(i\mathbb{T}W_{S})}|^{2}\lesssim\frac{\text{Im}[G_{jj}^{(\mathbb{T}W_{S})}]}{\eta}\lesssim\frac{\text{Im}[m_{\mathcal{T}}^{d}(z,w)]+\epsilon^{\prime}+\frac{\epsilon}{S_{g}^{1}}}{\eta}.$

We used the following triangle inequality to estimate
$G_{jj}^{(\mathbb{T}W_{S})}$,

(7.26)
$\displaystyle|G_{jj}^{(\mathbb{T}W_{S})}-m_{\mathcal{T}}^{d}(z,w)|\leq$
$\displaystyle|G_{jj}^{(\mathbb{T}W_{S})}-G_{jj}(Ext(B_{r}(j,\mathcal{G})Q_{O},Q_{I}))|$
$\displaystyle+|G_{jj}(Ext(B_{r}(j,\mathcal{G}),Q_{O},Q_{I}))-G_{jj}(Ext(B_{r}(j,\mathcal{G}),m_{\infty},m_{\infty}))|.$

The term $G_{jj}(Ext(B_{r}(\\{j\\},\mathcal{G}),m_{\infty},m_{\infty}))$ is
the same as $m_{\mathcal{T}}^{d}(z,w)$. Now, we can estimate the first term on
the right hand side of the above inequality by $\epsilon^{\prime}$ by using
Proposition 2.15. The second term on the right hand side of the above
inequality is bounded by $\frac{\epsilon}{S_{g}^{1}}$ by our inductive
hypothesis on the distance between $Q_{I/O}$ and $m_{\infty}$ from Definition
2.7 .

We can return to the expression in (7.22) to bound the quantity inside the
square root by the term above. Now, the number of $x$ vertices on the boundary
of $\mathbb{T}W_{S}$ is less than $(2d-1)^{\ell}$; the same is true of $y$.
Thus, the outer sum in equation (7.22) will give a factor of no more than
$(2d-1)^{2\ell}$. This will give us the desired inequality in equation (7.14).
∎

With this estimate on the difference between $Q_{I}/Q_{O}$ and
$\tilde{Q}_{I}/\tilde{Q}_{O}$, we can finally return to our proof of
Proposition 2.18 is simple.

###### Proof of Proposition 2.18.

From Lemmas 7.1and 7.3, we have a comparison between $\tilde{G}$ and a $P$
whose extension is given by parameters $Q_{I}$ and $Q_{O}$. The last Lemma 7.4
suggests that the difference between $Q_{I}/O$ and $\tilde{Q}_{I/O}$ are small
enough that we can apply the perturbation estimates from Theorem 1.11. These
estimates are sufficient for the proof of Proposition 2.18. ∎

##  8\. Concentration Estimates

The main issue with our stability estimate in equation (7.5) is the presence
of the term whose decay is
$\left(\frac{1}{d-1}\right)^{\frac{|d_{j}-d_{i}|}{2}}$. As long as $d_{j}$ and
$d_{i}$ are relatively small, this term will not decay as $N$ and $\ell$
increase. Recall that this error term came from estimating the following term,

$\frac{1}{d-1}\sum_{\alpha}P_{i,l_{\alpha}}P_{l_{\alpha},j}(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})_{c_{\alpha},c_{\alpha}}.$

While the triangle inequality will not show an improvement, the main point is
that this new graph came from random switchings. Thus, we can try to apply a
concentration argument to show that that the quantity that appears above has
superior bounds. Loosely speaking, the improvement will improve the constant
$\sum_{\alpha}|P_{i,l_{\alpha}}||P_{l_{\alpha},j}|$ to
$\sqrt{\sum_{\alpha}|P_{i,l_{\alpha}}P_{l_{\alpha},j}|^{2}}$. Under the
$l_{2}$ norm on $|P_{i,l_{\alpha}}||P_{l_{\alpha},j}|$, the branching factor
of the tree no longer cancels out the effect of the decrease. This is the main
improvement that we want to seek. To derive this improvement, we use the fact
that the $c_{\alpha}$’s are randomly chosen, independent from each other.
Using this fact, one would expect better concentration results for most
switching neighborhoods.

The main result of this section is the following Theorem,

######  Theorem 8.1.

Let $\mathcal{G}$ be a graph from $\Omega^{1}_{S,\mathfrak{q},o}$ with $\ell$
neighborhood $\mathbb{T}$. Further recall the notation
$P_{xy}:=G(Ext(B_{r}(\mathbb{T},\mathcal{G}),Q_{I},Q_{O}))_{xy}$ for
$x,y\in\mathbb{T}$.

Consider the following weight families. These weight families will allow us to
understand $Q_{I}$.

  1. (1)

Let $v$ be a vertex in $\mathbb{T}$ and let $\tilde{v}$ be an index
corresponding to $v$ ( so it is either $v$ or $v+N$). Recall our indexing of
boundary vertices of $\mathbb{T}$ as $l_{\alpha}$. We define the in-weights
$w^{\text{in}}_{\alpha}:=P_{xl_{\alpha}}P_{l_{\alpha}x}$. There are
$\lesssim|\mathbb{T}|$ of these types of indices depending on the choice of
the index $x$.

  2. (2)

If $\mathbb{T}$ is a truncated $d$-regular tree, fix a vertex $k$ that is
connected to $o$; assume for now that the edge is oriented $k\to o$. Define
$A$ to be a set of indices as follows. Consider a vertex $l_{\alpha}$ on the
boundary of $\mathbb{T}$; if the path from $o$ to $v_{\alpha}$ does not pass
through $k$, then we include the index $\alpha$ in $A$. We then define the
weight $w^{\text{in}}_{\alpha}:=P^{(k)}_{o,l_{\alpha}}P^{(k)}_{l_{\alpha},o}$.
$P^{(k)}$ is a shorthand for
$G_{o,l_{\alpha}}(Ext(B_{r}(\mathbb{T},\mathcal{G}^{(i)}),Q_{I},Q_{O}))$. If
instead the edge were oriented $o\to k$, we would instead choose the weights
$P^{(k)}_{o+N,l_{\alpha}}P^{(k)}_{l_{\alpha},o+N}$. There are $2d$ such
weights of this type.

There exists and event $S_{C}(\mathcal{G})\subset S_{G}(\mathcal{G})$ such
that
$1-\mathbb{P}(S_{C}(\mathcal{G}))=1-\mathbb{P}(S_{G}(\mathcal{G}))-(|T|+d)\exp[-(\log
N)^{2}]$ such that we have the following estimate,

$\displaystyle\left|\sum_{\alpha}w_{\alpha}(\tilde{G}_{\tilde{a}_{\alpha}+N,\tilde{a}_{\alpha}+N}^{(\mathbb{T})}-G_{\tilde{a}_{\alpha}+N,\tilde{a}_{\alpha}+N}(Ext_{i}(B_{r}(\tilde{a}_{\alpha},\tilde{\mathcal{G}}^{(\mathbb{T})}),Q_{1},Q_{2})))-\sum_{\alpha}w_{\alpha}(Q_{I}-Y_{i,r}(Q_{I},Q_{O}))\right|$
$\displaystyle\lesssim(\log
N)\epsilon^{\prime}\sqrt{\sum_{\alpha}|w_{\alpha}|^{2}}+\Big{(}(2d-1)^{2\ell}\frac{\text{Im}[m_{\mathcal{T}}^{d}]+\epsilon^{\prime}+\frac{\epsilon}{S_{g}^{1}}}{N\eta}+N^{\mathfrak{c}-1}\Big{)}+\frac{1}{N^{1-\mathfrak{c}}}.$

######  Remark 8.2.

We have a similar concentration statement to understand the concentration
around $Q_{O}$. We do not write out the whole statement for simplicity, but
mention the appropriate changes to the weights and computed function. In the
first type of wight family, we change the weights to
$w_{\alpha}^{\text{out}}:=P_{x,l_{\alpha}+N}P_{l_{\alpha}+N,x}$. The function
which we try to compute using concentration estimates will be of the form
$\sum_{\alpha}w_{\alpha}\tilde{G}_{\tilde{a}_{\alpha},\tilde{a}_{\alpha}}$.

The proof of the above statement will be divided into smaller parts. Since the
random variables $\tilde{a}_{\alpha}$ are chosen independently of each other
given the graph,
$\tilde{G}^{(\mathbb{T})}_{\tilde{a}_{\alpha}+N,\tilde{a}_{\alpha}+N}$ are
almost independent random variables, but he fact that they are not truly
independent makes directly applying standard concentration estimates
difficult. Instead, we first prove concentration for a closely related family
of legitimate independent random variables.

###  8.1. Concentration estimates for a related family of independent random
variables

For a vertex $v\in\mathcal{G}$, we use $(v\mathbb{T})$ as a short way to
express the union $\\{v\\}\cup\mathbb{T}$. Also let $\chi(\cdot)$ is the
indicator function of the event that the vertex is question is of distance at
least $\mathfrak{R}/4$ from the vertices that bound $\mathbb{T}$ and that the
vertex in question has a radius $\mathfrak{R}/4$ tree-like neighborhood. As a
shorthand for what will follow, we will define $D_{\alpha}$ as a shorthand for
the difference,

(8.1)
$D^{\text{in}}_{\alpha}:=\chi(c_{\alpha})(G^{(b_{\alpha}\mathbb{T})}-P^{(b_{\alpha}\mathbb{T})})_{c_{\alpha}+N,c_{\alpha}+N},$

where recall that $P^{(b_{\alpha}\mathbb{T})}$ was defined to be the Green’s
function of the extension

$P_{ij}:=G(Ext(B_{r}(\\{i,j\\},\mathcal{G}\backslash(b_{\alpha}\mathbb{T})),Q_{I},Q_{O}))$,
while $P_{ij}^{(\mathbb{T})}$ is simply
$G_{ij}(Ext(B_{r}(\\{i,j\\}),\mathcal{G}\backslash\mathbb{T}),Q_{I},Q_{O}))$.
Note that we specifically chose the unswitched graph here.

######  Lemma 8.3.

Consider all of the families of weights $w_{\alpha}$ as given in Theorem 8.1
Let $S_{C}(\mathcal{G})\subset S_{G}(\mathcal{G})$ be the set of switching
events such that the following event holds for all of the weight families.

(8.2)
$\displaystyle\Big{|}\sum_{\alpha}w_{\alpha}D^{\text{in}}_{\alpha}-\sum_{\alpha}w_{\alpha}(Q_{I}(z,w)-Y_{i,r}(Q_{I}(z,w),Q_{O}(z,w)))\Big{|}\lesssim$
$\displaystyle(\log
N)\epsilon^{\prime}\sqrt{\sum_{\alpha}|w_{\alpha}|^{2}}+\Big{(}(2d-1)^{2\ell}\frac{\text{Im}[m_{\mathcal{T}}^{d}]+\epsilon^{\prime}+\frac{\epsilon}{S_{g}^{1}}}{N\eta}+N^{\mathfrak{c}-1}\Big{)}.$

Then,
$\mathbb{P}(S_{C}(\mathcal{G})=\mathbb{P}(S_{G}(\mathcal{G}))-(|T|+d)\exp[-(\log
N)^{2}]$.

###### Proof.

We have shown in Proposition 2.15 that each of the differences
$|(G^{(\mathbb{T})}-P^{(\mathbb{T})})_{c_{\alpha}+N,c_{\alpha}+N}|\leq\epsilon^{\prime}$.
We can apply the resolvent identity to understand
$|G^{(b_{\alpha}\mathbb{T})}_{c_{\alpha}+N,c_{\alpha}+N}-P^{(b_{\alpha}\mathbb{T})}_{c_{\alpha}+N,c_{\alpha}+N}|$.
First of all, we see that, for edges $(i\to j)$,

(8.3)
$\chi(j)G^{(i\mathbb{T})}_{j+N,j+N}=\chi(j)(G^{(\mathbb{T})}_{j+N,j+N}-G^{(\mathbb{T})}|_{j+N\times\\{i,i+N\\}}(G^{(\mathbb{T})}|_{\\{i,i+N\\}})^{-1}G^{(\mathbb{T})}|_{\\{i,i+N\\}\times
j+N}).$

In addition, we have that,

(8.4)
$\chi(j)P^{(i\mathbb{T})}_{j+N,j+N}=\chi(j)(P^{(\mathbb{T})}_{j+N,j+N}-P^{(\mathbb{T})}|_{j+N\times\\{i,i+N\\}}(P^{(\mathbb{T})}|_{\\{i,i+N\\}})^{-1}P^{(\mathbb{T})}|_{\\{i,i+N\\}\times
j+N}).$

We have the estimate that
$|G^{(\mathbb{T})}-P^{(\mathbb{T})}|\lesssim\epsilon^{\prime}$ from
Proposition 4.3. We also know that entries of
$(P^{(\mathbb{T})}|_{\\{i,i+N\\}})^{-1}$ are $O(1)$ quantities when
$\chi(j)\neq 0$, since, in this case, $i$ has at least a radius $\mathfrak{R}$
treelike-neighborhood in $\mathcal{G}\backslash T$. This allows us to apply a
simple perturbation argument to assert that,

(8.5)
$\displaystyle\chi(j)\bigg{|}G^{(\mathbb{T})}|_{j+N\times\\{i,i+N\\}}(G^{(\mathbb{T})}|_{\\{i,i+N\\}})^{-1}G^{(\mathbb{T})}|_{\\{i,i+N\\}\times
j+N}$ $\displaystyle\hskip
28.45274pt-P^{(\mathbb{T})}|_{j+N\times\\{i,i+N\\}}(P^{(\mathbb{T})}|_{\\{i,i+N\\}})^{-1}P^{(\mathbb{T})}|_{\\{i,i+N\\}\times
j+N}\bigg{|}\lesssim\epsilon^{\prime}.$

These facts ensure that,

(8.6)
$\chi(j)|G^{(i\mathbb{T})}_{j+N,j+N}-P^{(i\mathbb{T})}_{j+N,j+N}|\leq\epsilon^{\prime},$

uniformly. Furthermore, once we have fixed the graph
$\mathcal{G}^{(\mathbb{T})}$, the switched edges are chosen independently of
each other. This means that the variables $D^{\text{in}}_{\alpha}$ are
independent and identically distributed.

By Hoeffding’s inequality, we have the following probability bound,

(8.7)
$\mathbb{P}\Big{(}\left|w_{\alpha}(D^{\text{in}}_{\alpha}-\mathbb{E}[D^{\text{in}}_{\alpha}])\right|\geq
t\sum_{\alpha}|w_{\alpha}|^{2}\epsilon^{\prime}\Big{)}\leq\exp[-t^{2}/C],$

for some constant $C$. Here, the probability $\mathbb{P}$ and the expectation
$\mathbb{E}$ is only over the randomness of the choice of switched sets, only,
not on the randomness of the random graph.

Our goal now is to relate $\mathbb{E}[D^{\text{in}}_{\alpha}]$ to the
quantities $Q_{I}$. We first define the set $\mathcal{E}^{(\mathbb{T})}$ to be
the set of all edges in the complement of $\mathbb{T}$ in $\mathcal{G}$. By
definition,

(8.8)
$\mathbb{E}[D^{\text{in}}_{\alpha}]=\frac{1}{|\mathcal{E}^{(\mathbb{T})}|}\sum_{(i\to
j)}\chi(j)(G^{(i\mathbb{T})}_{j+N,j+N}-P^{(i\mathbb{T})}_{j+N,j+N}).$

We have earlier shown that all of these quantities are less than
$\epsilon^{\prime}$ uniformly. In addition, we have that
$|\mathcal{E}^{(mt)}|\geq Nd-O((2d-1)^{\ell})\geq Nd-O(N^{\mathfrak{c}})$. By
adjusting the normalization factor, we have that

Thus, we would know that,

(8.9) $\mathbb{E}[D^{\text{in}}_{\alpha}]=\frac{1}{Nd}\sum_{(i\to
j)}\chi(j)(\tilde{G}^{(i\mathbb{T})}_{j+N,j+N}-P^{(i\mathbb{T})}_{j+N,j+N})+O\left(\frac{N^{\mathfrak{c}}}{Nd}\right).$

Now, we relate $G^{(i)}_{j+N,j+N}$ to $G^{(i\mathbb{T})}_{j+N,j+N}$ via the
Schur complement formula. We can apply the same argument as found in the proof
of equation (7.15) to show that,

(8.10) $\frac{1}{Nd}\sum_{(i\to
j)}\chi(j)|G^{(i)}_{j+N,j+N}-G^{(i\mathbb{T})}_{j+N,j+N}|\lesssim(2d-1)^{2\ell}\frac{\text{Im}[m_{\mathcal{T}}^{d}]+\epsilon^{\prime}+\frac{\epsilon}{S_{g}^{1}}}{N\eta},$

Furthermore, using the fact that $\chi(j)=1$ implies that the vertex $j$ has a
radius $\mathfrak{R}/4$ tree-like neighborhood ensures that,

(8.11)
$\frac{1}{Nd}\sum_{(i,j)}\chi(j)P^{(i\mathbb{T})}_{j+N,j+N}=\frac{1}{Nd}\sum_{(i\to
j)}\chi(j)Y_{1,r}(Q_{I},Q_{O}).$

For the remaining quantities with $\chi(j)=0$, we know that
$P^{(i)}_{j+N,j+N}$ is $O(1)$ from Lemma 3.4. Using Proposition 2.15 would
further imply that the entries $G^{(i)}_{j+N,j+N}$ are also $O(1)$. This
bounds the sum of terms $\frac{1}{Nd}\sum_{i\to
j}(1-\chi(j))G^{(i)}_{j+N,j+N}$ by $N^{\mathfrak{c}-1}$.

Combining these facts, we see that,

(8.12)
$\sum_{\alpha}w_{\alpha}\mathbb{E}[D^{in}_{\alpha}]=\sum_{\alpha}w_{\alpha}(Q_{I}(z,w)-Y_{i,r}(Q_{i},Q_{O}))+O\Big{(}(2d-1)^{2\ell}\frac{\text{Im}[m_{\mathcal{T}}^{d}]+\epsilon^{\prime}+\frac{\epsilon}{S_{g}^{1}}}{N\eta}+N^{\mathfrak{c}-1}\Big{)}.$

In the final line, we used the fact that $\sum_{\alpha}w_{\alpha}\lesssim 1$.
∎

To use our concentration estimates for the unswitched graph onto the switched
graph, we apply the following lemma, which will show that the values of
$\tilde{G}^{(\mathbb{T}})_{c_{\alpha}+N,c_{\alpha}+N}$ are close to those of
$G^{(b_{\alpha}\mathbb{T})}_{c_{\alpha}+N,c_{\alpha}+N}$ as well as similar
results for the index $c_{\alpha}$.

######  Lemma 8.4.

Assume that $c_{\alpha}$ has distance at least $\mathfrak{R}/4$ from all of
the other vertices $\\{a_{\beta},b_{\beta},c_{\beta}\\},\beta\neq\alpha$ that
participate in the switching and that the pair ${c_{\alpha},b_{\alpha}}$ is
not Green’s function connected to $\\{c_{\beta},b_{\beta}\\}$ for
$\beta\neq\alpha$. Then, we have that,

(8.13)
$|G^{(b_{\alpha}\mathbb{T})}_{c_{\alpha},c_{\alpha}}-\tilde{G}^{(\mathbb{T})}_{c_{\alpha},c_{\alpha}}|\lesssim(2d-1)^{\ell}\phi^{2}$

###### Proof.

The desired estimate is a consequence of the following intermediate comparison
estimates,

(8.14)
$\displaystyle|G^{(\mathbb{T}W_{S})}_{c_{\alpha},c_{\alpha}}-G^{(\mathbb{T}b_{\alpha})}_{c_{\alpha},c_{\alpha}}|\lesssim(2d-1)^{\ell}(\phi)^{2}$
$\displaystyle|G^{(\mathbb{T}W_{S})}_{c_{\alpha},c_{\alpha}}-\tilde{G}^{(\mathbb{T})}_{c_{\alpha},c_{\alpha}}|\lesssim(2d-1)^{\ell}(\phi^{2})$

The proof of both of these estimates are similar, so it will suffice to just
prove the first one.

By the resolvent identity, we have,

(8.15)
$|G^{(\mathbb{T}W_{S})}_{c_{\alpha},c_{\alpha}}-G^{(b_{\alpha}\mathbb{T})}_{c_{\alpha},c_{\alpha}}|\leq\Big{|}\sum_{x,y\in
W_{s}\backslash
b_{\alpha}}G^{(b_{\alpha}\mathbb{T})}_{c_{\alpha},x}(G^{(b_{\alpha}\mathbb{T})}|_{W_{s}\backslash
b_{\alpha}})_{xy}^{-1}G^{(b_{\alpha}\mathbb{T})}_{y,c_{\alpha}}\Big{|}$

Now, the proof of Proposition 2.16 would also show that the elements
$G^{(b_{\alpha}\mathbb{T})}_{c_{\alpha},x}$ and
$G^{(b_{\alpha}\mathbb{T})}_{y,c_{\alpha}}$ are both $\lesssim\phi$.
Furthermore, Lemma 5.5 would show that
$|(G^{(b_{\alpha}\mathbb{T})}|_{W_{S}\backslash b_{\alpha}})^{-1}_{xy}|$ is
bounded by $\epsilon^{\prime}$ if $x$ and $y$ are not indices that correspond
to the same vertex, while we can bound this by $O(1)$ if they do correspond to
the same index. Using these facts, we see that the bound on the right hand
side of (8.15) is
$(2d-1)^{\ell}\phi^{2}+(2d-1)^{2\ell}\epsilon^{\prime}\phi^{2}$ which is
dominated by the first term.

For the term involving the switched graph, the Schur complement formula gives
us,

(8.16)
$|\tilde{G}^{(\mathbb{T})}_{c_{\alpha},c_{\alpha}}-G^{(\mathbb{T}W_{S})}_{c_{\alpha},c_{\alpha}}|\leq\Big{|}\sum_{x,y\in\delta(W_{S})}(G^{(\mathbb{T}W_{S})}B)_{c_{\alpha},x}(\tilde{G}^{(\mathbb{T})})_{xy}(B^{\prime}G^{(\mathbb{T}W_{S})})_{y,c_{\alpha}}\Big{|},$

where $\delta(W_{S})$ correspond to the vertices that neighbor those of
$W_{S}$ in $\mathcal{G}\backslash W_{S}$. We have shown earlier in Proposition
2.16 that we can bound the entries of
$(G^{(\mathbb{T}W_{S})}B)_{c_{\alpha},x}$ and
$(B^{\prime}G^{(\mathbb{T}W_{S})})_{y,c_{\alpha}}$ by $\phi$. Furthermore, we
would also know that $\tilde{G}^{(\mathbb{T})}_{xy}$ is $O(1)$ if $x$ and $y$
correspond to the same vertex or is bounded by $\epsilon^{\prime}$ otherwise
by Lemma 6.3. The same counting gives us the desired bound. ∎

With these two lemmas in hand, we can return to a proof of Theorem 8.1.

###### Proof of Theorem 8.1.

From Lemma 8.3, we know that $\sum_{\alpha}w_{\alpha}D_{\alpha}^{in}$ is close
to the desired estimate $\sum_{\alpha}w_{\alpha}(Q_{I}-Y_{i,r}(Q_{I},Q_{O}))$
on the event $S_{C}{\mathcal{G}}$. It suffices to understand the differences,

(8.17)
$\sum_{\alpha}|w_{\alpha}||D_{\alpha}^{in}-(\tilde{G}_{\tilde{a}_{\alpha}+N,\tilde{a}_{\alpha}+N}^{(\mathbb{T})}-G_{\tilde{a}_{\alpha}+N,\tilde{a}_{\alpha}+N}(Ext(B_{r}(\tilde{a}_{\alpha},\tilde{\mathcal{G}}^{(\mathbb{T})}),Q_{1},Q_{2}))|.$

We know that for all terms in which the pair $c_{\alpha},b_{\alpha}$ is not
Green’s function connected to $c_{\beta},b_{\beta}$ for $\beta\neq\alpha$ that
we know
$|\tilde{G}_{a_{\alpha}+N,a_{\alpha}+N}^{(\mathbb{T})}-G^{(b_{\alpha}\mathbb{T})}_{a_{\alpha}+N,a_{\alpha}+N}|\lesssim(2d-1)^{\ell}\phi^{2}$
via Lemma 8.4. Furthermore, we would also know that since $\tilde{a}_{\alpha}$
would have a radius $\mathfrak{R}/4$ tree-like neighborhood that,

(8.18)
$G_{\tilde{a}_{\alpha}+N,\tilde{a}_{\alpha}+N}(Ext_{i}(B_{r}(\tilde{a}_{\alpha},\tilde{\mathcal{G}}\backslash\mathbb{T}),Q_{I},Q_{O}))=G_{\tilde{a}_{\alpha}+N,\tilde{a}_{\alpha}+N}(Ext_{i}(B_{r}(\tilde{a}_{\alpha},\mathcal{G}\backslash\mathbb{T}),Q_{I},Q_{O})).$

This deals with all except for $O(1)$ many indices $\alpha$. For the remaining
indices, we may use the trivial bound $\epsilon^{\prime}$.

Thus, we see that,

$\displaystyle\sum_{\alpha}w_{\alpha}(\tilde{G}_{\tilde{a}_{\alpha}+N,\tilde{a}_{\alpha}+N}^{(\mathbb{T})}-G_{\tilde{a}_{\alpha}+N,\tilde{a}_{\alpha}+N}(Ext_{i}(B_{r}(\tilde{a}_{\alpha},\tilde{\mathcal{G}}^{(\mathbb{T})}),Q_{1},Q_{2})))-\sum_{\alpha}w_{\alpha}(Q_{I}-Y_{i,r}(Q_{I},Q_{O}))$
$\displaystyle=\sum_{\alpha}w_{\alpha}D^{in}_{\alpha}+O(\sum_{\alpha}|w_{\alpha}|(2d-1)^{\ell}\phi^{2}+\max_{\alpha}|w_{\alpha}|\epsilon^{\prime})$

Manifestly, $\max_{\alpha}|w_{\alpha}|\epsilon^{\prime}$ is still less than
$(\log N)\epsilon^{\prime}\sqrt{\sum_{\alpha}|w_{\alpha}|^{2}}$. Furthermore,
we can use the fact that $\sum_{\alpha}|w_{\alpha}|\lesssim 1$ and the value
of $\phi$ from Definition 5.2 to assert that we can bound
$\sum_{\alpha}|w_{\alpha}|(2d-1)^{\ell}\phi^{2}\ll N^{1-\mathfrak{c}}$ Since
$\max_{\alpha}|w_{\alpha}|$ decays as $(d-1)^{-ell/2}$, we have sufficient
control of this completes the proof of Theorem 8.1. ∎

###  8.2. Improved Bounds on $\tilde{G}$

Given the graph $\mathcal{G}$ in $\Omega^{1}_{S,\mathfrak{q},o}$, we choose a
switching event $S\in\mathbb{S}_{\mathcal{G},o}$ that belongs in
$S_{C}(\mathcal{G})$ as in Theorem 8.1. With these concentration estimates in
hand, we are now in position to prove improved bounds on our Green’s functions
in order to prove Theorem 2.11.

###### Proof of Theorem 2.11.

We consider the event $S_{C}(\mathcal{G})$. The proof of Theorem 2.11 involves
proving the three estimates (2.11), (2.12), and (2.13).

We start with the equation (2.13). This is a rather simple consequence of the
estimates of Section 7. From Lemma 7.3 Equation (7.9), we know that,
$|G_{oi}-P_{oi}|\lesssim\frac{(\log N)^{2}\epsilon^{\prime}}{(d-1)^{\ell/2}}$.
Here,

$P_{oi}=G_{oi}(Ext(B_{r}(i\mathbb{T},\tilde{\mathcal{G}}),Q_{I},Q_{O})),$

In the above expression, we have to replace $Q_{I}$ and $Q_{O}$ with
$\tilde{Q}_{I}$ and $\tilde{Q}_{O}$ as well as change the domain to
$B_{r}(\\{i,o\\}$ instead of $B_{r}(i\mathbb{T})$.

First of all, we have bounds on the difference $Q_{I}-\tilde{Q}_{I}$ as well
as $Q_{O}-\tilde{Q}_{O}$ from Lemma 7.4. Combining this bound with a slight
modification of the perturbation bound from Lemma 3.4.

Namely, we have that,

(8.19)
$\displaystyle|G_{oi}(Ext(B_{r}(i\mathbb{T},\tilde{\mathcal{G}}),Q_{I},Q_{O}))-G_{oi}(Ext(B_{r}(i\mathbb{T},\tilde{\mathcal{G}}),\tilde{Q}_{I},\tilde{Q}_{O}))|$
$\displaystyle\lesssim\Big{(}\frac{1}{d-1}\Big{)}^{\text{dist}(i,j)}(1+\log
N)^{3}[|Q_{I}-\tilde{Q}_{I}|+|Q_{O}-\tilde{Q}_{O}|]$
$\displaystyle\lesssim\Big{(}\frac{1}{d-1}\Big{)}^{\text{dist}(i,j)}(\log
N)^{3}\Big{[}\frac{1}{N^{1-\mathfrak{c}}}+(2d-1)^{2\ell}\frac{\text{Im}[m_{\mathcal{T}}^{d}(z,w)]+\epsilon^{\prime}+\frac{\epsilon}{S_{g}^{1}}}{N\eta}\Big{]}.$

Finally, we can use Lemma 3.6 to change the domain used in the Ext operator
from $B_{r}(i\mathbb{T},\mathcal{G})$ to $B_{r}(\\{i,o\\})$. This introduces
the terms involving $|\tilde{Q}_{I}+\tilde{Q}_{O}-2m_{\infty}|$, etc. on the
right hand side of equation (2.13). Finally, we can combine all of these
estimates using a triangle inequality to finish the proof of (2.13).

Here, we specifically use the fact that $\mathfrak{j}(d)<\frac{1}{2}$ to
cancel out the factor coming from $\epsilon^{\prime}$.

The derivation equation (2.12) from equation (7.5) is quite similar.

The replacement of
$G_{oi}(Ext(B_{r}(i\mathbb{T},\tilde{\mathcal{G}}),Q_{I},Q_{O}))$ with
$G_{oi}(Ext(B_{r}(i\mathbb{T},\tilde{\mathcal{G}}),\tilde{Q}_{I},\tilde{Q}_{O}))$
is similar to the proof of equation (2.13).

However, we now need to find an improvement in the second term of the right
hand side of equation (7.5); the first term is sufficiently small. Tracing
through the proof of equation (7.5), This term comes from an attempt to bound
the term on the second line of equation (7.6). Namely, the sum of the on-
diagonal terms.

(8.20)
$\frac{1}{d-1}\sum_{\alpha}P_{i,l_{\alpha}}P_{l_{\alpha},j}(\tilde{G}^{(\mathbb{T})}-P^{(\mathbb{T})})_{\tilde{c}_{\alpha},\tilde{c}_{\alpha}}$

We can replace $P^{(\mathbb{T})}_{\tilde{c}_{\alpha},\tilde{c}_{\alpha}}$ is
defined with respect to the domain
$B_{r}(c_{\alpha}\mathbb{T},\mathcal{G}^{(\mathbb{T})})$. This can be replaced
with the extension with respect to the domain
$B_{r}(c_{\alpha},\mathcal{G}^{(\mathbb{T})})$ with an error term of the same
order of magnitude as the right hand side of (2.12). Now, since
$\sum_{\alpha}|P_{i,l_{\alpha}}||P_{l_{\alpha},i}|\lesssim 1$, it causes not
issue to apply a triangle inequality.

After the appropriate replacement of the the domain of the extension, the term
in (8.20) is controlled by the estimates of Theorem 8.1. This completes the
desired bound of equation (2.12). The proof of (2.11) requires very similar
manipulations as the previous two, but uses the second family of weights
$w_{\alpha}$ from Theorem 8.1 rather than the first. ∎

##  Appendix A Collected estimates on Green’s function of infinite graphs

###  A.1.  Bounds on $G_{ij}$ for tree-like and almost tree-like graphs

Recall our inductive procedure to compute for a directed tree, all Green’s
function values (via the Schur complement formula), starting from the solution
$m_{\infty}$ of (1.17). The success of this procedure requires that the sum of
$|G_{ij}|^{2}$ over all vertices $j$ of graph-distance $k$ from $i$, be
bounded uniformly in $k$. While the naive bound
$G_{ij}\leq\left(\sqrt{d-1}\right)^{-\text{dist}(i,j)}$ is not strong enough
to compensate the branching factor of the tree, our next bound on
$m_{\infty}$, helps control the latter branching factor.

######  Lemma A.1.

For some $C_{0}=C_{0}(d)$, $d\geq 3$ finite, any $z\in\mathbb{C}_{+}$,
$w\in\mathbb{C}$ and any solution $m_{\infty}:\mathbb{C}_{+}\to\mathbb{C}_{+}$
of (1.17), setting

(A.1) $X:=|m_{\infty}|^{2}\,,\qquad
Y:=\frac{d}{d-1}|m_{\infty}^{uod}|^{2}=\frac{d}{d-1}\frac{|w|^{2}|m_{\infty}|^{2}}{\big{|}z+\frac{d}{d-1}m_{\infty}\big{|}^{2}}\,,$

we have that

(A.2) $X+Y<1\,,\qquad|m^{sd}_{\infty}|\leq C_{0}\,.$

###### Proof.

Taking $(1/\cdot)$ of both sides of (1.17), results with

(A.3)
$\frac{1}{m_{\infty}}=\frac{|w|^{2}}{z+\frac{d}{d-1}m_{\infty}}-z-m_{\infty}\,.$

The imaginary part of this identity is precisely

$-\frac{\Im(m_{\infty})}{|m_{\infty}|^{2}}=-\frac{|w|^{2}\big{(}\Im(z)+\frac{d}{d-1}\Im(m_{\infty})\big{)}}{|z+\frac{d}{d-1}m_{\infty}|^{2}}-\Im(z)-\Im(m_{\infty}).$

Now, utilizing that $\Im(z)>0$, results with the inequality,

$\frac{\Im(m_{\infty})}{|m_{\infty}|^{2}}>\Im(m_{\infty})\Big{[}1+\frac{\frac{d}{d-1}|w|^{2}}{|z+\frac{d}{d-1}m_{\infty}|^{2}}\Big{]}\,.$

Now, dividing both sides of this inequality by $\Im(m_{\infty})>0$, yields the
lhs of (A.2).

Next, the real part of the identity (A.3) amounts to

$\frac{\Re(m_{\infty})}{|m_{\infty}|^{2}}=\frac{|w|^{2}\big{(}\Re(z)+\frac{d}{d-1}\Re(m_{\infty})\big{)}}{|z+\frac{d}{d-1}m_{\infty}|^{2}}-\Re(z)-\Re(m_{\infty}).$

With $X,Y\in[0,1]$, it follows after some algebra that

$\frac{\Re(m_{\infty})}{\Re(z)}=\frac{\frac{d-1}{d}Y-X}{1-Y+X}\geq-\frac{1}{2}\,.$

Since $\Im(m_{\infty})>0$ and $\Im(z)>0$, this implies in turn that also
$\Re(m_{\infty}/z)\geq-1/2$. With $|m_{\infty}|\leq 1$, we thus deduce from
(1.18) that for any $d\geq 3$,

$|m_{\infty}^{sd}|\leq\frac{|1+m_{\infty}/z|}{|\frac{d-1}{d}+m_{\infty}/z|}\leq\sup_{\Re(S)\geq-1/2}\Big{\\{}\frac{|1+S|}{|\frac{d-1}{d}+S|}\Big{\\}}:=C_{0}(d)$

is finite, as claimed. ∎

Using Lemma A.1, we next show that $\sum_{y\in\partial B_{k}(r)}|G_{r,y}|^{2}$
is bounded, uniformly in $k$, for any one of the directed trees of interest to
us. This computation from the root is relevant for the coefficient of various
first order terms that will appear in our perturbation series.

######  Lemma A.2.

For the trees $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ from Definition 1.8 and
any $k\geq 1$,

(A.4) $\displaystyle A_{1,k}:=\sum_{v\in\partial
B_{k}(r),o_{v}\in\\{0,\aleph\\}}|(G_{\mathcal{T}_{1}})_{r+\aleph,v+o_{v}}|^{2}\lesssim
1,$ $\displaystyle A_{2,k}:=\sum_{v\in\partial
B_{k}(r),o_{v}\in\\{0,\aleph\\}}|(G_{\mathcal{T}_{2}})_{r,v+o_{v}}|^{2}\lesssim
1,$

where the implicit constants do not depend on $k$. The corresponding
quantities for the Green’s function $G_{\mathcal{T}}$ of the ‘pure’
$d$-regular directed tree, are also bounded uniformly in $k$.

###### Proof.

Suppose $l\in\mathcal{T}_{1}$ and $r=v_{0},v_{1},\ldots,v_{k}=l$ is the
(undirected) path in $\mathcal{T}_{1}$ from $r$ to $l$. Note that upon removal
of the edge from $r$ to $v_{1}$, the vertex $l$ is in a copy
$\mathcal{T}^{(r)}_{1}$ or $\mathcal{T}^{(r)}_{2}$, respectively, of
$\mathcal{T}_{1}$ or $\mathcal{T}_{2}$ rooted at $v_{1}$. Thus, similarly to
the derivation of (1.14)-(1.15), but now utilizing (1.12), we get in case of
an out-edge from $r$ leading to $v_{1}$, that

(A.5)
$\displaystyle(G_{\mathcal{T}_{1}})_{r+\aleph,l+o_{l}}=\frac{-1}{\sqrt{d-1}}(G_{\mathcal{T}_{1}})_{r+\aleph,r}(G_{\mathcal{T}^{(r)}_{1}})_{v_{1}+\aleph,l+o_{l}},$
$\displaystyle(G_{\mathcal{T}_{2}})_{r,l+o_{l}}=\frac{-1}{\sqrt{d-1}}(G_{\mathcal{T}_{2}})_{r,r}(G_{\mathcal{T}^{(r)}_{1}})_{v_{1}+\aleph,l+o_{l}},$

whereas if an in-edge of $r$ is connected to $v_{1}$, we get instead that

(A.6)
$\displaystyle(G_{\mathcal{T}_{1}})_{r+\aleph,l+o_{l}}=\frac{-1}{\sqrt{d-1}}(G_{\mathcal{T}_{1}})_{r+\aleph,r+\aleph}(G_{\mathcal{T}^{(r)}_{2}})_{v_{1},l+o_{l}}\,,$
$\displaystyle(G_{\mathcal{T}_{2}})_{r,l+o_{l}}=\frac{-1}{\sqrt{d-1}}(G_{\mathcal{T}_{2}})_{r,r+\aleph}(G_{\mathcal{T}^{(r)}_{2}})_{v_{1},l+o_{l}}\,.$

We take $|\cdot|^{2}$ of both sides, sum over $o_{l}$ and all vertices
$l\in\partial B_{k}(r)$ and substitute our expressions (1.17)–(1.18) for
$(G_{\mathcal{T}_{1}})_{r+\aleph,r}$,
$(G_{\mathcal{T}_{1}})_{r+\aleph,r+\aleph}$,
$(G_{\mathcal{T}_{2}})_{r,r+\aleph}$ and $(G_{\mathcal{T}_{2}})_{r,r}$, to
arrive at the following recursion relations

(A.7) $\displaystyle A_{1,k}=YA_{1,k-1}+XA_{2,k-1},$ $\displaystyle
A_{2,k}=XA_{1,k-1}+YA_{2,k-1},$

in terms of $(X,Y)$ of (A.1). Solving the recursion (A.7) leads to

(A.8) $\begin{bmatrix}A_{1,k}\\\ A_{2,k}\end{bmatrix}=\begin{bmatrix}Y&X\\\
X&Y\end{bmatrix}^{k}\begin{bmatrix}A_{1,0}\\\ A_{2,0}\end{bmatrix}.$

The central matrix has eigenvalues $Y\pm X$. From (A.2) we know that $|Y\pm
X|<1$, which upon transforming into the basis of eigenvectors, suffices for
the uniform in $k$ boundedness of $A_{1,k}$ and $A_{2,k}$.

In case of the tree $\mathcal{T}$, we derive the corresponding recursion via
the Schur complement formula after the removal of the root. Indeed, we have
that,

(A.9) $\displaystyle\sum_{l\in\partial
B_{k}(r),o_{l}}|(G_{\mathcal{T}})_{r+o_{r},l+o_{l}}|^{2}$
$\displaystyle=\frac{d}{d-1}|(G_{\mathcal{T}})_{r+o_{r},r}|^{2}\sum_{l\in\partial
B_{k-1}(r),o_{l}}|(G_{\mathcal{T}_{1}})_{r+\aleph,l+o_{l}}|^{2}$
$\displaystyle+\frac{d}{d-1}|(G_{\mathcal{T}})_{r+o_{r},r+\aleph}|^{2}\sum_{l\in\partial
B_{k-1}(r),o_{l}}|(G_{\mathcal{T}_{2}})_{r,l+o_{l}}|^{2}.$

We conclude by observing that both terms are bounded, uniformly in $k$, per
(A.4). ∎

Proceeding to generalize the computation in Lemma A.2 to other higher order
terms in perturbation expansions, we first prove a general factorization
property of the Green’s functions on directed trees.

######  Lemma A.3.

Denote by $p$ the path in $\mathcal{T}$, $\mathcal{T}_{1}$, or
$\mathcal{T}_{2}$, between two indices $x$ and $y$ (each being either $u$ or
$u+\aleph$ for some vertex $u$). For $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$,
specify the root as $r$ and denote by $x\wedge y$ the common ancestor of $x$
and $y$ of the largest depth. Let $E_{v}$ denote the types of the pair of
edges in $p$ adjacent to each vertex $v\in p$ (i.e., whether they are in-edges
or out-edges). For some explicit function $K(E)\leq\frac{1}{\sqrt{d-1}}$
depending only on $z,w,d$ and the edge types and some universal constant $C$,
we have the following bound on the corresponding Green’s function

(A.10) $|G_{x,y}|\leq C\prod_{\begin{subarray}{c}v\in p\\\ v\neq x,y,x\wedge
y\end{subarray}}K(E_{v}),$

uniformly over $w\in\mathbb{D}$, a fixed compact region in $\mathbb{C}$ (where
$v\neq x\wedge y$ means that $v$ is not the ancestor of the points $x$ and $y$
on the path to the root in $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$.)

######  Remark A.4.

While this shows that $G_{x,y}$ has ‘nice’ factorization properties, one has
to be careful here. Indeed, (A.10) is more complicated due to the dependence
of $G_{x,y}$ on the specific orientations along the path connecting $x$ and
$y$.

###### Proof.

In principle, this factorization is a consequence of the Schur complement
formula. However, as mentioned, one has to be aware of the orientations along
$p$ while performing a case by case analysis. First, if either the index $x$
or $y$ corresponds to the root vertex, then (A.10) is fairly straightforward.
Indeed, as we saw in the recursions (A.5)-(A.6) leading to Lemma A.2, in this
case each of the $K(E_{v})$ is the absolute value of one of
$(G_{\mathcal{T}_{1}})_{v+\aleph,v},(G_{\mathcal{T}_{1}})_{v+\aleph,v+\aleph},(G_{\mathcal{T}_{2}})_{v,v}$
or $(G_{\mathcal{T}_{2}})_{v,v+\aleph}$ times $\frac{1}{\sqrt{d-1}}$. Further,
for any intermediate vertex $v\in p$, $v\neq x,y$, the specific Green’s
function entry to choose among these four options depends only on the
orientation of the edges along $p$ immediately before it and immediately after
it. Each of the factors corresponding to our pair of fixed indices $x$ and $y$
is covered by a universal finite constant $C_{0}$ as long as $|w|$ is
uniformly bounded.

Since $\mathcal{T}$ is regular, in that case we shall assume with no loss of
generality that $x$ is the root. The more delicate case is when neither of $x$
or $y$ are at the root in either $\mathcal{T}_{1}$ or $\mathcal{T}_{2}$. Due
to duality, it suffices to proceed with the detailed analysis only for
$\mathcal{T}_{1}$, and we assume first that $x\wedge y\neq r$ and denote by
$\ell\geq 1$ the length of the path $p_{x\wedge y}$ from $r$ to $x\wedge y$.
Denoting by $c$ the child of $r$ which is on this path, upon removing the edge
from $r$ to $c$, we get from (1.13) that

(A.11)
$G_{x,y}=G^{(r)}_{x,y}+\frac{1}{d-1}G^{(r)}_{x,c+\tilde{o}}(G_{\mathcal{T}_{1}})_{c+o,c+o}G^{(r)}_{c+\tilde{o},y}$

$o$ and $\tilde{o}$ are either $\aleph$ or $0$ depending on the orientation of
the edge connecting $c$ to $r$. The quantity $(G_{\mathcal{T}_{1}})_{c+o,c+o}$
is either $m_{\infty}$ or $m_{\infty}^{sd}$ and in either case bounded in
absolute value by the universal, finite $C_{0}$. Note that the tree
$\mathcal{T}_{1}^{(r)}$ after the removal of $r$ is either a $\mathcal{T}_{1}$
rooted at $c$ or a $\mathcal{T}_{2}$ rooted at $c$. Thus, following
(A.5)-(A.6) yields the product bound of (A.10) for both
$G^{(r)}_{x,c+\tilde{o}}$ and $G^{(r)}_{c+\tilde{o},y}$. Combining the latter
two bounds gives the terms $K(E_{v})$ for all vertices $v\in p$ except
possibly $x$, $y$ and $x\wedge y$, as well as the product of
$K(E_{u})^{2}\leq\frac{1}{d-1}$ over all $u\in p_{x\wedge y}$, $u\neq r$.
Consequently,

$|G_{x,y}|\leq|G^{(r)}_{x,y}|+C_{0}^{3}(d-1)^{-\ell}\prod_{\begin{subarray}{c}v\in
p\\\ v\neq x,y,x\wedge y\end{subarray}}K(E_{v})\,.$

By the preceding reasoning, when starting with $G^{(r)}_{x,y}$ instead of
$G_{x,y}$, we get the same bound on the second term on the rhs of (A.11),
except for reducing $\ell$ by one. Thus, setting
$\widehat{C}_{i}=C_{0}^{3}\sum_{k\geq i}(d-1)^{-k}$, $i\geq 0$, and iterating
till all that remains from $p_{x\wedge y}$ is the common ancestor $x\wedge y$,
we conclude that

(A.12)
$|G_{x,y}|\leq|(G_{\mathcal{T}^{(\star)}})_{x,y}|+\widehat{C}_{2}\prod_{\begin{subarray}{c}v\in
p\\\ v\neq x,y,x\wedge y\end{subarray}}K(E_{v})\,,$

where $\mathcal{T}^{(\star)}$ is either a $\mathcal{T}_{1}$ tree or a
$\mathcal{T}_{2}$ tree, now rooted at $x\wedge y$. Turning to deal with
$|(G_{\mathcal{T}^{(\star)}})_{x,y}|$, we appeal once more to (1.13), where
since now $r=x\wedge y$, the first term on the rhs is zero at $x,y$. Assuming
wlog that $\mathcal{T}^{(\star)}$ is a $\mathcal{T}_{1}$ tree and with
$c_{x}\neq c_{y}$ denoting the children of $x\wedge y$ along the path $p_{x}$
and $p_{y}$ leading in that tree to $x$ and $y$ respectively, we find that

(A.13)
$(G_{\mathcal{T}^{(\star)}})_{x,y}=\frac{1}{d-1}G^{(\star)}_{x,c_{x}+\tilde{o}_{1}}(G_{\mathcal{T}_{1}})_{r+o_{1},r+o_{2}}G^{(\star)}_{c_{y}+\tilde{o}_{2},y},$

where $G^{(\star)}$ denotes the Green function of
$\mathcal{T}^{(\star)}\backslash(x\wedge y)$, and $\tilde{o}_{i}$, $o_{i}$ are
$0$ or $\aleph$, depending on the types of edges connecting $c_{x}$ and
$c_{y}$ to $x\wedge y$. We use as before the factorization properties of the
disjoint sub-trees of $\mathcal{T}^{(\star)}\backslash(x\wedge y)$ containing
$x$ and $y$, to see that

$|G^{(\star)}_{x,c_{x}+\tilde{o}_{1}}|\leq C_{0}\prod_{\begin{subarray}{c}v\in
p_{x}\\\ v\neq x,x\wedge
y\end{subarray}}K(E_{v})\,,\qquad|G^{(\star)}_{c_{y}+\tilde{o}_{2},y}|\leq
C_{0}\prod_{\begin{subarray}{c}v\in p_{y}\\\ v\neq y,x\wedge
y\end{subarray}}K(E_{v})\,.$

Plugging the latter bounds and our usual bound
$|(G_{\mathcal{T}_{1}})_{r+o_{1},r+o_{2}}|\leq C_{0}$ into (A.13) then
combining with (A.12), we finally arrive at (A.10) (with $C=\widehat{C}_{1}$ a
universal constant). ∎

Building on the preceding factorization property and bounding the expressions
$\\{K(E_{v})\\}$, we now generalize Lemma A.2, starting at any
$x\in\mathcal{T}_{1}$ (and not only at its root).

######  Lemma A.5.

Let $\mathcal{K}_{xy}$ denote the rhs of (A.10). Then, for the tree
$\mathcal{T}_{1}$ with root $r$, uniformly in $k\geq 1$, $w\in\mathbb{D}$
compact and $x\in\mathcal{T}_{1}$,

(A.14) $\sum_{y\in B_{k}(x)}|\mathcal{K}_{xy}|^{2}\lesssim k.$

###### Proof.

Let $p_{x}$ denote the path from $x$ to the root $r$. Let $v_{l}$ denote the
vertex on $p_{x}$ that is of distance $l$ from $x$. We let $C(v_{l})$ denote
the children of $v_{l}$ that are of distance less than $k-l$ from $v_{l}$
aside from those that can only reached using an edge of $p_{x}$. The product
expression (A.10) gives us,

(A.15) $\sum_{y\in
B_{k}(x)}|\mathcal{K}_{xy}|^{2}=\sum_{l=0}^{k}\left(\frac{1}{d-1}\right)^{l-1}\sum_{z\in
C(v_{l})}|\mathcal{K}_{v_{l}z}|^{2}.$

Now, our main observation is that $|\mathcal{K}_{v_{l}z}|^{2}$ can be roughly
understood as $|P_{v_{l}z}|^{2}$ in a tree that uses $v_{l}$ as a root. More
formally, let $ch^{l}_{1},\ldots,ch^{l}_{2d-2}$ denote the direct children of
$v_{l}$ in $C(v_{l})$ and let $C(ch^{l}_{m})$ denote the children of
$ch^{l}_{m}$ in $C(v_{l})$, while we let $T_{ch^{l}_{m}}$ denote the tree with
root $ch^{l}_{m}$. We see we have,

(A.16) $\sum_{z\in
C(v_{l})}|\mathcal{K}_{v_{l}z}|^{2}=\sum_{m=1}^{2d-1}\sum_{z\in
C(ch^{l}_{m})}|G_{ch^{l}_{m},z}|^{2}.$

Each of the internal sums on the right hand side can be explicitly computed
and shown to be $\lesssim k-l$ by Lemma A.2. The outer sum will just give a
constant factor outside. Finally, we can evaluate the full sum in equation
(A.15). The summability of the exponential series will show that this will be
bounded by some universal constant times $k$, as desired. ∎

The following lemma allows us to generalize our bounds on the decay of Green’s
function values with distance to the case of almost tree-like graphs with at
most one cycle. The most important part is the relation of the Green’s
function of the graph to the Green’s function of the simply connected cover,
which is the infinite tree.

######  Lemma A.6.

Consider a digraph $\mathcal{G}$ with excess at most 1; let $i$ and $j$ be
vertices in $\mathcal{G}$. Let $p_{1}$ be the shortest path connecting $i$ and
$j$ in $\mathcal{G}$ and let $p_{2}$ be the second shortest non-backtracking
path connecting $i$ and $j$ in $\mathcal{G}$. Furthermore, let $sp_{1}$ be a
sequence of letters $f$ or $r$ indicating whether each edge in the path
$p_{1}$ were traversed in the forward or reverse direction, and let $sp_{2}$
be the same object for the path $p_{2}$. Given these sequences $sp_{1}$ and
$sp_{2}$, consider the ‘pure’ infinite tree $\mathcal{T}$ and vertices $v_{1}$
and $v_{2}$ in $\mathcal{T}$ that are reachable from the root $r$ using a
sequences of edges that match $sp_{1}$ and $sp_{2}$, respectively. For
example, if $sp_{1}$ involved only forward edges, then $v_{1}$ should be a
vertex that is reachable from $r$ using only forward edges.

We can derive the following estimate on the Green’s function extension,

(A.17)
$\displaystyle|G(Ext(\mathcal{G},m_{\infty},m_{\infty}))_{i+o_{i},j+o_{j}}|$
$\displaystyle\lesssim|(G_{\mathcal{T}})_{r+o_{i},v_{1}+o_{j}}|+|(G_{\mathcal{T}})_{r+o_{i},v_{2}+o_{j}}|$
$\displaystyle\lesssim\left[\frac{\max\\{|m_{\infty}|,|m^{uod}_{\infty}|\\}}{\sqrt{d-1}}\right]^{\text{dist}(i,j)}.$

Here, $o_{i}$ and $o_{j}$ can be $0$ or $\aleph$ to distinguish the two
indices that correspond to the same vertex.

######  Remark A.7.

In the top line of the preceding bound, we distinguish the specific edges that
are used in the path connecting $i$ and $j$ in order to be able to derive
sharp bounds when large neighborhoods are considered.

###### Proof.

The extension of $Ext(\mathcal{G},m_{\infty},m_{\infty})$ involves adding an
appropriate infinite tree to every boundary vertex of the digraph
$\mathcal{G}$ that does not yet have full degree. Since we have assumed that
the digraph $\mathcal{G}$ has excess at most 1, this would imply that there is
at most one cycle in the extension graph.

Now, we can always relate the Green’s function of a graph to its infinite
cover as follows. First, we remark that the Green’s function is the unique
solution to the following system of equations,

(A.18)
$\displaystyle\delta_{ik}+zG_{ik}=wG_{\aleph+i,k}+\frac{1}{\sqrt{d-1}}\sum_{(i\to
j)\in E}G_{\aleph+j,k}$ $\displaystyle
zG_{i,\aleph+k}=wG_{\aleph+i,\aleph+k}+\frac{1}{\sqrt{d-1}}\sum_{(i\to j)\in
E}G_{\aleph+j,\aleph+k}$ $\displaystyle
zG_{\aleph+i,k}=\overline{w}\,G_{ik}+\frac{1}{\sqrt{d-1}}\sum_{(j\to i)\in
E}G_{j,k}$
$\displaystyle\delta_{ik}+zG_{\aleph+i,\aleph+k}=\overline{w}\,G_{i,\aleph+k}+\frac{1}{\sqrt{d-1}}\sum_{(j\to
i)\in E}G_{\aleph+j,\aleph+k}.$

We argue that if we have a new graph $\hat{H}$, with Green’s function
$\hat{G}$, that is a lift of the graph $H$, with covering map $\pi$. Then, we
would have the following relationship between the Green’s function $G$ of the
original graph and the Green’s function of the covering graph.

(A.19) $\displaystyle G_{ij}=\sum_{y:\pi(y)=j}G_{xy}$ $\displaystyle
G_{\aleph+i,j}=\sum_{y:\pi(y)=j}G_{\aleph+x,y}$ $\displaystyle
G_{i,j+\aleph}=\sum_{y:\pi(y)=j}G_{x,\aleph+y}$ $\displaystyle
G_{i+\aleph,j+\aleph}=\sum_{y:\pi(y)=j}G_{x+\aleph,y+\aleph}.$

Here, $x$ is a vertex in $\hat{H}$ that maps to $i$ under the map $\pi$; the
value on the right hand side does not depend on the choice of $x$ due to
translation invariance. It is implicitly implied that the above results hold
as long as the quantities that appear on the right hand side are convergent.
In order to check the above relation, we substitute the proposed equalities in
equation (A.19) into the defining equations of equation (A.18) and check that
equality holds. This mainly involves realizing that if we choose $\hat{i}$ so
that $\pi(\hat{i})=i$, then we can parameterize the vertices $j$ such that
$i\to j$ is an edge by some lifted vertex $\hat{j}$ such that $\pi(\hat{j})=j$
and $\hat{i}\to\hat{j}$ is a edge in $\hat{H}$. This confirms the first two
equations in equation (A.18). We can do the same thing for edges $j\to i$ as
well, and this verifies the last two equations of (A.18).

We can use the above formula to compute the Green’s function of
$Ext(\mathcal{G},m_{\infty},m_{\infty})$ by setting
$H=Ext(\mathcal{G},m_{\infty},m_{\infty})$ . This graph has only one cycle due
to our assumption on the excess; thus, the covering graph $\hat{H}$ is an
infinite tree. The preimage of any vertex $i\in H$ will correspond to the set
of non-backtracking paths in $\hat{H}$. $\sum_{y:\pi(y)=j}$ now merely
correspond to a ‘sum’ over non-backtracking paths.

For points $i$ and $j$ that are of distance $k$ in $H$, the non-backtracking
paths all have lengths at least $k$ and the different non-backtracking paths
have length that differ by $|C|$ where $|C|$ is the length of the unique
simple cycle in $H$. Recall that $p_{1}$ was the shortest path between $i$ and
$j$ while $p_{2}$ was the second-shortest non-backtracking path between $i$
and $j$. We have the following structural properties on the paths $p_{j}$. We
can divide $p_{2}$ as $Q_{i}\cup C\cup Q_{o}$ where $C$ is the cycle and
further shortest backtracking paths $p_{j}$ are $Q_{i}\cup C\cup\ldots\cup
C\cup Q_{o}$ where there are $j-1$ copies of $C$. The path $p_{1}$ must be
either included completely in $Q_{o}$ or equal to the union $Q_{i}\cup Q_{o}$.

We also have the following property, let $v$ be a fixed lift of $i$ in
$\hat{H}$ and $w_{1}$ be the lift of $j$ in $\hat{H}$ that is closest to $v$.
Then, if $\hat{p}_{1}$ is the path between $v$ and $w_{1}$, and $\hat{sp}_{1}$
is the set of labels ( either $f$ or $b$) of the edges of $\hat{p}_{1}$, then
$\hat{sp}$ is the same sequence as $sp_{1}$. In addition, let $w_{2}$ is the
lift of $j$ in $\hat{H}$ that is the second closest to $v$. If $\hat{p}_{2}$
is the path between $v$ and $w_{2}$, and $\hat{sp}_{2}$ is the set of labels
of this path, then $\hat{sp}_{2}$ is the same as $sp_{2}$.

Thus, we see that

$\displaystyle|G_{ij}(Ext(\mathcal{G},m_{\infty},m_{\infty})|\leq\sum_{n=1}^{\infty}|(G_{\mathcal{T}})_{v,w_{n}}|\leq|(G_{\mathcal{T}})_{v,w_{1}}|+|(G_{\mathcal{T}})_{v,w_{2}}|\frac{1}{1-\frac{|m_{\infty}|\vee|m_{\infty}^{uod}|}{\sqrt{d-1}}}.$

Here, $w_{n}$ is the $n$th closest lift of $j$ to $v$. To derive the final
inequality, we used the decomposition of $G$ found in Lemma A.5. The paths
$p_{j}$ have $(j-1)|C|$ more $K$ factors than $p_{2}$. We can thus apply a
geometric sum for these terms. ∎

As a simple corollary of this estimate, we can readily show that we have the
same type of estimate for the first order term in perturbation series as in
Lemma A.2. Later, we will show more general estimates.

######  Corollary A.8.

Let $\mathcal{G}$ be a graph with excess at most $1$. Fix a vertex $i$ in
$\mathcal{G}$ and let $R_{k}$ denote all of the vertices in $\mathcal{G}$ of
distance exactly $k$ from $i$ in $\mathcal{G}$. Then, we have the following
estimate,

(A.20) $\sum_{j\in
R_{k}}|G_{ij}(Ext(\mathcal{G},m_{\infty},m_{\infty})|^{2}\lesssim 1.$

###### Proof.

A graph with excess $0$ would correspond to an infinite tree after the
expansion, so this estimate is already known.

We can understand graphs of excess $1$ by, again, referring to the infinite
cover of the tree. Recall that we have,

(A.21)
$G_{ij}(Ext(\mathcal{G},m_{\infty},m_{\infty})=\sum_{l=1}^{\infty}(G_{\mathcal{T}})_{vw_{l}},$

where $v$ is a fixed lift of $i$ and $w_{l}$ is a set of lifts of $w$ in order
from closest to most distant. Furthermore if $j$ is of distance $k$ from $i$
then $w_{1}$ is of distance $k$ from $v$ and $w_{2}$ is of distance $\geq
k+|C|$ from $v$.

The Cauchy-Schwartz inequality will show that,

(A.22)
$|\sum_{l=1}^{\infty}(G_{\mathcal{T}})_{vw_{l}}|^{2}\leq\sum_{l=1}^{\infty}|(G_{\mathcal{T}})_{vw_{l}}|^{2}e^{l\theta}\sum_{l=1}^{\infty}e^{-l\theta}\lesssim|(G_{\mathcal{T}})_{vw_{1}}|^{2}+|(G_{\mathcal{T}})_{vw_{2}}|^{2}.$

Setting
$\theta=-\frac{1}{2}\log\frac{|m_{\infty}|\vee|m_{\infty}^{uod}|}{\sqrt{d-1}}$,
makes sure that the infinite sum $\sum_{l=1}^{\infty}e^{-l\theta}$ is finite.
Furthermore, $|(G_{\mathcal{T}})_{vw_{l}}|^{2}e^{l\theta}$ will still have
exponential decay since the factor $e^{\theta}$ is chosen to be smaller than
the ratio $\frac{(G_{\mathcal{T}})_{vw_{l-1}}}{(G_{\mathcal{T}})_{vw_{l}}}$.

By applying this inequality to all vertices $j$ that are in $R_{k}$, we see
that we can bound,

(A.23) $\sum_{j\in
R_{k}}|G_{ij}(Ext(\mathcal{G},m_{\infty},m_{\infty})|^{2}\lesssim\sum_{w\in
S_{k}\cup S_{k+|C|}}|(G_{\mathcal{T}})_{v,w}|^{2}\lesssim 1.$

Here, $S_{k}$ denotes the elements that are of distance $k$ from $v$ in
$\mathcal{T}$. ∎

###  A.2. Comparison of Stieltjes transforms

######  Lemma A.9.

We show the following equality between the Stieltjes transform proposed in
equations (1.18) and those coming from free probability computations as in
[3]:

$m_{\mathcal{T}}^{d}(z,w)=\sqrt{d-1}m_{\star}(\sqrt{d-1}z,\sqrt{d-1}w).$

###### Proof.

First, notice that if we remove the scaling of edges in the adjacency matrix
by $\frac{1}{\sqrt{d-1}}$ , then the corresponding equations for $m_{\infty}$
and $m_{\mathcal{T}}^{d}$ would be,

(A.24) $\displaystyle
m_{\infty}=\frac{z+dm_{\infty}}{|w|^{2}-\big{(}z+dm_{\infty}\big{)}(z+(d-1)m_{\infty})},$
$\displaystyle
m_{\mathcal{T}}^{d}=\frac{z+dm_{\infty}}{|w|^{2}-\big{(}z+dm_{\infty}\big{)}^{2}}.$

Consider $\mathcal{T}_{d}$, our infinite $d$-regular digraph tree; from this,
pick a subgraph $S_{d-1}$ in $\mathcal{T}_{d}$ that is isomorphic to the
infinite $d-1$ regular tree $\mathcal{T}_{d-1}$. For every vertex $v$ that is
part of $S_{d-1}$, there will be one edge, $i_{v}$, into it and one edge,
$o_{v}$, out of it that will be part of the original graph $\mathcal{T}_{d}$,
but will not be part of the subgraph $S_{d-1}$. If we remove the edge $o_{v}$,
the connected component remaining that is totally disjoint from $S_{d-1}$ will
be isomorphic to $\mathcal{T}_{1}$ (the $2d-1$-ary tree). If we remove
$i_{v}$, the connected component remaining that is totally disjoint from
$S_{d-1}$ will be isomorphic to $\mathcal{T}_{2}$. For $|z|>(d-1)+|w|^{2}$, we
compute the Green’s function of the Hermitized (unscaled) adjacency matrices
of $\mathcal{T}_{d}$ by counting paths and carefully tracking where such paths
uses edges of $S_{d-1}$. (We will naturally consider $w$ and $w^{*}$ to
correspond to a weighted self-loops at the appropriate vertex.)

Consider trying to compute $(G_{\mathcal{T}_{d}})_{rr}$ at the root $r$. For
its first step, it could either take an edge that is part of $S_{d-1}$ or else
it could take the outedge $o_{r}$. If the path takes the outedge $o_{r}$, the
path will perform a walk in $\mathcal{T}_{1}$ before returning to the root by
traversing $o_{r}$ in the reverse direction. The weighted contribution of
paths that take this option would be $\frac{m_{\infty}(z)}{z}$, corresponding
to the weighted contribution of walks that return to the root in
$\mathcal{T}_{1}$. Before the walk takes an edge that is part of $S_{d-1}$, it
could repeat this process indefinitely. Thus, the total weighted contribution
of paths that could occur before the walk’s first step in $S_{d-1}$ is,

$\sum_{k=0}^{\infty}\left(\frac{m_{\infty}}{z}\right)^{k}=\frac{1}{1-\frac{m_{\infty}}{z}}.$

If the path takes an edge that is part of $S_{d-1}$ to get to the vertex $p$,
we can repeat a similar argument. Either the next step after this is also a
part of $S_{d-1}$ or it could take the inedge $i_{p}$. (Note that this is
still true if we took the weighted edge corresponding to the self loop.) We
can count the contribution of all paths that use the inedge $i_{p}$ as
$\frac{1}{1-\frac{m_{\infty}}{z}}$. If we repeat this argument as we traverse
edges of $S_{d-1}$ we see that $m_{\mathcal{T}}^{d}$ can be expressed as
follows. Let $\mathcal{S}_{k}$ denote the total weight of all paths in
$S_{d-1}$ that use $k$ edges.

(A.25)
$m_{\mathcal{T}}^{d}=\frac{1}{z}\sum_{k=0}^{\infty}\frac{\mathcal{S}_{k}}{z^{k}}\left(\frac{1}{1-\frac{m_{\infty}(z)}{z}}\right)^{k+1}.$

Thus,

(A.26)
$m^{d}_{\mathcal{T}}=m^{d-1}_{\mathcal{T}}\left(z-m_{\infty}(z)\right).$

If we return to the equations in (A.24), we find that,

(A.27)
$\frac{1}{m^{d}_{\mathcal{T}}}=\frac{|w|^{2}}{z+dm_{\infty}}-(z+dm_{\infty})=\frac{|w|^{2}}{z+dm_{\infty}(z)}-(z+(d-1)m_{\infty})-m_{\infty}(z)=-m_{\infty}(z)+\frac{1}{m_{\infty}}.$

Solving the quadratic gives,

(A.28) $m_{\infty}=\frac{-1+\sqrt{1+4m_{d}^{2}}}{2m_{d}}.$

Returning to equation (A.26), we see that,

(A.29)
$m^{d}_{\mathcal{T}}(z)=m^{d-1}_{\mathcal{T}}\left(z-\frac{2m^{d}_{\mathcal{T}}}{1+\sqrt{1+4(m^{d}_{\mathcal{T}})^{2}}}\right).$

This is the same recursion as in equation (4.6) of [3]. Notice that though we
only confirmed the identity for $|z|\geq(d-1)+|w|^{2}$, the identity would
hold for all values of $z$ by analytic continutation. To fully confirm the
equality of Green’s functions, it suffices to show the equality of Green’s
functions when $d=1$.

When $d=1$, we have to solve the quadratic,

(A.30)
$m_{\infty}^{2}+m_{\infty}\left[z+\frac{1}{z}-\frac{|w|^{2}}{z}\right]+1=0.$

Setting the quantity $A=z+\frac{1}{z}-\frac{|w|^{2}}{z}$, we see that we have,

(A.31) $m_{\infty}=\frac{-A-\sqrt{A^{2}-4}}{2},$

and, using (A.27), we see that,

(A.32) $\displaystyle m^{1}_{\mathcal{T}}$
$\displaystyle=-\frac{1}{\sqrt{A^{2}-4}}=-\frac{1}{\sqrt{\left(z+\frac{1}{z}-\frac{|w|^{2}}{z}\right)^{2}-4}}$
$\displaystyle=-\frac{z}{\sqrt{\left(z^{2}+1-|w|^{2}\right)^{2}-4z^{2}}}$
$\displaystyle=-\frac{z}{\sqrt{\left(z^{2}+2z+1-|w|^{2})(z^{2}-2z+1-|w|^{2}\right)}}$
$\displaystyle=-\frac{z}{\sqrt{\left((z+1)^{2}-|w|^{2})((z-1)^{2}-|w|^{2}\right)}}$
$\displaystyle=-\frac{z}{\sqrt{(z+1-|w|)(z+1+|w|)(z-1-|w|)(z-1+|w|)}}$
$\displaystyle=-\frac{z}{\sqrt{(z^{2}-(1-|w|)^{2})(z^{2}-(1+|w|)^{2})}}.$

This Green’s function can be checked to correspond to the density of equation
(4.1) in [3]. ∎

## References

  * [1] G.W. Anderson, A. Guionnet, and O. Zeitouni.  An introduction to random matrices, volume 118 of Cambridge Stud. Adv. Math. Cambridge Univ.Press , Cambridge, UK, 2010.
  * [2] A. Basak, N. Cook, and O. Zeitouni.  Circular law for the sum of random permutation matrices.  Electron. Jour. Probab., 23(33):1–51, 2018.
  * [3] A. Basak and A. Dembo.  Limiting spectral distribution of sums of unitary and orthogonal matrices.  Electron. Commun. Probab., 18(69):1–19, 2013.
  * [4] R. Bauerschmidt, J. Huang, and H.-T. Yau.  Local Kesten-McKay law for random regular graphs.  Comm. Math. Phys., 369(2):523 –636, 2019.
  * [5] R. Bauerschmidt, A. Knowles, and H.-T. Yau.  Local semicircle law for random regular graphs.  Comm. Pure Appl. Math, 70(10):1898 –1960, 2017.
  * [6] C. Bordenave and D. Chafai.  Around the circular law.  Probability Surveys, 9:1–89, 2012.
  * [7] V. Girko.  The circular law.  Teor. Veroyatnost. i Primenen, 29(4):669–679, 1984.
  * [8] A. Guoinnet, M. Krishnapur, and O. Zeitouni.  The single ring theorem.  Ann. of Math., 174(2):1189–1217, 2011.
  * [9] A. Guoinnet, P. Wood, and O. Zeitouni.  Convergence of spectral measure of non normal matrices.  Proc. AMS, 142(2):667–679, 2014.
  * [10] U. Haagerup and F. Larsen.  Brown’s spectral distribution measure for R-diagonal elements in finite von Neumann algebras.  J. Funct.Anal., 176:331–367, 2000.
  * [11] J. Huang.  Invertibility of adjacency matrices for random d-regular graphs.  Duke Math. Jour., 170(18):3977 –4032, 2021.
  * [12] J. Huang and H.-T. Yau.  Spectrum of random d-regular graphs up to the edge.  arXiv:2102..00963v2, 2021.
  * [13] A. Litvak, A. Lytova, T. Tikhomirov, N. Tomczak-Jaegarmann, and Y. Youssef.  The smallest singular value of a shifted d-regular random square matrix.  arXiv:1707.02635v3, 2018.
  * [14] L. Litvak and T. Tikhomirov.  Singularity of sparse Bernoulli matrices.  Duke Math. Jour., 171(5):1135–1233, 2022.
  * [15] C. Male.  The distribution of traffics and their free product: an asymptotic freensess theorem for random matrices and a central limit theorem.  arxiv:1111.4662v3.
  * [16] M. Rudelson and R. Vershynin.  Invertibility of random matrices: unitary and orthogonal perturbations.  Bulletin of the American Mathematical Society, 27(2):293–338, 2014\.
  * [17] P. Sniady.  Random regularization of Brown spectral measure.  J. Funct. Anal., 193:291–313, 2002.
  * [18] T. Tao and V. Vu.  Random matrices: universality of ESDs and the circular law,.  Ann. Probab., 38(5):2023–2065, 2010.