$\displaystyle{\mathcal{H}}^{\Lambda,\tau}_{G}(ws,uz)$
$\displaystyle={{\mathcal{I}}}^{M,\sigma}_{G_{w,u}}(ws,uz),$
$\displaystyle{\mathcal{H}}^{\Lambda,\tau}_{G}(uz,ws)$
$\displaystyle={{\mathcal{I}}}^{M,\sigma}_{G_{w,u}}(uz,ws)\enspace.$ (11.13)

Both entries ${{\mathcal{I}}}^{M,\sigma}_{G_{w,u}}(ws,uz)$ and
${{\mathcal{I}}}^{M,\sigma}_{G_{w,u}}(uz,ws)$ are with respect to the measure
$\upnu^{M,\sigma}$ which is the $\\{ws,uz\\}$-extension of
$\mu^{\Lambda,\tau}_{G}$. Recall that $\upnu^{M,\sigma}$ is a Gibbs
distribution on $G_{w,u}$, where $(M,\sigma)$ is obtained from
$(\Lambda,\tau)$.

Then, from Claim 4.1 we have that

$\displaystyle{{\mathcal{I}}}^{M,\sigma}_{G_{w,u}}(ws,uz)$
$\displaystyle=\frac{\upnu^{M,\sigma}_{uz}(1)\cdot\upnu^{M,\sigma}_{uz}(-1)}{\upnu^{M,\sigma}_{ws}(1)\cdot\upnu^{M,\sigma}_{ws}(-1)}\cdot{{\mathcal{I}}}^{M,\sigma}_{G_{w,u}}(uz,ws)\enspace.$
(11.14)

Combining (11.14) and (11.13) we get that

$\displaystyle{\mathcal{H}}^{\Lambda,\tau}_{G}(ws,uz)$
$\displaystyle=\frac{\upnu^{M,\sigma}_{uz}(1)\cdot\upnu^{M,\sigma}_{uz}(-1)}{\upnu^{M,\sigma}_{ws}(1)\cdot\upnu^{M,\sigma}_{ws}(-1)}\cdot{\mathcal{H}}^{\Lambda,\tau}_{G}(uz,ws)\enspace.$
(11.15)

Then, (11.12) follows noting that
$\max_{ws,uz}\left\\{\frac{\upnu^{M,\sigma}_{uz}(1)\cdot\upnu^{M,\sigma}_{uz}(-1)}{\upnu^{M,\sigma}_{ws}(1)\cdot\upnu^{M,\sigma}_{ws}(-1)}\right\\}\leq
b^{-2}$. The bound follows by noting that, since $\mu^{\Lambda,\tau}_{G}$ is
assumed to be $b$-marginally bounded, we have that $\upnu^{M,\sigma}$ is
$b$-marginally bounded, too.

All the above conclude the proof of Claim 11.4. ∎

Plugging the bound from Claim 11.4 into (11.10) we get that

$\displaystyle\left|\left|{{\mathcal{I}}}^{\Lambda,\tau}_{G}\right|\right|_{2}$
$\displaystyle\leq
1+b^{-6}\cdot{\Delta}\cdot\textstyle\left|\left|{}^{-1}\cdot\
{\mathcal{H}}^{\Lambda,\tau}_{G}\cdot\UpD\right|\right|_{\infty}\enspace.$
(11.16)

Let ${\upkappa}_{1}$ be the eigenvector that corresponds to the maximum
eigenvalue of G. Recall that ${\upkappa}_{1}$ is indexed by $M$, the set of
oriented edges of $G$. Note that since we have assumed that G is irreducible,
for any $xv\in M$ we have that

$\displaystyle{\upkappa}_{1}(xv)>0\enspace.$ (11.17)

Let $\Upphi$ be the ${\mathcal{S}}_{\Lambda}\times{\mathcal{S}}_{\Lambda}$
diagonal matrix such that for any $xv\in{\mathcal{S}}_{\Lambda}$ we have that

$\displaystyle\Upphi(xv,xv)$ $\displaystyle={\upkappa}_{1}(vx)\enspace,$
(11.18)

note that the argument $vx$ refers to the oriented edge from $v$ to $x$. One
needs to be cautious about the direction of the edge in the component of
${\upkappa}_{1}$ for the diagonal entries of $\Upphi$.

We further note that, due to (11.17), the diagonal entries of $\Upphi$ are all
positive, hence the matrix is non-singular. Setting $\UpD=\Upphi$ in (11.16)
we get that

$\displaystyle\left|\left|{{\mathcal{I}}}^{\Lambda,\tau}_{G}\right|\right|_{2}$
$\displaystyle\leq
1+b^{-6}\cdot{\Delta}\cdot\textstyle\left|\left|\Upphi^{-1}\cdot{\mathcal{H}}^{\Lambda,\tau}_{G}\cdot\Upphi\right|\right|_{\infty}\enspace.$
(11.19)

Then, using Theorem 11.3 and working as in the proof of Theorem 5.5 we get
that

$\displaystyle\left|\left|\Upphi^{-1}\cdot{\mathcal{H}}^{\Lambda,\tau}_{G}\cdot\Upphi\right|\right|_{\infty}$
$\displaystyle\leq
c\cdot(1-(1-\varepsilon)^{1/s})^{-1}\cdot\max_{wx\in{\mathcal{S}}_{\Lambda}}\left\\{{\textstyle\left(\frac{{\upkappa}_{1}(wx)}{{\upkappa}_{1}(xw)}\right)^{1/s}}\right\\}$
$\displaystyle\leq\frac{\zeta}{\uptheta}\cdot{\hat{c}}\cdot(1-(1-\varepsilon)^{1/s})^{-1}\enspace.$

The last inequality follows since we have assumed that
${}_{G}\in{\mathbb{H}}_{n,{\hat{c}}}$ while $c=\zeta/\uptheta$. Then, we have
that

$\displaystyle\left|\left|{{\mathcal{I}}}^{\Lambda,\tau}_{G}\right|\right|_{2}$
$\displaystyle\leq
1+b^{-6}\cdot\zeta\cdot{\hat{c}}\cdot(1-(1-\varepsilon)^{1/s})^{-1}\cdot{\Delta}/\uptheta\enspace.$

The above conclude the proof of Theorem 5.6. $\Box$

##  12\. Proof of Theorem 11.2

Let ${\mathcal{F}}^{\Lambda,\tau}_{G}$ be the
${\mathcal{S}}_{\Lambda}\times(V\setminus\Lambda)$ matrix such that the entry
${\mathcal{F}}^{\Lambda,\tau}_{G}(sw,v)$ is as follows: letting
$\upzeta(\cdot\ |\ (N,\xi))$ be the $ws$-extension of
$\mu^{\Lambda,\tau}_{G}$, for $w\neq v$ we have

$\displaystyle{\mathcal{F}}^{\Lambda,\tau}_{G}(ws,v)$
$\displaystyle=\upzeta_{v}(+1\ |\ (N,\xi),\ (ws,+1))-\upzeta_{v}(+1\ |\
(N,\xi),(ws,-1))\enspace,$ (12.1)

If $w=v$, then ${\mathcal{F}}^{\Lambda,\tau}_{G}(ws,v)=0$.

######  Lemma 12.1.

We have that
${{\mathcal{I}}}^{\Lambda,\tau}_{G}=\UpI+\UpK\cdot{\mathcal{F}}^{\Lambda,\tau}_{G}.$

######  Lemma 12.2.

We have that
${\mathcal{F}}^{\Lambda,\tau}_{G}=\left({\mathcal{H}}^{\Lambda,\tau}_{G}\circ{\mathcal{N}}\right)\cdot\UpC$.

Theorem 11.2 follows as a corollary from Lemmas 12.1 and 12.2. $\Box$

###  12.1. Proof of Lemma 12.1

Firstly, note that both ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$ and
$\UpI+\UpK\cdot{\mathcal{F}}^{\Lambda,\tau}_{G}$ are
$(V\setminus\Lambda)\times(V\setminus\Lambda)$ matrices.

For brevity we use ${\mathcal{F}}$ and ${{\mathcal{I}}}$ to denote
${\mathcal{F}}^{\Lambda,\tau}_{G}$ and ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$,
respectively. From the definition of the matrices ${\mathcal{F}},\UpK$ it is a
simple calculation to show that

$\displaystyle\left(\UpK\cdot{\mathcal{F}}\right)(v,v)$ $\displaystyle=0$
$\displaystyle v\in V\setminus\Lambda\enspace.$

The above implies that both ${{\mathcal{I}}}$ and
$\UpI+\UpK\cdot{\mathcal{F}}$ have ones at their diagonal. We focus on the
off-diagonal diagonal elements. It suffices to show that for any $u,w\in
V\setminus\Lambda$, different from each other, we have that

$\displaystyle{{\mathcal{I}}}(w,u)$ $\displaystyle=\sum\nolimits_{ws\in
S_{w}}{\mathcal{F}}(ws,v)\enspace,$ (12.2)

where recall that $S_{w}$ is the set of split-vertices in $G_{w}$.

Let $T=T_{{\rm SAW}}(G,w)$ be the tree of self-avoiding walks in $G$ that
starts from $w$. Also, let $\\{\upbeta(e)\\}$ be the collection of weights
over the edges of $T$ we obtain as described in (6.3). From Proposition 6.1 we
have that

$\displaystyle{{\mathcal{I}}}(w,u)$
$\displaystyle=\sum\nolimits_{P\in{\mathcal{M}}}\prod\nolimits_{e\in
P}\upbeta(e)\enspace,$ (12.3)

where ${\mathcal{M}}$ consists of all paths from the root of ${T_{\rm
SAW}}(w)$ to the set of copies of $u$ in $T$.

Consider now $G_{w}$ the $w$-extension of $G$. Then, for $ws\in S_{w}$ let
$\upzeta(\cdot\ |\ (N,\xi))$ be the $w$-extension of $\mu^{\Lambda,\tau}_{G}$.
Since $\upzeta(\cdot\ |\ (N,\xi))$ is a Gibbs distribution on $G_{w}$, we
apply the construction we describe in Section 6. Specifically, let
$T_{s}=T_{{\rm SAW}}(ws)$ be the tree of self-avoiding walks in $G_{w}$ that
starts from $ws$. We, also, let $\\{\upbeta_{s}(e)\\}$ be the collection of
weights over the edges of $T_{s}$ we obtain as described in (6.3).

Clearly, Proposition 6.1 implies that

$\displaystyle{\mathcal{F}}(ws,u)$
$\displaystyle=\sum\nolimits_{P\in{\mathcal{M}}_{s}}\prod\nolimits_{e\in
P}\upbeta_{s}(e)\enspace,$ (12.4)

where ${\mathcal{M}}_{s}$ consists of all paths from the root of ${T_{\rm
SAW}}(ws)$ to the set of copies of $u$ in $T_{s}$.

The above constructions have some properties that need highlighting: Firstly,
note that $T_{s}$ is identical to the subtree of $T$ which is induced by the
root of $T$, the child of the root which is a copy of $s$, as well as the
descendent of this vertex. Hence, we rearrange the sum in (12.3) and get that

$\displaystyle{{\mathcal{I}}}(w,u)$
$\displaystyle=\sum\nolimits_{s}\sum\nolimits_{P\in{\mathcal{M}}_{s}}\prod\nolimits_{e\in
P}\upbeta(e)\enspace.$ (12.5)

Secondly, if we identify $T_{s}$ as a subtree of $T$, then for all $e\in
T_{s}$ we have that

$\displaystyle\upbeta_{s}(e)$ $\displaystyle=\upbeta(e)\enspace.$ (12.6)

To see the above, note that the weights $\upbeta(e)$ and $\upbeta_{s}(e)$ do
not depend on the marginal distribution at the root of the corresponding tree.
Furthermore, the copy of vertex $s$ that is a child of the root in $T$ has the
same marginal distribution as the corresponding copy of $s$ in the tree
$T_{s}$. Hence, it is straightforward that the rest of the construction gives
the same weights for the two trees.

Combining (12.5) and (12.6), we get that

$\displaystyle{{\mathcal{I}}}(w,u)$
$\displaystyle=\sum\nolimits_{s}\sum\nolimits_{P\in{\mathcal{M}}_{s}}\prod\nolimits_{e\in
P}\upbeta_{s}(e)=\sum\nolimits_{s}{\mathcal{F}}(ws,u)\enspace.$ (12.7)

For the last equality we use (12.4).

Lemma 12.1 follows by noting that (12.7) implies (12.2). $\Box$

###  12.2. Proof of Lemma 12.2

Before we start our proof, it is useful to notice that Lemma 12.1 implies that
the influence matrix ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$ satisfies the
following relation: for any $w,u\in V\setminus\Lambda$ we have that

$\displaystyle{{\mathcal{I}}}^{\Lambda,\tau}_{G}(w,u)$
$\displaystyle=\sum\nolimits_{ws\in
S_{w}}{{\mathcal{I}}}^{M_{s},\sigma_{s}}_{G_{w}}(ws,u)\enspace,$ (12.8)

where note that on the r.h.s. the influence matrix is with respect to $G_{w}$
and $\upzeta(\cdot\ |\ M_{s},\sigma_{s})$, i.e., the $ws$-extension of $G$ and
the Gibbs distribution $\mu^{\Lambda,\tau}_{G}$. The boundary condition
$(M_{s},\sigma_{s})$ is obtained as we describe in (11.2) and (11.5). We use
the subscripts to indicate the dependence of the condition on $ws$. We use
this observation later in the proof.

The lemma follows by showing that for any $w,u\in V\setminus\Lambda$ and any
split-vertex $ws\in S_{w}$, we have that

$\displaystyle{\mathcal{F}}^{\Lambda,\tau}_{G}(ws,u)$
$\displaystyle=\sum\nolimits_{uz\in
S_{u}}{\mathcal{N}}(ws,uz)\cdot{\mathcal{H}}^{\Lambda,\tau}_{G}(ws,uz)\enspace.$
(12.9)

where ${\mathcal{N}}$ is the same matrix as that in the statement of Theorem
11.2 and is specified later.

From the definition of ${\mathcal{F}}^{\Lambda,\tau}_{G}$, we have that
${\mathcal{F}}^{\Lambda,\tau}_{G}(ws,u)$ is the influence of $ws$ to $u$ under
the measure $\upzeta^{M_{s},\sigma_{s}}$, which is the $ws$-extension of
$\mu^{\Lambda,\tau}_{G}$. That is,

$\displaystyle{\mathcal{F}}^{\Lambda,\tau}_{G}(ws,u)$
$\displaystyle={{\mathcal{I}}}^{M_{s},\sigma_{s}}_{G_{w}}(ws,u)=\frac{\upzeta^{M_{s},\sigma_{s}}_{u}(1)\cdot\upzeta^{M_{s},\sigma_{s}}_{u}(-1)}{\upzeta^{M_{s},\sigma_{s}}_{ws}(1)\cdot\upzeta^{M_{s},\sigma_{s}}_{ws}(-1)}\cdot{{\mathcal{I}}}^{M_{s},\sigma_{s}}_{G_{w}}(u,ws)\enspace.$
(12.10)

The second equality follows from Claim 4.1.

Furthermore, applying (12.8) to the entry
${{\mathcal{I}}}^{M_{s},\sigma_{s}}_{G_{w}}(u,ws)$ we get that

$\displaystyle{{\mathcal{I}}}^{M_{s},\sigma_{s}}_{G_{w}}(u,ws)$
$\displaystyle=\sum\nolimits_{uz\in
S_{u}}{{\mathcal{I}}}^{M_{s,z},\sigma_{s,z}}_{G_{w,u}}(uz,ws)=\sum\nolimits_{uz\in
S_{u}}{\mathcal{H}}^{\Lambda,\tau}_{G}(uz,ws)\enspace.$ (12.11)

For the influence matrices in the sum in the middle part, note that each one
of them is with respect to the $\\{uz\\}$-extension of
$\upzeta^{M_{s},\sigma_{s}}$. Let us call this measure
$\upnu^{M_{s,z},\sigma_{s,z}}$, while note that this is the
$\\{ws,uz\\}$-extension of $\mu^{\Lambda,\tau}_{G}$. The second equality
follows from the definition of ${\mathcal{H}}^{\Lambda,\tau}_{G}$, i.e., we
have that

$\displaystyle{{\mathcal{I}}}^{M_{s,z},\sigma_{s,z}}_{G_{w,u}}(uz,ws)$
$\displaystyle={\mathcal{H}}^{\Lambda,\tau}_{G}(uz,ws)$ $\displaystyle\forall
uz\in S_{u}\enspace.$

With the above equality in mind, we apply Claim 4.1 once more and get that

$\displaystyle{\mathcal{H}}^{\Lambda,\tau}_{G}(uz,ws)$
$\displaystyle=\frac{\upnu^{M_{s,z},\sigma_{s,z}}_{ws}(1)\cdot\upnu^{M_{s,z},\sigma_{s,z}}_{ws}(-1)}{\upnu^{M_{s,z},\sigma_{s,z}}_{uz}(1)\cdot\upnu^{M_{s,z},\sigma_{s,z}}_{uz}(-1)}\cdot{\mathcal{H}}^{\Lambda,\tau}_{G}(ws,uz)\enspace.$
(12.12)

Plugging (12.11) and (12.12) into (12.10) we get that

$\displaystyle{\mathcal{F}}^{\Lambda,\tau}_{G}(ws,u)$
$\displaystyle=\sum_{uz\in
S_{u}}\frac{\upzeta^{M_{s},\sigma_{s}}_{u}(1)\cdot\upzeta^{M_{s},\sigma_{s}}_{u}(-1)}{\upzeta^{M_{s},\sigma_{s}}_{ws}(1)\cdot\upzeta^{M_{s},\sigma_{s}}_{ws}(-1)}\cdot\frac{\upnu^{M_{s,z},\sigma_{s,z}}_{ws}(1)\cdot\upnu^{M_{s,z},\sigma_{s,z}}_{ws}(-1)}{\upnu^{M_{s,z},\sigma_{s,z}}_{uz}(1)\cdot\upnu^{M_{s,z},\sigma_{s,z}}_{uz}(-1)}\cdot{\mathcal{H}}^{\Lambda,\tau}_{G}(ws,uz)\enspace.$
(12.13)

We set ${\mathcal{N}}(ws,uz)$ equal to the coefficient of
${\mathcal{H}}^{\Lambda,\tau}_{G}(ws,uz)$ in the above sum.

It remains to prove that for every $ws,uz\in{\mathcal{S}}_{\Lambda}$ we have
$0\leq{\mathcal{N}}(ws,uz)\leq b^{-4}$. Since $\mu^{\Lambda,\tau}_{G}$ is
assumed to be $b$-marginally bounded, it is straightforward that
$\upzeta^{M_{s},\sigma_{s}}$ and $\upnu^{M_{s,z},\sigma_{s,z}}$ are
$b$-marginally bounded, too. Recall that both have the same specifications as
$\mu^{\Lambda,\tau}_{G}$. This implies that indeed
$0\leq{\mathcal{N}}(ws,uz)\leq b^{-4}$.

Lemma 12.2 follows. $\Box$

##  13\. Proof of Theorem 11.3

In what follows, for the diagonal matrix , we abbreviate $\UpD(wx,wx)$ to
$\UpD(wx)$.

For $wx,uz\in{\mathcal{S}}_{\Lambda}$ such that $w\neq u$, the entry
${\mathcal{H}}^{\Lambda,\tau}_{G}(wx,uz)$ corresponds to the influence of $wx$
to $uz$ in the graph $G_{w,u}$ under the $\\{wx,uz\\}$-extension of
$\mu^{\Lambda,\tau}_{G}$. Let the Gibbs distribution on
$\upnu^{M,\sigma}_{G_{u,w}}$ be the $\\{wx,uz\\}$-extension of
$\mu^{\Lambda,\tau}_{G}(\cdot)$.

Since ${\mathcal{H}}^{\Lambda,\tau}_{G}(wx,uz)$ is an influence, we consider
the construction Section 6. Specifically, let $T=T_{{\rm SAW}}(G_{u,w},wx)$,
while let the weights $\\{\upbeta_{{uz}}(e_{i})\\}$ be obtained as we describe
in (6.3) with respect to $\upnu^{M,\sigma}_{G_{u,w}}$. Note that $(M,\sigma)$
and hence $\\{\upbeta_{{uz}}(e_{i})\\}$ depend on the $wx,uz$.

For every path $P=e_{1},e_{2},\ldots,e_{\ell}$, that starts from the root of
the tree $T$, let

$\displaystyle{\tt
weight}_{uz}(P)=\prod\nolimits_{i\in[\ell]}\upbeta_{uz}(e_{i})\enspace.$

Let ${\mathcal{Q}}^{(\ell,uz)}_{\rm root}$ be defined by

$\displaystyle{\mathcal{Q}}^{(\ell,uz)}_{\rm root}$
$\displaystyle=\frac{\UpD(uz)}{\UpD(wx)}\cdot\sum\nolimits_{P\in{\mathcal{P}}_{uz}}\left|{\tt
weight}_{uz}(P)\right|\enspace,$ (13.1)

where ${\mathcal{P}}_{uz}$ is the set of all paths from the root of $T$ to the
vertices in ${\tt A}(uz,\ell)$, i.e., the set of vertices at level $\ell$ of
the tree $T$ which are copies of the split-vertex $uz$. Also, let

$\displaystyle{\mathcal{Q}}^{(\ell)}_{\rm root}$
$\displaystyle=\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}{\mathcal{Q}}^{(\ell,uz)}_{\rm
root}\enspace.$

It is clear that

$\displaystyle\sum\nolimits_{uz\in
S_{u}}\left|\left({}^{-1}\cdot{\mathcal{H}}^{\Lambda,\tau}_{G}\cdot\UpD\right)(wx,vz)\right|$
$\displaystyle\leq\sum\nolimits_{\ell\geq 1}{\mathcal{Q}}^{(\ell)}_{\rm
root}\enspace.$ (13.2)

The theorem follows by showing for any $wx\in{\mathcal{S}}_{\Lambda}$ and any
$\ell>1$, we have that

$\displaystyle{\mathcal{Q}}^{(\ell)}_{\rm root}$
$\displaystyle\leq\frac{c}{\UpD(wx)}\cdot\left(\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}|{\tt
A}(uz,\ell)|\cdot\delta^{\ell-1}\cdot{}^{s}(uz)\right)^{1/s}\enspace,$ (13.3)

while for $\ell=1$, we have that

$\displaystyle{\mathcal{Q}}^{(\ell)}_{\rm root}\leq
c\cdot\frac{\UpD(xw)}{\UpD(wx)}\enspace.$ (13.4)

In order to prove (13.3) we use the following result, which is useful to
involve the potential function ${\Psi}$ in our derivations.

######  Claim 13.1.

For any $uz\in S_{u}$, for any path $P=e_{1},\ldots,e_{\ell}$ of length
$\ell>1$, that starts from the root of the tree $T_{{\rm SAW}}(G_{u,w},wx)$,
we have that

$\displaystyle{\tt weight}_{uz}(P)$
$\displaystyle=\upgamma_{uz}(e_{\ell})\cdot\frac{\upbeta_{uz}(e_{1})}{\upgamma_{uz}(e_{1})}\cdot\prod^{\ell}_{i=2}\frac{\upgamma_{uz}(e_{i-1})}{\upgamma_{uz}(e_{i})}\cdot\upbeta_{uz}(e_{i})\enspace,$

where $\upgamma_{uz}(e)=\chi(\upbeta_{uz}(e))$ and $\chi={\Psi}^{\prime}$.

The proof of Claim 13.1 is identical to that of Claim 10.2, i.e., we use the
same telescopic trick. For this reason, we omit it.

Consider the vertex $v$ in the tree $T$, at level $0\leq h<\ell$. As before,
let $T_{v}$ be the subtree that contains $v$ and all its descendants. Let the
quantity ${\mathcal{R}}^{uz}_{v}$ be defined by

$\displaystyle{\mathcal{R}}^{uz}_{v}=\frac{\UpD(uz)}{\UpD(wx)}\cdot\sum_{P\in{\mathcal{P}}^{uz}_{u}}\prod^{\ell-h}_{i=1}\frac{\upgamma_{uz}(e_{i-1})}{\upgamma_{uz}(e_{i})}\cdot\left|\upbeta_{uz}(e_{i})\right|\enspace,$

where ${\mathcal{P}}^{vz}_{u}$ is the set of paths from the root of $T_{v}$ to
the vertices in $T_{v}\cap{\tt A}(uz,\ell)$, while we take $P$ such that
$P=e_{1},\ldots,e_{\ell-h}$ and $e_{0}$ is the edge that connects $v$ with its
parent.

For a vertex $v\in T$ at level $h=\ell$ we set

$\displaystyle{\mathcal{R}}^{uz}_{v}=\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}\frac{\UpD(uz)}{\UpD(wx)}\cdot\mathds{1}\\{v\in{\tt
A}(uz,\ell)\\}\enspace.$ (13.5)

For $h=0$, i.e., having vertex $v$ to be the roof of $T$, we have
${\mathcal{R}}^{uz}_{v}={\mathcal{Q}}^{(\ell,uz)}_{wx}$. This follows from
(13.1).

A simple induction implies that $R^{uz}_{v}$, for vertex $v$ being at level
$0<h<\ell$ of the tree $T$, satisfied the following recursive relation: let
$v_{1},\ldots,v_{d}$ be the children of $v$ in $T_{v}$, while let
$a_{1},\ldots,a_{d}$ be the edges that connect $v$ with its children, i.e.,
the edge $a_{j}$ connects $v$ to $v_{j}$, etc. Then, we have that

$\displaystyle{\mathcal{R}}^{uz}_{v}$
$\displaystyle=\upgamma_{uz}(a_{0})\cdot\sum\nolimits_{i\in[d]}\frac{\left|\upbeta_{uz}(a_{i})\right|}{\upgamma_{uz}(a_{0})}\cdot{\mathcal{R}}^{uz}_{v_{i}}\enspace,$
(13.6)

where $a_{0}$ is the edge that connects $v$ to its parent in the tree $T$.

We further consider the quantity ${\mathcal{R}}_{v}$ defined by

$\displaystyle{\mathcal{R}}_{v}$
$\displaystyle=\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}{\mathcal{R}}^{uz}_{v}\enspace.$

Then, (13.6) implies that for a vertex $v$ at level $0<h<\ell$, we have that

$\displaystyle{\mathcal{R}}_{v}$
$\displaystyle=\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}{\mathcal{R}}^{uz}_{v}\
=\
\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}\upgamma_{uz}(a_{0})\cdot\sum\nolimits_{i}\frac{\left|\upbeta_{uz}(a_{i})\right|}{\upgamma_{uz}(a_{0})}\cdot{\mathcal{R}}^{uz}_{v_{i}}$
$\displaystyle=\sum\nolimits_{i}\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}\upgamma_{uz}(a_{0})\cdot\frac{\left|\upbeta_{uz}(a_{i})\right|)}{\upgamma_{uz}(a_{0})}\cdot{\mathcal{R}}^{uz}_{v_{i}}$
$\displaystyle\leq\sum\nolimits_{i}\max\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}\left\\{\upgamma_{uz}(a_{0})\cdot\frac{\left|\upbeta_{uz}(a_{i})\right|}{\upgamma_{uz}(a_{0})}\right\\}\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}{\mathcal{R}}^{uz}_{v_{i}}$
$\displaystyle\leq\sum\nolimits_{i}\max_{uz\in{\mathcal{S}}_{\Lambda}}\left\\{\upgamma_{uz}(a_{0})\cdot\frac{\left|\upbeta_{uz}(a_{i})\right|}{\upgamma_{uz}(a_{0})}\right\\}{\mathcal{R}}_{v_{i}}\enspace.$

Combining the above inequality with our assumption about the
$(s,\delta,c)$-potential, i.e., the contraction property, we get that

$\displaystyle\left({{\mathcal{R}}}_{v}\right)^{s}\leq\delta\cdot\sum\nolimits_{v_{i}}\left({\mathcal{R}}_{v_{i}}\right)^{s}\enspace.$

Then, a simple induction proves that

$\displaystyle\left({{\mathcal{R}}}_{v}\right)^{s}$
$\displaystyle\leq\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}\left(\frac{\UpD(uz)}{\UpD(wx)}\right)^{s}\cdot\delta^{\ell-h}\cdot|{\tt
A}(uz,\ell)\cap T_{v}|\enspace,$

where recall that $0<h<\ell$ is the level of vertex $v$ in the tree $T$.

Focusing on vertex $\pi$ the single child of the root of $T$, the above
implies that

$\displaystyle\left({{\mathcal{R}}}_{\pi}\right)^{s}$
$\displaystyle\leq\sum\nolimits_{uz\in{\mathcal{S}}_{\Lambda}}\left(\frac{\UpD(uz)}{\UpD(wx)}\right)^{s}\cdot\delta^{\ell-1}\cdot|{\tt
A}(uz,\ell)|\enspace.$ (13.7)

For the above inequality, we observe that, since the root of $T$ has only
vertex $\pi$ as a child and $\ell>1$, then we have that ${\tt A}(uz,\ell)\cap
T_{c}={\tt A}(uz,\ell)$. Furthermore, it is not hard to see that

$\displaystyle{{\mathcal{Q}}}^{(\ell)}_{\rm root}$
$\displaystyle\leq\max_{uz}\max_{e_{a},e_{b}\in
T}\left\\{\upgamma_{uz}(e_{a})\cdot\frac{|\upbeta_{uz}(e_{b})|}{\upgamma_{uz}(e_{b})}\right\\}\cdot{{\mathcal{R}}}_{\pi}\enspace.$

Our assumption about the $(s,\delta,c)$-potential, i.e., the boundedness
property, implies that

$\displaystyle{{\mathcal{Q}}}^{(\ell)}_{\rm root}$ $\displaystyle\leq
c\cdot{{\mathcal{R}}}_{\pi}\enspace.$ (13.8)

Then (13.3) follows by plugging (13.7) into (13.8).

As far as ${{\mathcal{Q}}}^{(1)}_{\rm root}$ is concerned, note the following:
for any $e\in T$ and any $uz\in{\mathcal{S}}_{\Lambda}$ we have that

$\displaystyle|\upbeta_{uz}(e)|=\frac{\upgamma_{uz}(e)}{\upgamma_{uz}(e)}\cdot|\upbeta_{uz}(e)|\leq\max_{\bar{e},\hat{e}\in
T}\left\\{\upgamma_{uz}(\bar{e})\cdot\frac{|\upbeta_{uz}(\hat{e})|}{\upgamma_{uz}(\hat{e})}\right\\}\leq
c\enspace,$ (13.9)

where the last inequality follows from our assumption about
$(s,\delta,c)$-potential, i.e., “Boundedness”. From the definition of
${{\mathcal{Q}}}^{(1)}_{\rm root}$, we have that

$\displaystyle{{\mathcal{Q}}}^{(1)}_{\rm root}$
$\displaystyle=\frac{1}{\UpD(wx)}\UpD(xw)\cdot\left|\upbeta_{xw}(e)\right|\leq
c\cdot\frac{\UpD(xw)}{\UpD(wx)}\enspace.$ (13.10)

In the last inequality we use (13.9). The above proves (13.4).

Having proved that both (13.3) and (13.4) are true, concludes the proof of
Theorem 11.3. $\Box$

##  14\. Proof of results in Section 2 \- Ising Model

For $d>0$, consider the functions $H_{d}$ and $h(\cdot)$ defined in (5.3) and
(5.4), respectively. Recall that the zero external field Ising model $\mu$
corresponds to setting the parameters $\beta,\gamma$ and $\lambda$ such that
$\beta=\gamma$ and $\lambda=1$. We have that

$\displaystyle H_{d}:[-\infty,+\infty]^{d}\to[-\infty,+\infty]$ s.t.
$\displaystyle(x_{1},\ldots,x_{d})\mapsto\sum\nolimits_{i\in[d]}\log\left(\frac{\beta\exp(x_{i})+1}{\exp(x_{i})+\beta}\right)\enspace.$
(14.1)

Since $\frac{\partial}{\partial x_{i}}H_{d}(x_{1},\ldots,x_{d})=h(x_{i})$, we
have that

$\displaystyle h(x)$
$\displaystyle=-\frac{(1-\beta^{2})\exp(x)}{(\beta\exp(x)+1)(\exp(x)+\beta)}\enspace.$
(14.2)

The following is a folklore result.

######  Lemma 14.1.

For any $d>0$, $\zeta\in(0,1)$, $R>1$ and $\beta\in{\mathbb{U}_{\rm
Ising}}(R,\zeta)$ we have the following: the functions $H_{d}$ specified in
(14.1) satisfies that

$\displaystyle||\nabla H_{d}({y}_{1},{y}_{2},\ldots,{y}_{d})||_{\infty}$
$\displaystyle\leq{(1-\zeta)}/{R}\enspace.$ (14.3)

For the sake of our paper being self-contained, we present a proof of Lemma
14.1 in Section A.3.

###  14.1. Proof of Theorem 2.1

If ${\rho}={\rho}({}_{G})$ is bounded, then the same holds for the maximum
degree ${\Delta}$ of $G$. This follows from the standard relation that
${\Delta}\leq{\rho}^{2}\leq{\Delta}^{2}$.

Lemma 14.1 implies the following: for any $\beta\in{\mathbb{U}_{\rm
Ising}}({\rho},\varepsilon)$, the set of functions
$\\{H_{d}\\}_{d\in[{\Delta}]}$ specified in (14.1) exhibits
$({1-\varepsilon})/{{\rho}}$-contraction. That is,

$\displaystyle||\nabla H_{d}({y}_{1},{y}_{2},\ldots,{y}_{d})||_{\infty}$
$\displaystyle\leq({1-\varepsilon})/{{\rho}}$ $\displaystyle\forall
d\in[{\Delta}]\enspace.$

The above, combined with Theorem 5.2 imply that for $\Lambda\subseteq V$ and
$\tau\in\\{\pm 1\\}^{\Lambda}$, the pairwise influence matrix
${{\mathcal{I}}}^{\Lambda,\tau}_{G}$, induced by $\mu$, satisfies that

$\displaystyle{\rho}({{\mathcal{I}}}^{\Lambda,\tau}_{G})\leq\varepsilon^{-1}\enspace.$
(14.4)

Furthermore, for $\beta\in{\mathbb{U}_{\rm Ising}}({\rho},\varepsilon)$ where
${\rho}$ is bounded, we have that $\mu$ is $b$-marginally bounded for $b>0$
bounded away from zero.

Then, the theorem follows as a corollary from Theorem 4.5 $\Box$

###  14.2. Proof of Theorem 2.2

The proof of Theorem 2.2 is not that different from that of Theorem 2.1. Note
that we assume that both ${\Delta}$ and $\uptheta$ are bounded, while
${}_{G}\in{\mathbb{H}}_{n,{\hat{c}}}$, where ${\hat{c}}\in\mathbb{R}_{>0}$ is
also bounded.

Lemma 14.1 implies the following: for any $\beta\in{\mathbb{U}_{\rm
Ising}}(\uptheta,\varepsilon)$, the set of functions
$\\{H_{d}\\}_{d\in[{\Delta}]}$ specified in (14.1) exhibits
$({1-\varepsilon})/{\uptheta}$-contraction, i.e.,

$\displaystyle||\nabla H_{d}({y}_{1},{y}_{2},\ldots,{y}_{d})||_{\infty}$
$\displaystyle\leq({1-\varepsilon})/{\uptheta}$ $\displaystyle\forall
d\in[{\Delta}]\enspace.$

The above, combined with Theorem 5.3 imply that for $\Lambda\subseteq V$ and
$\tau\in\\{\pm 1\\}^{\Lambda}$, the pairwise influence matrix
${{\mathcal{I}}}^{\Lambda,\tau}_{G}$, induced by $\mu$, satisfies that

$\displaystyle{\rho}({{\mathcal{I}}}^{\Lambda,\tau}_{G})\leq
1+{\hat{c}}\cdot{\Delta}/\varepsilon\enspace.$

Clearly, our assumptions imply that
${\rho}({{\mathcal{I}}}^{\Lambda,\tau}_{G})\in O(1)$.

Furthermore, for $\beta\in{\mathbb{U}_{\rm Ising}}(\uptheta,\varepsilon)$,
where both $\uptheta$ and ${\Delta}$ are bounded numbers, we have that $\mu$
is trivially $b$-marginally bounded for $b>0$ bounded away from zero.

Then, the theorem follows as a corollary from Theorem 4.5 $\Box$

##  15\. Proof of results in Section 2 \- Hard-core Model

We start by introducing the potential function ${\Psi}$. We define ${\Psi}$ in
terms of $\chi={\Psi}^{\prime}$. We have that

$\displaystyle\chi$ $\displaystyle:\mathbb{R}_{>0}\to\mathbb{R}$ such that
$\displaystyle y$
$\displaystyle\textstyle\mapsto\sqrt{\frac{e^{y}}{1+e^{y}}}\enspace,$ (15.1)

while ${\Psi}(0)=0$.

The potential function ${\Psi}$ was proposed -in a more general form- in [11].
It is standard to show that ${\Psi}$ is well-defined, e.g., see [11]. Later in
our analysis, we need to use certain results from [36], which (essentially)
use another, but closely related, potential function from [31]. We postpone
this discussion until later.

For any given $\lambda>0$, we define, implicitly, the function
${\Delta_{c}}(\lambda)$ to be the positive number $z>1$ such that
$\frac{z^{z}}{(z-1)^{(z+1)}}=\lambda$.

From its definition it is not hard to see that ${\Delta_{c}}(\cdot)$ is the
inverse map of ${\lambda_{c}}(\cdot)$, i.e., we have that
${\Delta_{c}}(x)={\lambda_{c}}^{-1}(x)$. In that respect, ${\Delta_{c}}(x)$ is
well-defined as ${\lambda_{c}}(x)$ is monotonically decreasing in $x$.

######  Theorem 15.1.

For $\lambda>0$, let ${\Delta_{c}}={\Delta_{c}}(\lambda)$. We have that
${\Psi}$ defined in (15.1) is a $(s_{0},\delta_{0},c_{0})$-potential function
(as in Definition 5.4) such that

$\displaystyle s_{0}^{-1}$ $\displaystyle=\textstyle
1-\frac{{\Delta_{c}}-1}{2}\log\left(1+\frac{1}{{\Delta_{c}}-1}\right),$
$\displaystyle\delta_{0}$ $\displaystyle\textstyle\leq\frac{1}{{\Delta_{c}}}$
and $\displaystyle c_{0}\leq\textstyle\frac{\lambda}{1+\lambda}\enspace.$
(15.2)

The proof of Theorem 15.1 appears in Section 16.

We also have the following claim.

######  Claim 15.2.

For $\varepsilon\in(0,1)$, $L\geq 2$ and
$0<\lambda<(1-\varepsilon){\lambda_{c}}(L)$ the following is true: There is
$0<z<1$ , which only depend on $\varepsilon$, such that for
${\Delta_{c}}={\Delta_{c}}(\lambda)$, we have

$\displaystyle\textstyle\frac{1-z}{L}$
$\displaystyle\geq\frac{1}{{\Delta_{c}}}$ and
$\displaystyle\frac{\lambda}{1+\lambda}$
$\displaystyle<\frac{e^{3}}{L}\enspace.$ (15.3)

Claim 15.2 follows from elementary calculations. For the proof of Claim 15.2
see Section A.4.

###  15.1. Proof of Theorem 2.3

Combining Theorem 15.1 and Theorem 5.5 we get the following corollary.

######  Corollary 15.3.

Let $\varepsilon\in(0,1)$, ${\Delta}>1$ and ${\rho}>1$. Consider the graph
$G=(V,E)$ of maximum degree ${\Delta}$, while G has spectral radius ${\rho}$.
Also, let $\mu$ be the Hard-core model on $G$, with fugacity
$0<\lambda\leq(1-\varepsilon){\lambda_{c}}({\rho})$.

There is $0<z<1$, that depends only on $\varepsilon$, such that for any
$\Lambda\subseteq V$ and $\tau\in\\{\pm 1\\}^{\Lambda}$, the pairwise
influence matrix ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$, induced by $\mu$,
satisfies that

$\displaystyle{\rho}\left({{\mathcal{I}}}^{\Lambda,\tau}_{G}\right)$
$\displaystyle\leq
1+e^{3}\left({{\Delta}}/{{\rho}}\right)^{1/2}z^{-1}\enspace.$

###### Proof of Theorem 2.3.

As argued in the proof of Theorem 2.1, if the spectral radius ${\rho}$ is
bounded, then the same holds for the maximum degree ${\Delta}$ as we always
have that ${\Delta}\leq({\rho})^{2}\leq{\Delta}^{2}$.

Since both ${\rho}$ and ${\Delta}$ are bounded and $\varepsilon\in(0,1)$ is
fixed, for fugacity $0\leq\lambda\leq(1-\varepsilon){\lambda_{c}}({\rho})$,
Corollary 15.3 implies that
${\rho}\left({{\mathcal{I}}}^{\Lambda,\tau}_{G}\right)=O(1)$ for any
$\Lambda\subseteq V$ and $\tau\in\\{\pm 1\\}^{\Lambda}$.

Furthermore, for fugacity
$0\leq\lambda\leq(1-\varepsilon){\lambda_{c}}({\rho})$, where ${\rho}$ is
bounded, w e have that the Hard-core model $\mu$ on $G$ is trivially
$b$-marginally bounded for $b>0$ bounded away from zero.

Then, the theorem follows as a corollary from Theorem 4.5 ∎

###  15.2. Results for the Hashimoto Matrix G

Combining Theorem 15.1 and Theorem 5.6 we get the following corollary.

######  Corollary 15.4.

Let $\varepsilon\in(0,1)$, ${\hat{c}}>0$, ${\Delta}\geq 2$ and $\uptheta>1$.
Consider the graph $G=(V,E)$ of maximum degree ${\Delta}$, while
${}_{G}\in{\mathbb{H}}_{n,{\hat{c}}}$ has spectral radius $\uptheta$. Also,
let $\mu$ be the Hard-core model on $G$, with fugacity
$0<\lambda\leq(1-\varepsilon){\lambda_{c}}(\uptheta)$.

There is $0<z<1$, that depends only on $\varepsilon$, such that for any
$\Lambda\subseteq V$ and $\tau\in\\{\pm 1\\}^{\Lambda}$, the pairwise
influence matrix ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$, induced by $\mu$,
satisfies that

$\displaystyle{\rho}\left({{\mathcal{I}}}^{\Lambda,\tau}_{G}\right)$
$\displaystyle\leq 1+e^{-15}\cdot{\hat{c}}\cdot\uptheta^{5}\cdot{\Delta}\cdot
z^{-1}\enspace.$

###### Proof of Theorem 2.4.

Since all the quantities $\uptheta$, ${\hat{c}}$ and ${\Delta}$ are bounded
and $\varepsilon\in(0,1)$ is fixed, for fugacity
$0\leq\lambda\leq(1-\varepsilon){\lambda_{c}}({\rho})$, we have that the Hard-
core model $\mu$ on $G$ is trivially $b$-marginally bounded for $b>0$ bounded
away from zero. Furthermore, Corollary 15.4 implies that
${\rho}\left({{\mathcal{I}}}^{\Lambda,\tau}_{G}\right)=O(1)$ for any
$\Lambda\subseteq V$ and $\tau\in\\{\pm 1\\}^{\Lambda}$.

Then, the theorem follows as a corollary from Theorem 4.5 ∎

##  16\. Proof of Theorem 15.1

Recall that the ratio of Gibbs marginals ${R}^{\Lambda,\tau}_{x}$, defined in
Section 5, is possible to be equal to zero, or $\infty$. Typically, this
happens if the vertex $x$ with respect to which we consider the ratio is a
part of the boundary set $\Lambda$, or has a neighbour in $\Lambda$. When we
are dealing with the Hard-core model, there is a standard way to avoid these
infinities and zeros in our calculations and make the derivation much simpler.

Suppose that we have the Hard-core model with fugacity $\lambda>0$ on a tree
$T$, while at the set of vertices $\Lambda$ we have a boundary condition
$\tau$. Then, it is elementary to verify that this distribution is identical
to the Hard-core model with the same fugacity on the tree (or forest)
$T^{\prime}$ which is obtained from $T$ by working as follows: we remove from
$T$ every vertex $w$ which either belongs to $\Lambda$, or has a neighbour
$u\in\Lambda$ such that $\tau(u)=$“occupied”.

From now one, for the instances of the problem we consider, assume that we
have applied the above steps and removed any boundary conditions.

Perhaps it is useful to write down the functions that arise from the
recursions in Section 5, for the Hard-core model with fugacity $\lambda$.
Recall that, in this case, we have $\beta=0$ and $\gamma=1$. In the following
definitions, we take into consideration that boundary conditions have been
removed as described above.

For integer $d\geq 1$, we have that

$\displaystyle F_{d}:\mathbb{R}^{d}_{>0}\to(0,\lambda)$ such that
$\displaystyle(x_{1},\ldots,x_{d})\mapsto\lambda\prod\nolimits_{i\in[d]}\frac{1}{{x}_{i}+1}\enspace.$
(16.1)

We also define $F_{d,{\rm sym}}:\mathbb{R}^{d}_{>0}\to(0,\lambda)$ the
symmetric version of the above function, that is

$\displaystyle x$ $\displaystyle\mapsto F_{d}(x,x,\ldots,x)\enspace.$ (16.2)

Recall, also, that $H_{d}=\log\circ F_{d}\circ\exp$. For the Hard-core model
with fugacity $\lambda$, we have that

$\displaystyle H_{d}:\mathbb{R}^{d}\to\mathbb{R}$ s.t.
$\displaystyle(x_{1},\ldots,x_{d})\mapsto\log\lambda+\sum\nolimits_{i\in[d]}\log\left(\frac{1}{\exp(x_{i})+1}\right)\enspace.$
(16.3)

For $h(\cdot)$ such that $\frac{\partial}{\partial
x_{i}}H_{d}(x_{1},\ldots,x_{d})=h(x_{i})$, we have

$\displaystyle h:\mathbb{R}\to\mathbb{R}$ such that $\displaystyle\textstyle
x\mapsto-\frac{e^{x_{i}}}{e^{x_{i}}+1}\enspace.$ (16.4)

Finally, the set of log-ratios $J$, defined in (5.9), satisfies that

$\displaystyle J=(-\infty,\log(\lambda))\enspace.$ (16.5)

Note also, that the image of ${\Psi}$, i.e., the set $S_{{\Psi}}$, satisfies
that $S_{{\Psi}}=(-\infty,\infty)$.

With all the above, we proceed to prove Theorem 15.1. We need to show that
${\Psi}$ satisfies the contraction and the boundedness conditions, for
appropriate parameters.

We start with the contraction. For any integer $d>0$, we let
${\mathcal{E}}_{d}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ be such
that for ${\bf m}=({\bf m}_{1},\ldots,{\bf m}_{d})\in\mathbb{R}^{d}_{\geq 0}$,
and ${\bf y}=({\bf y}_{1},\ldots,{\bf y}_{d})\in\mathbb{R}^{d}$ we have that

$\displaystyle{\mathcal{E}}_{d}({\bf m},{\bf
y})={\textstyle\chi\left(H_{d}({\bf
y})\right)}\sum^{d}_{j=1}\frac{\textstyle\left|h\left({\bf
y}_{j}\right)\right|}{\textstyle\chi\left({\bf y}_{j}\right)}\times{\bf
m}_{j}\enspace.$

######  Proposition 16.1 (contraction).

For $\lambda>0$, let ${\Delta_{c}}={\Delta_{c}}(\lambda)$. Let $q>0$ be such
that

$\displaystyle q^{-1}$ $\displaystyle=\textstyle
1-\frac{{\Delta_{c}}-1}{2}\log\left(1+\frac{1}{{\Delta_{c}}-1}\right)\enspace.$
(16.6)

For $d>0$, for ${\bf m}\in\mathbb{R}^{d}_{\geq 0}$ we have that

$\displaystyle\sup_{{\bf y}\in(Q_{{\Psi}})^{d}}\\{{\mathcal{E}}_{d}({\bf
m},{\bf y})\\}\leq{\Delta_{c}}^{-\frac{1}{q}}\cdot\left|\left|{\bf
m}\right|\right|_{q}\enspace,$ (16.7)

where $Q_{{\Psi}}\subseteq\mathbb{R}$ contains every $y\in\mathbb{R}$ such
that there is $\tilde{y}\in S_{{\Psi}}$ for which we have
${y}={\Psi}^{-1}(\tilde{y})$.

The proof of Proposition 16.1 appears in Section 16.1.

Note that Proposition 16.1 implies that ${\Psi}$ satisfies the contraction
condition with the parameter we need in order to prove our theorem. We now
focus on establishing the boundedness property of ${\Psi}$.

######  Lemma 16.2 (boundedness).

For $\lambda>0$, we have that $\textstyle\max_{y_{1},y_{2}\in
J}\left\\{\chi(y_{2})\cdot\frac{|h(y_{1})|}{\chi(y_{1})}\right\\}\leq\frac{\lambda}{1+\lambda}$.

###### Proof.

Using the definitions of the functions $\chi$ and $h$ from (16.9) and (16.4),
respectively, we have that

$\displaystyle\max_{y_{1},y_{2}\in
J}\left\\{\chi(y_{2})\cdot\frac{|h(y_{1})|}{\chi(y_{1})}\right\\}$
$\displaystyle=\max_{y_{1},y_{2}\in
J}\left\\{\sqrt{h(y_{1})h(y_{2})}\right\\}\ =\ \max_{y_{1},y_{2}\in
J}\left\\{\sqrt{\frac{e^{y_{1}}}{1+e^{y_{1}}}\frac{e^{y_{2}}}{1+e^{y_{2}}}}\right\\}\
=\ {\frac{\lambda}{1+\lambda}}\enspace.$

The last inequality follows from the observation that the function
$g(x)=\frac{e^{x}}{1+e^{x}}$ is increasing in $x$, while, from (16.5), we have
that $e^{y_{1}},e^{y_{2}}\leq\lambda$. The claim follows. ∎

In light of Proposition 16.1 and Lemma 16.2, Theorem 15.1 follows. $\Box$

###  16.1. Proof of Proposition 16.1

The proposition follows by using results from [36]. However, in order to apply
these results, we need to bring ${\mathcal{E}}_{d}({\bf m},{\bf y})$ into an
appropriate form.

For any $d>0$, we let ${\mathcal{J}}_{d}:\mathbb{R}^{d}_{\geq
0}\times\mathbb{R}^{d}_{\geq 0}\to\mathbb{R}$ be such that for ${\bf m}=({\bf
m}_{1},\ldots,{\bf m}_{d})\in\mathbb{R}^{d}_{\geq 0}$ and ${\bf z}=({\bf
z}_{1},\ldots,{\bf z}_{d})\in\mathbb{R}^{d}_{\geq 0}$ we have

$\displaystyle{\mathcal{J}}_{d}({\bf m},{\bf z})$
$\displaystyle=\textstyle\chi\left(\log F_{d}({\bf
z})\right)\sum^{d}_{j=1}\frac{\textstyle\left|h\left(\log{\bf
z}_{j}\right)\right|}{\textstyle\chi\left(\log{\bf z}_{j}\right)}\times{\bf
m}_{j}\enspace.$

Using the definitions in (16.1) and (16.3), it is elementary to verify that
for any $d>0$, for any ${\bf m}\in\mathbb{R}^{d}_{\geq 0}$, ${\bf
z}\in\mathbb{R}^{d}_{>0}$ and ${\bf y}\in\mathbb{R}^{d}$ such that ${\bf
z}_{j}=e^{{\bf y}_{j}}$, we have that

$\displaystyle{\mathcal{J}}_{d}({\bf m},{\bf z})={\mathcal{E}}_{d}({\bf
m},{\bf y})\enspace.$

In light of the above, the proposition follows by showing that

$\displaystyle{\textstyle\sup_{{\bf
z}\in\mathbb{R}^{d}_{>0}}}\\{{\mathcal{J}}_{d}({\bf m},{\bf
z})\\}\leq{\Delta_{c}}^{-{1}/{s}}\cdot\left|\left|{\bf
m}\right|\right|_{s}\enspace.$ (16.8)

In order to prove (16.8), we let

$\displaystyle{\psi}$ $\displaystyle:\mathbb{R}_{>0}\to\mathbb{R}$ such that
$\displaystyle y$
$\displaystyle\textstyle\mapsto\frac{1}{2}\sqrt{\frac{1}{y(1+y)}}\enspace.$
(16.9)

######  Claim 16.3.

For any ${\bf m}=({\bf m}_{1},\ldots,{\bf m}_{d})\in\mathbb{R}^{d}_{\geq 0}$
and ${\bf z}=({\bf z}_{1},\ldots,{\bf z}_{d})\in\mathbb{R}^{d}_{>0}$ we have
that

$\displaystyle{\mathcal{J}}_{d}({\bf m},{\bf z})$
$\displaystyle={\psi}(F_{d}({\bf z}))\times\sum\nolimits_{i\in[d]}\frac{{\bf
m}_{i}}{{\psi}({\bf z}_{i})}\left.\left|\frac{\partial}{\partial{\bf
t}_{i}}F_{d}({\bf t})\right|_{{\bf t}={\bf z}}\right|\enspace,$ (16.10)

where $F_{d}$ and ${\psi}$ are defined in (16.1) and (16.9), respectively.

###### Proof.

The claim follows by using simple rearrangements. We have that

$\displaystyle{\mathcal{J}}_{d}({\bf m},{\bf z})$
$\displaystyle=\textstyle\chi\left(\log F_{d}({\bf
z})\right)\sum^{d}_{j=1}\frac{\textstyle\left|h\left(\log{\bf
z}_{j}\right)\right|}{\textstyle\chi\left(\log{\bf z}_{j}\right)}\times{\bf
m}_{j}$ $\displaystyle=\textstyle\sqrt{\frac{F_{d}({\bf z})}{1+F_{d}(\bf
z)}}\sum^{d}_{j=1}\sqrt{\frac{{\bf z}_{j}}{1+{\bf z}_{j}}}\times{\bf m}_{j}$
(16.11) $\displaystyle=\textstyle\sqrt{\frac{1}{F_{d}({\bf z})(1+F_{d}(\bf
z))}}\sum^{d}_{j=1}\sqrt{{\bf z}_{j}(1+{\bf z}_{j})}\times\frac{F_{d}(\bf
z)}{1+{\bf z}_{j}}\times{\bf m}_{j}\enspace.$

In (16.11), we substitute $\chi$ and $h$ according to (15.1) and (16.4),
respectively. Using the definition of ${\psi}$ from (16.9), we get that

$\displaystyle{\mathcal{J}}_{d}({\bf m},{\bf z})$
$\displaystyle={\psi}(F_{d}({\bf
z}))\sum\nolimits_{j\in[d]}\frac{1}{{\psi}({\bf z}_{j})}\times\frac{F_{d}(\bf
z)}{1+{\bf z}_{i}}\times{\bf m}_{j}\enspace.$

The above implies (16.10), note that $\left|\frac{\partial}{\partial{\bf
t}_{i}}F_{d}({\bf t})\right|=\frac{F_{d}({\bf t})}{1+{\bf t}_{i}}$, for any
$i\in[d]$. The claim follows. ∎

In light of Claim 16.3, (16.8) follows by showing that for any ${\bf m}=({\bf
m}_{1},\ldots,{\bf m}_{d})\in\mathbb{R}^{d}_{\geq 0}$ and ${\bf z}=({\bf
z}_{1},\ldots,{\bf z}_{d})\in\mathbb{R}^{d}_{>0}$ we have that

$\displaystyle{\psi}(F_{d}({\bf z}))\times\sum\nolimits_{i\in[d]}\frac{{\bf
m}_{i}}{{\psi}({\bf z}_{i})}\left.\left|\frac{\partial}{\partial{\bf
t}_{i}}F_{d}({\bf t})\right|_{{\bf t}={\bf z}}\right|$
$\displaystyle\leq{\Delta_{c}}^{-\frac{1}{s}}\cdot\left|\left|{\bf
m}\right|\right|_{s}\enspace.$ (16.12)

The above follows by using standard results form [36]. For any $s\geq 1,d>0$
and $x\geq 0$, we let the function

$\displaystyle{\Xi}(s,d,x)=\frac{1}{d}\left(\frac{{\psi}(F_{d,{\rm
sym}}(x))}{{\psi}(x)}F^{\prime}_{d,{\rm sym}}(x)\right)^{s}\enspace,$

where the functions $F_{d,{\rm sym}}$, ${\psi}$ are defined in (16.2) and
(16.9), respectively, while $F^{\prime}_{d,{\rm sym}}(x)=\frac{d}{dx}F_{d,{\rm
sym}}(x)$.

######  Lemma 16.4 ([36]).

For any $\lambda>0$, for integer $d\geq 1$, for $s\geq 1$, for ${\bf
x}\in\mathbb{R}^{d}_{>0}$ and ${\bf m}\in\mathbb{R}^{d}_{\geq 0}$, the
following holds: there exists $\bar{x}>0$ and integer $0\leq k\leq d$ such
that

$\displaystyle{\psi}(F_{d}({\bf x}))\times\sum\nolimits_{i\in[d]}\frac{{\bf
m}_{i}}{{\psi}({\bf x}_{i})}\left|\left.\frac{\partial}{\partial
z_{i}}F_{d}({\bf z})\right|_{{\bf z}={\bf x}}\right|$
$\displaystyle\leq\left({\Xi}(s,k,\bar{x})\right)^{1/s}\times||{\bf
m}||_{s}\enspace,$

where ${\bf x}=({\bf x}_{1},\ldots,{\bf x}_{d})$ and ${\bf m}=({\bf
m}_{1},\ldots,{\bf m}_{d})$.

In light of the above lemma, our proposition follows as a corollary from the
following result.

######  Lemma 16.5 ([36]).

For $\lambda>0$, consider ${\Delta_{c}}={\Delta_{c}}(\lambda)$ and
$F_{{\Delta_{c}},{\rm sym}}$ with fugacity $\lambda$. Let $q\geq 1$ be such
that

$\displaystyle q^{-1}$ $\displaystyle=\textstyle
1-\frac{{\Delta_{c}}-1}{2}\log\left(1+\frac{1}{{\Delta_{c}}-1}\right)\enspace.$

For any $x>0$, $d>0$, we have that

$\displaystyle{\Xi}(q,d,x)\leq{\Xi}(q,{\Delta_{c}},\tilde{x})=({\Delta_{c}})^{-1}\enspace,$

where $\tilde{x}\in[0,1]$ is the unique fix-point of $F_{{\Delta_{c}},{\rm
sym}}$, i.e., $\tilde{x}=F_{{\Delta_{c}},{\rm sym}}(\tilde{x})$.

By combining Lemmas 16.4 and 16.5 we get (16.12). This concludes the proof of
Proposition 16.1. $\Box$

## References

  * [1] E. Abbe, C. Sandon. Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery. In 56th Annual Symposium on Foundations of Computer Science  FOCS’15, pp: 670–688, 2015.
  * [2] V. L. Alev and L. C. Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1198 –1211, 2020.
  * [3] N. Anari, K. Liu, S. Oveis Gharan: Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. In Proc. of 61st IEEE Annual Symposium on Foundations of Computer Science, (FOCS), pp. 1319-1330, 2020.
  * [4] F. Bencs, K. Berrekkal, G Regts. Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees. arXiv preprint arXiv:2310.04338, 2023. 2023
  * [5] I. Bezáková, A. Galanis, L. A. Goldberg, D. l Stefankovic: Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs. In Proc. 49th International Colloquium on Automata, Languages, and Programming (ICALP’22), pp: 21:1–21:16, 2022.
  * [6] C. Bordenave, M. Lelarge and L. Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. The Annals of Probability, 46(1), pp 1-71, 2018.
  * [7] R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In Proc. 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 223 – 231, 1997.
  * [8] Y. Chen and R. Eldan. Localization schemes: A framework for proving mixing bounds for Markov chains. In Proc. 63th Annual Symposium on Foundations of Computer Science (FOCS), pp. 110– 122, 2022.
  * [9] X. Chen, W. Feng, Y. Yin, X. Zhang. Optimal mixing for two-state anti-ferromagnetic spin systems. In 62rd IEEE Annual Symposium on Foundations of Computer Science, (FOCS) pp:588–599, 2022.
  * [10] Z. Chen, K. Liu, N. Mani and A. Moitra. Strong spatial mixing for colorings on trees and its algorithmic applications. CoRR abs/2304.01954, 2023.
  * [11] Z. Chen, K. Liu, E. Vigoda. Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. In Proc. of 61st IEEE Annual Symposium on Foundations of Computer Science, (FOCS) pp 1307–1318, 2020.
  * [12] Z. Chen, K. Liu, E. Vigoda. Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion. In 53rd Annual ACM SIGACT Symposium on Theory of Computing, (STOC’21), pp 1537–1550, 2021. Online version: https://arxiv.org/abs/2011.02075.
  * [13] X. Chen, W. Feng, Y. Yin, X. Zhang. Rapid mixing of Glauber dynamics via spectral independence for all degrees. In 62nd IEEE Annual Symposium on Foundations of Computer Science, (FOCS) pp:137-148, 2021.
  * [14] A Decelle, F Krzakala, C Moore, L Zdeborová Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications In Physical review E 84(6), 066106, 2011.
  * [15] M. Dyer, L. A. Goldberg and M. Jerrum. Matrix norms and rapid mixing for spin systems. Ann. Appl. Probab. 19(1), pp 71 – 107, 2009.
  * [16] P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of Markov chains. The Annals of Applied Probability, pp. 36–61, 1991.
  * [17] Z. Dvořák, B. Mohar. Spectral radius of finite and infinite planar graphs and of graphs of bounded genus. Journal of Combinatorial Theory, Series B (JCTB) 100 pp 729 – 739, 2010.
  * [18] C. Efthymiou and W. Feng. On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n, d/n). To appear in ICALP 2023. Online version CoRR abs/2302.06172 (2023)
  * [19] C. Efthymiou, T. Hayes, D. Štefankovič and E. Vigoda. Sampling Random Colorings of Sparse Random Graphs. In the proc of 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1759 –1771, 2018.
  * [20] C. Efthymiou, T. Hayes, D. Stefankovic, E. Vigoda and Y. Yin. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. SIAM Journal on Computing (SICOMP) 48(2), pp 581–643, 2019.
  * [21] C. Efthymiou. On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs. In the proc. of 49th International Colloquium on Automata, Languages, and Programming (ICALP’22), pp 57:1–57:16, 2022.
  * [22] C. Glover and M. Kempton. Some spectral properties of the non-backtracking matrix of a graph. Linear Algebra and its Applications, 618, pp 37-57, 2021.
  * [23] C. D. Godsil. Algebraic Combinatorics. Chapman and Hall Math. Series, Chapman & Hall, New York, 1993. MR 1220704. Zbl 0784.05001.
  * [24] K. Hashimoto. Zeta functions of finite graphs and representations of $p$-adic groups. In Automorphic Forms and Geometry of Arithmetic Varieties. Adv. Stud. Pure Math. 15, pp 211–280. Academic Press, Boston, MA, 1989.
  * [25] T. P. Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. In Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp 39– 46, 2006.
  * [26] T. P. Hayes, J. C. Vera and E. Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. In Proc. of the 39th Annual ACM Symposium on Theory of Computing (STOC’07), pp 450–458, 2007.
  * [27] R. A. Horn and C. R. Johnson. Matrix Analysis, 2nd Edition. Cambridge University Press, New York, 2013.
  * [28] Y. Ihara, On discrete subgroups of the two by two projective linear group over $p$-adic fields, J. Math. Soc. Japan, 18, pp 219–235, 1966.
  * [29] F. P. Kelly. Stochastic Models of Computer Communication Systems. Journal of the Royal Statistical Society. Series B (Methodological), 47(3):379-395, 1985.
  * [30] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, P. Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences 110 (52), 20935-20940, 2013.
  * [31] L. Li, P. Lu, and Y. Yin. Correlation Decay Up to Uniqueness in Spin Systems. In the Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 67–84, 2013.
  * [32] L. Massoulié. Community detection thresholds and the weak Ramanujan property. In Symposium on Theory of Computing, STOC’14, pp. 694–703, 2014.
  * [33] C. D. Meyer. Matrix analysis and applied linear algebra. Society for Industrial and Applied Mathematics (SIAM), 2000.
  * [34] A. W. Marcus, D. A. Spielman and N. Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Annals of Mathematics 182, pp 307–325, 2015.
  * [35] A. Sinclair and M. Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82, pp. 93 – 133, 1989.
  * [36] A. Sinclair, P. Srivastava, D. Stefankovic and Y. Yin. Spatial mixing and the connective constant: Optimal bounds. In Probability Theory and Related Fields 168, pp. 153–197, 2017.
  * [37] A. Sly. Computational Transition at the Uniqueness Threshold. In Proc. of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287– 296, 2010.
  * [38] A. Sly and N. Sun. The Computational Hardness of Counting in Two-Spin Models on $d$-Regular Graphs. The Annals of Probability 42(6) pp. 2383 – 2416, 2014.
  * [39] E. Vigoda. A Note on the Glauber Dynamics for Sampling Independent Sets. Electronic Journal of Combinatorics, 8(1): Research paper 8, 2001.
  * [40] D. Weitz. Counting independent sets up to the tree threshold. Proc.of 38th ACM Symposium on Theory of Computing (STOC), pp 140–149, 2006.

##  Appendix A Remaining Proofs

For the sake of keeping the paper self-contained, in this section we present
the proof of some well-known results presented in the main body.

###  A.1. Proof of Claim 4.1

Here we restate Claim 4.1 and provide its proof.

See 4.1

###### Proof.

Let $\Upsigma^{\Lambda,\tau}_{G}$ be the
$(V\times\Lambda)\times(V\times\Lambda)$ covariance matrix defined with
respect to $\mu^{\Lambda,\tau}$. That is, for any $u,v\in V\setminus\Lambda$
we have that

$\displaystyle\Upsigma^{\Lambda,\tau}_{G}(v,u)$
$\displaystyle=\mu^{\Lambda,\tau}_{(v,u)}((+1,+1))-\mu^{\Lambda,\tau}_{v}(+1)\cdot\mu^{\Lambda,\tau}_{u}(+1)\enspace.$

A straightforward observation is that $\Upsigma^{\Lambda,\tau}_{G}$ is
symmetric. W.l.o.g. in this proof, assume that the diagonal entries of
$\Upsigma^{\Lambda,\tau}_{G}$ are non-zero.

Note that for any $v\in V\setminus\Lambda$ we have that

$\displaystyle\UpM(v,v)=\sqrt{\Upsigma^{\Lambda,\tau}_{G}(v,v)}\enspace.$
(A.1)

Furthermore, it is standard to show, e.g. see [11], that
$\Upsigma^{\Lambda,\tau}_{G}$ and ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$ satisfy
that

$\displaystyle{{\mathcal{I}}}^{\Lambda,\tau}_{G}(u,v)$
$\displaystyle=\textstyle\frac{\Upsigma^{\Lambda,\tau}_{G}(u,v)}{\Upsigma^{\Lambda,\tau}_{G}(u,u)}\enspace.$

Since $\Upsigma^{\Lambda,\tau}_{G}$ is symmetric, the above relation implies
that

$\displaystyle\Upsigma^{\Lambda,\tau}_{G}(u,u)\cdot{{\mathcal{I}}}^{\Lambda,\tau}_{G}(u,v)$
$\displaystyle=\Upsigma^{\Lambda,\tau}_{G}(v,v)\cdot{{\mathcal{I}}}^{\Lambda,\tau}_{G}(v,u)\enspace.$

Then, a simple rearrangement gives

$\displaystyle\textstyle\sqrt{\frac{\Upsigma^{\Lambda,\tau}_{G}(u,u)}{\Upsigma^{\Lambda,\tau}_{G}(v,v)}}\cdot{{\mathcal{I}}}^{\Lambda,\tau}_{G}(u,v)$
$\displaystyle\textstyle=\sqrt{\frac{\Upsigma^{\Lambda,\tau}_{G}(v,v)}{\Upsigma^{\Lambda,\tau}_{G}(u,u)}}\cdot{{\mathcal{I}}}^{\Lambda,\tau}_{G}(v,u)\enspace.$

From (A.1) we get that

$\displaystyle\textstyle\frac{\UpM(u,u)}{\UpM(v,v)}\cdot{{\mathcal{I}}}^{\Lambda,\tau}_{G}(u,v)$
$\displaystyle\textstyle=\frac{\UpM(v,v)}{\UpM(u.u)}\cdot{{\mathcal{I}}}^{\Lambda,\tau}_{G}(v,u)\enspace.$

The l.h.s. in the above equation corresponds to the entry
$({}^{-1}\cdot{{\mathcal{I}}}^{\Lambda,\tau}_{G}\cdot\UpM)(u,v)$, while the
r.h.s. corresponds to
$({}^{-1}\cdot{{\mathcal{I}}}^{\Lambda,\tau}_{G}\cdot\UpM)(v,u)$.

The claim follows. ∎

###  A.2. Proof of Claim 9.3

Here we restate Claim 9.3 and provide its proof.

See 9.3

###### Proof.

For what follows, we abbreviate ${}^{\Lambda,\tau}_{G}$ and
${{\mathcal{I}}}^{\Lambda,\tau}_{G}$ to and ${{\mathcal{I}}}$, respectively.

Recall from (9.10) that is a block anti-diagonal matrix. For any vector ${\bf
z}$ such that $\left|\left|{\bf z}\right|\right|_{2}=1$, that can be written
as ${\bf z}=\left[\begin{array}[]{cc}{\bf y}\\\ {\bf x}\end{array}\right]$,
where ${\bf x},{\bf y}$ are $(V\setminus\Lambda)\times 1$ vectors, we have
that

$\UpW{\bf z}=\UpW\left[\begin{array}[]{cc}{\bf y}\\\ {\bf
x}\end{array}\right]=\left[\begin{array}[]{cc}{{\mathcal{I}}}{\bf x}\\\
{{\mathcal{I}}}^{*}{\bf y}\end{array}\right]\enspace.$

Hence

$\displaystyle\left|\left|\UpW{\bf z}\right|\right|^{2}_{2}$
$\displaystyle=\left|\left|{{\mathcal{I}}}{\bf
x}\right|\right|^{2}_{2}+\left|\left|{{\mathcal{I}}}^{*}{\bf
y}\right|\right|^{2}_{2}\enspace.$ (A.2)

Since $\left|\left|{\bf z}\right|\right|_{2}=1$, there is a scalar $b\in[0,1]$
such that $\left|\left|{\bf y}\right|\right|^{2}_{2}=b$ and $\left|\left|{\bf
x}\right|\right|^{2}_{2}=(1-b)$. Hence, we have that

$\displaystyle\left|\left|{{\mathcal{I}}}^{*}{\bf y}\right|\right|^{2}_{2}$
$\displaystyle\leq b\left|\left|{{\mathcal{I}}}^{*}\right|\right|^{2}_{2},$
$\displaystyle\left|\left|{{\mathcal{I}}}{\bf x}\right|\right|^{2}_{2}$
$\displaystyle\leq(1-b)\left|\left|{{\mathcal{I}}}\right|\right|^{2}_{2}\enspace.$
(A.3)

Plugging the inequalities from (A.3) into (A.2) we get

$\displaystyle\left|\left|\UpW{\bf z}\right|\right|^{2}_{2}$
$\displaystyle\leq
b\left|\left|\mathcal{J}^{*}\right|\right|^{2}_{2}+(1-b)\left|\left|\mathcal{J}\right|\right|^{2}_{2}\leq\max\left\\{\left|\left|\mathcal{J}\right|\right|^{2}_{2},\
\left|\left|\mathcal{J}^{*}\right|\right|^{2}_{2}\right\\}=\left|\left|\mathcal{J}\right|\right|^{2}_{2}\enspace.$

The last equality follows since
$\left|\left|\mathcal{J}\right|\right|^{2}_{2}=\left|\left|\mathcal{J}^{*}\right|\right|^{2}_{2}$.

Note that the above inequality is tight. It becomes equality if, for example,
${\bf y},{\bf x}$ are such that $\left|\left|{\bf y}\right|\right|_{2}=0$,
$\left|\left|{\bf x}\right|\right|_{2}=1$ and
$\left|\left|\mathcal{J}\right|\right|_{2}=\left|\left|\mathcal{J}{\bf
x}\right|\right|_{2}$.

Hence, we conclude that indeed
$\left|\left|\UpW\right|\right|_{2}=\left|\left|\mathcal{J}\right|\right|_{2}$.
The claim follows. ∎

###  A.3. Proof of Lemma 14.1

We restate Lemma 14.1 and provide its proof.

See 14.1

###### Proof.

It suffices to show that any $d>0$ and any
$({y}_{1},{y}_{2},\ldots,{y}_{d})\in[-\infty,+\infty]^{d}$ we have that

$\displaystyle||\nabla H_{d}({y}_{1},{y}_{2},\ldots,{y}_{d})||_{\infty}$
$\displaystyle\leq\frac{|\beta-1|}{\beta+1}\enspace.$ (A.4)

Before showing that (A.4) is true, let us show how it implies (14.3). That is,
we show that for any $\beta\in{\mathbb{U}_{\rm Ising}}(R,\zeta)$, we have that
$\frac{|\beta-1|}{\beta+1}\leq\frac{1-\zeta}{R}$.

Consider the function $f(x)=\frac{|x-1|}{x+1}$ defined on the closed interval
$\left[\frac{R-1}{R+1},\frac{R+1}{R-1}\right]$. Taking derivatives, it is
elementary to verify that $f(x)$ is increasing in the interval
$1<x\leq\frac{R+1}{R-1}$, while it is decreasing in the interval
$\frac{R-1}{R+1}\leq x<1$. Furthermore, noting that $f(1)=0$, it is direct
that

$\displaystyle\sup_{\beta\in{\mathbb{U}_{\rm
Ising}}(R,\zeta)}f(\beta)=\textstyle
f\left(\frac{R-1+\zeta}{R+1-\zeta}\right)=\textstyle
f\left(\frac{R+1-\zeta}{R-1+\zeta}\right)=\frac{1-\zeta}{R}\enspace.$

It is immediate that indeed (A.4) implies (14.3). Hence, it remains to show
that (A.4) is true.

Since we have that $\frac{\partial}{\partial
x_{i}}H_{d}(x_{1},x_{2},\ldots,x_{d})=h(x_{i})$, it suffices to show that for
any $x\in[-\infty,+\infty]$ we have that

$\displaystyle\left|h(x)\right|$
$\displaystyle\leq\textstyle\frac{|1-\beta|}{1+\beta}\enspace.$ (A.5)

For the distribution we consider here, the function $h(\cdot)$ is given from
(14.2). From the above we get that

$\displaystyle|h(x)|$
$\displaystyle\textstyle=\frac{|1-\beta^{2}|\exp(x)}{(b\exp(x)+1)(b+\exp(x))}\
=\ \frac{|1-\beta^{2}|}{(\beta+\exp(-x))(\beta+\exp(x))}\ =\
\frac{|1-\beta^{2}|}{\beta^{2}+1+\beta(\exp(-x)+\exp(x))}\enspace.$

It is straightforward to verify that $\phi(x)=e^{-x}+e^{x}$ is convex and for
any $x\in[-\infty,+\infty]$ the function $\phi(x)$ attains its minimum at
$x=0$, i.e., we have that $\phi(x)\geq 2$. Consequently, we get that

$\displaystyle|h(x)|$
$\displaystyle\leq\textstyle\frac{|1-\beta^{2}|}{\beta^{2}+1+2\beta}\ =\
\frac{|1-\beta^{2}|}{(\beta+1)^{2}}\ =\ \frac{|1-\beta|}{1+\beta}\enspace,$

for any $x\in[-\infty,+\infty]$. The above proves that (A.5) is true and
concludes our proof. ∎

###  A.4. Proof of Claim 15.2

We restate Claim 15.2 and provide its proof.

See 15.2

###### Proof.

It elementary to verify that ${\Delta_{c}}(z)$ is decreasing in $z$. This
implies that for $\lambda\leq(1-\varepsilon){\lambda_{c}}(R)$,
${\Delta_{c}}(\lambda)\geq{\Delta_{c}}({\lambda_{c}}(R))=R$. Particularly,
this implies that there is $0<z<1$, which only depends on $\varepsilon$ such
that ${\Delta_{c}}(\lambda)\geq\frac{R}{(1-z)}$. This proves the leftmost
inequality in (15.3).

As far as the rightmost inequality is concerned, we have that

$\displaystyle\textstyle\frac{\lambda}{1+\lambda}\leq\lambda<{\lambda_{c}}(R)\enspace.$
(A.6)

The first inequality follows since $\lambda>0$, while the second follows since
$\lambda<{\lambda_{c}}(R)$. From the definition of ${\lambda_{c}}(\cdot)$, we
have that

$\displaystyle{\lambda_{c}}(R)$
$\displaystyle\textstyle=\frac{R^{R}}{(R-1)^{(R+1)}}\ =\
\frac{1}{R}\left(1-R^{-1}\right)^{-(R+1)}\ =\
\frac{1}{R}\left(1+\frac{1}{R-1}\right)^{R+1}\ \leq\
\frac{1}{R}\exp\left(\frac{R+1}{R-1}\right)\ \leq\ e^{3}/R\enspace.$ (A.7)

For the one before the last inequality we use that $1+x\leq e^{x}$. For the
last inequality we note that $\frac{R+1}{R-1}$ is decreasing in $R$, hence,
for $R\geq 2$, we have that $\frac{R+1}{R-1}\leq 3$. Plugging the above bound
into (A.6), gives the rightmost inequality in (15.3). The claim follows. ∎

##  Appendix B Perron-Frobenius Theorem

Let the matrix $\Uplambda\in\mathbb{R}^{N\times N}$ be non-negative. That is,
every entry $\Uplambda_{i,j}\geq 0$. We say that $\Uplambda$ is irreducible if
and only if $(\UpI+\Uplambda)^{N-1}$ is a positive matrix, i.e., all its
entries are positive numbers.

We associate $\Uplambda$ with the directed graph $G_{\Uplambda}$ on the vertex
set $[N]$, while the edge $(i,j)$ is in $G_{\Uplambda}$ iff
$\Uplambda_{i,j}>0$. Then, $\Uplambda$ is irreducible, if the resulting graph
$G_{\Uplambda}$ is strongly connected.

In this work, it is common to use the so-called Perron-Frobenius Theorem. For
the sake of keeping this paper self-contained, we state this theorem below.

######  Theorem B.1 (Perron-Frobenius Theorem).

Let $\Uplambda\in\mathbb{R}^{N\times N}$ be irreducible and non-negative
matrix and suppose that $N\geq 2$. Then,

  1. (1)

${\rho}(\Uplambda)>0$

  2. (2)

${\rho}(\Uplambda)$ is an algebraically simple eigenvalue of $\Uplambda$

  3. (3)

there is a unique real vector ${\bf x}=({\bf x}_{1},\ldots,{\bf x}_{N})$ such
that $\Uplambda\cdot{\bf x}={\rho}(\Uplambda){\bf x}$ and ${\bf
x}_{1}+\cdots{\bf x}_{N}=1$, while ${\bf x}_{j}>0$ for all $j\in{N}$

  4. (4)

there is a unique real vector ${\bf y}=({\bf y}_{1},\ldots,{\bf y}_{N})$ such
that ${\bf y}^{T}\Uplambda={\rho}(\Uplambda){\bf y}^{T}$ and ${\bf x}_{1}{\bf
y}_{1}+\cdots{\bf x}_{N}{\bf y}_{N}=1$, while ${\bf y}_{j}>0$ for all
$j\in{N}$.


# A Strategy Optimized Pix2pix Approach for SAR-to-Optical Image Translation
Task

Fujian Cheng
STAR.VISION
<EMAIL_ADDRESS>Yashu Kang
STAR.VISION
<EMAIL_ADDRESS>Chunlei Chen
STAR.VISION
<EMAIL_ADDRESS>Kezhao Jiang
Columbia University
<EMAIL_ADDRESS>
###### Abstract

This technical report summarizes the analysis and approach on the image-to-
image translation task in the Multimodal Learning for Earth and Environment
Challenge (MultiEarth $2022$). In terms of strategy optimization, cloud
classification is utilized to filter optical images with dense cloud coverage
to aid the supervised learning alike approach. The commonly used pix2pix
framework with a few optimizations is applied to build the model. A weighted
combination of mean squared error and mean absolute error is incorporated in
the loss function. As for evaluation, peak to signal ratio and structural
similarity were both considered in our preliminary analysis. Lastly, our
method achieved the second place with a final error score of $0.0412$. The
results indicate great potential towards SAR-to-optical translation in remote
sensing tasks, specifically for the support of long-term environmental
monitoring and protection.

##  1 Introduction

Satellite remote sensing data has been widely used in various domains
including urban management, agriculture, climate change, environmental
monitoring[4, 1], _etc_. The recent advances in generation, enhancement and
interpretation of RS imagery have helped gaining attentions of the machine
learning community. On the other hand, the mass amount of available data
collected from various sensors also poses challenges. For instance, Synthetic
aperture radar (SAR) data is obtained through actively illuminating the ground
with radio waves rather than utilizing reflectance values as with optical
images, which is insensitive to lighting and weather conditions [5].

For instance, in the Multimodal Learning for Earth and Environment Challenge
(MultiEarth $2022$), a key component of this event is monitoring the Amazon
rainforest regardless of weather and lighting conditions by utilizing a time
series of multispectral and SAR images [3]. The data set covers Sentinel-1
synthetic aperture radar data, Sentinel-2 multispectral data, Landsat-5/8
multispectral data, etc. Such a multimodal data set offers new opportunities
for a variety of applications as well as posing new challenges.

The goal of image-to-image translation track is to predict a set of possible
cloud-free corresponding optical images given an input SAR image. Since rainy
weather occurs to the Amazon rainforest for most of an entire year, continuous
monitoring by optical imagery is extremely difficult. SAR has the advantage of
invariance to weather and lighting conditions. Thus, the application of SAR-
to-optical image translation are important topics when it comes to SAR
interpretation.

The image-to-image translation task is essentially transforming one kind of
representation of a scenario into another. In recent years, some studies have
utilized deep learning models on this task. Existing studies include pix2pix
based on conditional generative adversarial networks (cGAN) [6, 2], cycle-
consistent GAN (cycleGAN) [7, 8], _etc_. Despite the downside of high
computation cost, cGAN can reduce the speckle effect and produce relatively
smooth textures. As for cycleGAN, it is more likely to generate hallucinations
and d4eflected spatial accuracy compared with cGANs.

###  1.1 Methodology

###  1.2 Data preparation

To fill the gaps in optical images and obtain interpretation, the goal is that
the resultant optical images should also be free of dense cloud coverage. In
our preliminary analysis, we used a simple VGG classification model to select
data without presence of dense cloud. For instance, Fig. 1 demonstrates the
outcome of the data selection results. In addition, in our $data\\_loader$
module, pixel values are preprocessed by normalizing to $[-1,1]$.

Figure 1: Data selection using cloud classification method

###  1.3 Model architecture

Based on encoder-decoder framework, we utilize a classical pix2pix
architecture where the generator follows a U-net design and Convolutional
Neural Networks (CNN) discriminator, as shown in Fig. 2 and Fig. 3. Using
paired images as input, this modeling framework resembles a supervised
learning task. Note that the data preparation described in the previous
section helps guarantee that the objective image is not impacted by dense
cloud.

The most commonly used pix2pix model incorporates two loss functions for
training, conditional adversarial loss $L_{cGAN}$ and $L_{L1}$ which uses $L1$
norm to estimate difference with the target. This loss function considers both
speckling effect and artifacts of the generated images.

Figure 2: The U-net generator Figure 3: The CNN discriminator

We also restricted the discriminator by performing backpropagation calculation
every other training epoch to avoid an overpowered discriminator and slow
convergence for the generator. As for the loss function design, a weighted
combination of mean squared error (MSE) and mean absolute error (MAE) is used
in this model.

###  1.4 Evaluation metric

Performance is evaluated based on error score[3]:

$\sum_{j}\min_{i}\|f(x)_{i}-y_{j}\|$ (1)

where $f(x)_{i}$ is a set of generated output images and $y_{i}$ is the
corresponding optical image ground truth. That is, for each SAR image with two
channels, there will be three possible outcomes.

##  2 Analysis Results

In our preliminary experiment, we trained the model with uint16 and uint8
images, respectively. The results are shown in Fig. 4 and Fig. 5. It revealed
that textual information and spatial information were better preserved. In
addition, Peak signal to noise ratio (PSNR) and structural similarity (SSIM)
were both calculated between the generated image and ground truth.

PSNR, peak signal to noise ratio is a commonly used metric to define the
similarity between two images. It is calculated using the MSE of the pixels
and the maximum possible pixel value (MAX) as follows:

$PSNR=10\cdot\log\left({\frac{{MAX}^{2}}{MSE}}\right)$ (2)

SSIM, the structural similarity index (SSIM) is developed in order to take
luminance, contrast and structure of both images into account. It is
calculated on various windows of an image. The measure between two windows $x$
and $y$ of common size $N$ is:

$SSIM(x,y)=\frac{(2\mu_{x}\mu_{y}+c_{1})(2\sigma_{xy}+c_{2})}{(\mu_{x}^{2}+\mu_{y}^{2}+c_{1})(\sigma_{x}^{2}+\sigma_{y}^{2}+c_{2})}$
(3)

The uint16 experiment achieved average PSNR 20.734 and SSIM 0.735, while the
uint8 experiment achieved average PSNR 21.551 and SSIM 0.763.

Figure 4: Experiments with uint16 image input Figure 5: Experiments with uint8
image input Figure 6: Final submission

Lastly, Fig. 6 demonstrates a sample from our final submission. Besides, the
final submission achieved PSNR value $22.527$ and SSIM $0.732$. Besides, we
found that implementing cumulative count cut processing was more efficient in
producing more accurate output images and enhancing model convergence than
optimization for uint16 input images. Due to time constraints, our final model
achieved the second place with an error score of $0.0412$.

##  3 Conclusions

This technical report summarizes our efforts on SAR-to-optical image
translation task in the MultiEarth $2022$ challenge. To generate accurate
optical images from SAR input, we utilized cloud classification to filter
cloud-dense optical images, so that the task is approached supervised-
learning-like and the style of the generated images can be ensured. The deep
learning model followed a general pix2pix framework and obtained a final error
score of $0.0412$, achieving the second place. In terms of strategy
optimization, the data preprocessing proved to be beneficial to help preserve
relevant features in the original data set.

Overall, despite the availability of both SAR and optical data, the image
translation task still posed a big challenge for us. However, the outcome
indicates great potential towards SAR-to-optical translation in remote sensing
tasks, specifically for the support of long-term environmental monitoring
where dense cloud coverage is often present. Due to time constraints, we did
not fully explore optimizations of other alternatives such as cGAN, cycleGAN
or pix2pixHD, etc. In future work, it also will be beneficial to incorporate
attention mechanism, which is gaining momentum in other domain adaptation
tasks, in producing higher quality images and reduce impact of speckles.

## References

  * [1] Katherine Anderson, Barbara Ryan, William Sonntag, Argyro Kavvada, and Lawrence Friedl.  Earth observation in service of the 2030 agenda for sustainable development.  Geo-spatial Information Science, 20(2):77–96, 2017.
  * [2] Jose D Bermudez, Patrick N Happ, Raul Q Feitosa, and Dario AB Oliveira.  Synthesis of multispectral optical images from sar/optical multitemporal data using conditional generative adversarial networks.  IEEE Geoscience and Remote Sensing Letters, 16(8):1220–1224, 2019\.
  * [3] Miriam Cha, Kuan Wei Huang, Morgan Schmidt, Gregory Angelides, Mark Hamilton, Sam Goldberg, Armando Cabrera, Phillip Isola, Taylor Perron, Bill Freeman, et al.  Multiearth 2022–multimodal learning for earth and environment workshop and challenge.  arXiv preprint arXiv:2204.07649, 2022.
  * [4] Emilio Chuvieco, Jonathan Li, and Xiaojun Yang.  Advances in earth observation of global change.  Springer, 2010.
  * [5] Mario Fuentes Reyes, Stefan Auer, Nina Merkle, Corentin Henry, and Michael Schmitt.  Sar-to-optical image translation based on conditional generative adversarial networks—optimization, opportunities and limits.  Remote Sensing, 11(17):2067, 2019.
  * [6] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros.  Image-to-image translation with conditional adversarial networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1125–1134, 2017.
  * [7] Javier Noa Turnes, Jose David Bermudez Castro, Daliana Lobo Torres, Pedro Juan Soto Vega, Raul Queiroz Feitosa, and Patrick N Happ.  Atrous cgan for sar to optical image translation.  IEEE Geoscience and Remote Sensing Letters, 19:1–5, 2020.
  * [8] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In Proceedings of the IEEE international conference on computer vision, pages 2223–2232, 2017.