The above lemma implies the contraction we need in order to prove our result.
In light of Proposition 10.5 and Lemma 10.6, Theorem 10.2 follows. $\Box$

###  10.3. Proof of Proposition 10.5

The proposition follows by using results from [25]. 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}.$

Using the definitions in (73) and (75), 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}).$

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}.$
(80)

In order to prove (80), 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)}}.$ (81)

######  Claim 10.7.

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\textstyle={\psi}(F_{d}({\bf z}))\times\sum^{d}_{i=1}\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|,$ (82)

where $F_{d}$ and ${\psi}$ are defined in (73) and (81), 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}$
(83) $\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}.$

In (83), we substitute $\chi$ and $h$ according to (68) and (76),
respectively. Using the definition of ${\psi}$ from (81), we get that

$\displaystyle{\mathcal{J}}_{d}({\bf m},{\bf z})$
$\displaystyle=\textstyle{\psi}(F_{d}({\bf
z}))\sum^{d}_{j=1}\frac{1}{{\psi}({\bf z}_{j})}\times\frac{F_{d}(\bf
z)}{1+{\bf z}_{i}}\times{\bf m}_{j}.$

The above implies (82), 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 10.7, (80) 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^{d}_{i=1}\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}.$ (84)

The above follows by using standard results form [25]. 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},$

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

######  Lemma 10.8 ([25]).

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^{d}_{i=1}\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},$

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 10.9 ([25]).

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).$

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

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

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 10.8 and 10.9 we get (84). This concludes the proof of
Proposition 10.5. $\Box$

##  11\. Proofs of the results in Section 5

###  11.1. Proof of Theorem 5.2

Firstly we note that for ${\mathbold{\phi}}\in\mathbb{R}^{{\tt
E}_{\mathcal{S}}}$ as defined in (50), we have that

$\displaystyle\max_{e\in{\tt
E}_{\mathcal{S}}}\left\\{|{\mathbold{\phi}}(e)|\right\\}$
$\displaystyle\leq\sup\\{h(x)\ |\ x\in[-\infty,+\infty]\\}.$ (85)

The assumption that the set of functions $\\{H_{d}\\}_{d\in[{\Delta}]}$
exhibits $\delta$-contraction implies that

$\displaystyle\sup\\{h(x)\ |\ x\in[-\infty,+\infty]\\}\leq\delta.$ (86)

Combining (85) and (86), we have that

$\displaystyle\max_{e\in{\tt
E}_{\mathcal{S}}}\left\\{|{\mathbold{\phi}}(e)|\right\\}$
$\displaystyle\leq\delta.$ (87)

Recall from Lemma 6.4 that ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$ is a walk-
matrix. Furthermore, using Corollary 7.2 we get that

$\displaystyle\textstyle{\rho}\left({{\mathcal{I}}}^{\Lambda,\tau}_{G}\right)$
$\displaystyle\leq\textstyle{\rho}\left({{\mathbold{W}}}_{\textrm{MAX-$n$},\bar{{\mathbold{\psi}}}}\right).$
(88)

where the vector of weights $\bar{{\mathbold{\psi}}}$ has all its components
equal to $\delta$. Note that we choose MAX-$n$ because the length of any self-
avoiding path is $\leq n$. Since all the components of
$\bar{{\mathbold{\psi}}}$ have the same value $\delta>0$, Lemma 6.2 implies
that

$\displaystyle{{\mathbold{W}}}_{\textrm{MAX-$n$},\bar{{\mathbold{\psi}}}}$
$\displaystyle=\textstyle\sum^{n}_{\ell=0}\left(\delta\cdot{\bf
A}_{G}\right)^{\ell}.$

We have that

$\displaystyle{\rho}\left({{\mathbold{W}}}_{\textrm{MAX-$n$},\bar{{\mathbold{\psi}}}}\right)$
$\displaystyle\leq\left|\left|{{\mathbold{W}}}_{\textrm{MAX-$n$},\bar{{\mathbold{\psi}}}}\right|\right|_{2}\
=\ \textstyle\left|\left|\sum^{n}_{\ell=0}(\delta{\bf
A}_{G})^{\ell}\right|\right|_{2}\ \leq\
\textstyle\sum^{n}_{\ell=0}|\delta|^{\ell}\cdot\left|\left|({\bf
A}_{G})^{\ell}\right|\right|_{2}.$

Furthermore, since $\delta=\frac{1-\epsilon}{{\rho}_{G}}>0$ and
$\left|\left|({\bf A}_{G})^{\ell}\right|\right|_{2}=({\rho}_{G})^{\ell}$,
because ${\bf A}_{G})^{\ell}$ is symmetric, we get that

$\displaystyle{\rho}\left({{\mathbold{W}}}_{\textrm{MAX-$n$},\bar{{\mathbold{\psi}}}}\right)$
$\displaystyle\leq\textstyle\sum^{n}_{\ell=0}(1-\epsilon)^{\ell}\ \leq\
\sum^{\infty}_{\ell=0}(1-\epsilon)^{\ell}=\epsilon^{-1}.$

The theorem follows by plugging the above into (88). $\Box$

###  11.2. Proof of Theorem 5.5.

As we prove in Lemma 6.4 the matrix ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$ is
identical to the walk-matrix
${{\mathbold{W}}}_{\mathcal{S},{\mathbold{\phi}}}$, where $\mathcal{S}$ is the
set of self-avoiding walks in $G$ that do not use vertices in $\Lambda$, while
${\mathbold{\phi}}\in\mathbb{R}^{{\tt E}_{\mathcal{S}}}$ is defined in (50).
In that respect, it suffices to prove that under the assumption of Theorem 5.5
we have that

$\displaystyle{\rho}\left({{\mathbold{W}}}_{\mathcal{S},{\mathbold{\phi}}}\right)$
$\displaystyle\leq
1+\zeta\cdot(1-(1-\epsilon)^{s})^{-1}\cdot\left({{\Delta}}/{{\rho}_{G}}\right)^{1-\frac{1}{s}},$

where $\zeta,s$ and $\epsilon$ are specified in the statement of Theorem 5.5.

In light of Corollary 8.1 the above follows by showing that

$\displaystyle\left|\left|{{\mathbold{W}}}_{\mathcal{S},{\mathbold{\phi}}}\right|\right|_{\mathbold{S}_{{\mathcal{P}}},\frac{1}{s},\infty}$
$\displaystyle\leq
1+\zeta\cdot(1-(1-\epsilon)^{s})^{-1}\cdot\left({{\Delta}}/{{\rho}_{G}}\right)^{1-\frac{1}{s}},$
(89)

where $\mathbold{S}_{{\mathcal{P}}}\in\mathbb{R}^{V_{{\mathcal{P}}}\times
V_{{\mathcal{P}}}}_{\geq 0}$ is the diagonal matrix whose
entry$\mathbold{S}(u,u)={{\bf f}_{1}}(u)>0$.

In order to prove (89), we use Theorem 8.3. Particularly, (89) follows from
Theorem 8.3 once we show that the assumptions of Theorem 5.5 imply that we can
have $\mathbold{\gamma}\in\mathbb{R}^{{\tt E}_{\mathcal{S}}}_{>0}$ which is a
$(s^{\prime},\delta^{\prime},c^{\prime})$-potential with respect to
$\mathcal{S}$ and ${\mathbold{\phi}}$ where $s^{\prime}=s$,
$\delta^{\prime}=\frac{1-\epsilon}{{\rho}_{G}}$ and
$c^{\prime}=\frac{\zeta}{{\rho}_{G}}$. As mentioned above, $s,\epsilon$ and
$\zeta$ are specified in the statement of Theorem 5.5.

Note that Theorem 5.5 assumes the existence of a $(s,\delta,c)$-potential
${\Psi}$, for $s\geq 1$, $\delta=\frac{1-\epsilon}{{\rho}_{G}}$ and
$c=\frac{\zeta}{{\rho}_{G}}$. We let the function $\chi={\Psi}^{\prime}$. We
define the weights $\mathbold{\gamma}\in\mathbb{R}^{{\tt
E}_{\mathcal{S}}}_{>0}$ as follows: for any edge $e\in{\tt E}_{\mathcal{S}}$
such that $e=\\{u,w\\}$ and $w$ is the child of $u$, we have

$\displaystyle\mathbold{\gamma}(e)$ $\displaystyle=\chi(w).$

From the fact that ${\Psi}$ is a $(s,\delta,c)$-potential, it follows
immediately (i.e., from Definitions 5.4, 8.2) that the weights
$\mathbold{\gamma}$ are $(s^{\prime},\delta^{\prime},c^{\prime})$-potential
with respect to $\mathcal{S}$ and ${\mathbold{\phi}}$. For the above it is
useful to recall that the edge weights ${\mathbold{\phi}}$ are specified in
(50). This concludes the proof of Theorem 5.5. $\Box$

###  11.3. Proof of Theorem 5.3

Throughout the proof we use either $\nu_{G}$, or ${\rho}(\mathbold{H}_{G})$ to
refer to the spectral radius of $\mathbold{H}_{G}$ and this should create no
confusion.

Working as in the proof of Theorem 5.2, we have the following: for
${\mathbold{\phi}}$ defined in (50), we have that

$\displaystyle\max_{e}\left\\{|{\mathbold{\phi}}(e)|\right\\}$
$\displaystyle\leq\delta.$

Furthermore, using the above and Corollary 7.3 we get that

$\displaystyle\textstyle{\rho}\left({{\mathcal{I}}}^{\Lambda,\tau}_{G}\right)$
$\displaystyle\leq\textstyle{\rho}\left({{\mathbold{W}}}_{\textrm{
NB-$n$},\bar{{\mathbold{\psi}}}}\right)\leq{\rho}\left({{\mathbold{W}}}_{\textrm{
NB-$\infty$},\bar{{\mathbold{\psi}}}}\right).$

For the second inequality we use Lemma 4.4 and the fact that both
${{\mathbold{W}}}_{\textrm{ NB-$n$},\bar{{\mathbold{\psi}}}}$ and
${{\mathbold{W}}}_{\textrm{ NB-$\infty$},\bar{{\mathbold{\psi}}}}$ are non-
negative matrices. Since ${\rho}\left({{\mathbold{W}}}_{\textrm{
NB-$\infty$},\bar{{\mathbold{\psi}}}}\right)\leq\left|\left|{{\mathbold{W}}}_{\textrm{
NB-$\infty$},\bar{{\mathbold{\psi}}}}\right|\right|_{2}$, we have that

$\displaystyle\textstyle{\rho}\left({{\mathcal{I}}}^{\Lambda,\tau}_{G}\right)$
$\displaystyle\leq\left|\left|{{\mathbold{W}}}_{\textrm{
NB-$\infty$},\bar{{\mathbold{\psi}}}}\right|\right|_{2}.$ (90)

The assumption that $\delta=(1-\epsilon)/{\rho}(\mathbold{H}_{G})$, implies
that ${\rho}(\delta\mathbold{H}_{G})<1$, hence, it is standard that
$\sum_{\ell\geq
0}\delta^{\ell}\mathbold{H}^{\ell}_{G}=({\mathbold{I}}-\delta\cdot\mathbold{H}_{G})^{-1}.$
Hence, we get that

$\displaystyle{{\mathbold{W}}}_{\textrm{
NB-$\infty$},\bar{{\mathbold{\psi}}}}$
$\displaystyle={\mathbold{I}}+\delta\cdot{\bf
K}\cdot({\mathbold{I}}-\delta\cdot\mathbold{H}_{G})^{-1}\cdot{\bf C}.$ (91)

The theorem follows by simplifying the above and showing that

$\displaystyle{{\mathbold{W}}}_{\textrm{
NB-$\infty$},\bar{{\mathbold{\psi}}}}=\left({\mathbold{I}}-\delta{\bf
A}_{G}+\delta^{2}({\mathbold{D}}-{\mathbold{I}})\right)^{-1}.$ (92)

For $k\geq 0$, let ${\mathbold{W}}^{(k)}$ be the $V\times V$ matrix, such that
for every $u,w\in V$ the entry ${\mathbold{W}}^{(k)}(u,w)$ is equal to the
number of non-backtracking walks of length exactly $k$ from vertex $u$ to
vertex $w$. Note that

$\displaystyle{{\mathbold{W}}}_{\textrm{
NB-$\infty$},\bar{{\mathbold{\psi}}}}$
$\displaystyle=\sum^{\infty}_{k=0}\delta^{k}\cdot{\mathbold{W}}^{(k)}.$ (93)

From (91) we have that the above summation is well defined. Furthermore, we
have that ${\mathbold{W}}^{(0)}={\mathbold{I}}$ and ${\mathbold{W}}^{(1)}={\bf
A}_{G}$, while for $k\geq 2$, we have the following recursive relation:

$\displaystyle{\mathbold{W}}^{(k)}$ $\displaystyle={\bf
A}_{G}\cdot{\mathbold{W}}^{(k-1)}-({\mathbold{D}}-{\mathbold{I}}){\mathbold{W}}^{(k-2)}.$
(94)

The above recursive relation is standard in the literature, e.g. see [20].

Consider the generating function
${\mathbold{F}}(x)=\sum^{\infty}_{k=0}x^{k}\cdot{\mathbold{W}}^{(k)}$. Eq.
(91) implies that the radius of convergence for ${\mathbold{F}}(x)$ is the
open interval $(-\nu^{-1}_{G},\nu^{-1}_{G})$. Specifically, from (94) it
elementary to show that for any $x\in(-\nu^{-1}_{G},\nu^{-1}_{G})$ we have
that ${\mathbold{F}}(x)=({\mathbold{I}}-x{\bf
A}_{G}+x^{2}({\mathbold{D}}-{\mathbold{I}}))^{-1}$. Then, (92) follows by
noting that ${{\mathbold{W}}}_{\textrm{
NB-$\infty$},\bar{{\mathbold{\psi}}}}={\mathbold{F}}(\delta)$. The theorem
follows. $\Box$

##  12\. Proof of results from Section 6

###  12.1. Proof of Lemma 6.1

Consider the trees ${T}_{{\mathcal{P}}}(w)$ and ${T}_{{\mathcal{Q}}}(w)$.
Using standard notation, for ${T}_{{\mathcal{P}}}(w)$ we have ${\tt
A}_{{\mathcal{P}},w},{\tt E}_{{\mathcal{P}},w}$ the set of vertices and edges.
Similarly for ${T}_{{\mathcal{Q}}}(w)$ we have the corresponding sets ${\tt
A}_{{\mathcal{Q}},w}$ and ${\tt E}_{{\mathcal{Q}},w}$. The lemma follows by
showing that ${\tt A}_{{\mathcal{Q}},w}\subseteq{\tt A}_{{\mathcal{P}},w}$ and
${\tt E}_{{\mathcal{Q}},w}\subseteq{\tt E}_{{\mathcal{P}},w}$.

The relation that ${\tt A}_{{\mathcal{Q}},w}\subseteq{\tt
A}_{{\mathcal{P}},w}$ follows immediately from the fact that
${\mathcal{Q}}\subseteq{\mathcal{P}}$. Specifically, every walk
$M\in{\mathcal{Q}}\cap{\mathcal{P}}$ corresponds to the same vertex $z$ in
both trees. Since ${\mathcal{Q}}\subseteq{\mathcal{P}}$ we have that for
$M\in{\mathcal{Q}}$ we have $M\in{\mathcal{Q}}\cap{\mathcal{P}}$, as well.
This implies that every vertex $z$ in the tree ${T}_{{\mathcal{Q}}}(w)$ also
belongs to the tree ${T}_{{\mathcal{P}}}(w)$.

In order to prove that ${\tt E}_{{\mathcal{Q}},w}\subseteq{\tt
E}_{{\mathcal{P}},w}$ we work as follows: Let the edge $e=\\{x,z\\}$ in ${\tt
E}_{{\mathcal{Q}},w}$, while assume that $x$ is the parent of $z$ in the tree
${T}_{{\mathcal{Q}}}(w)$. There are walks $M_{a}=z_{0},z_{1},\ldots,z_{\ell}$
and $M_{b}=z_{0},z_{1},\ldots,z_{\ell-1}$, for $\ell\geq 1$ such that
$M_{a},M_{b}\in{\mathcal{Q}}$ while $M_{a}$ corresponds to the vertex $z$ in
${T}_{{\mathcal{Q}}}(w)$ and $M_{b}$ corresponds to the vertex $x$. Since we
have assumed that ${\mathcal{Q}}\subseteq{\mathcal{P}}$, we have that
$M_{a},M_{b}\in{\mathcal{P}}$. Consequently vertices $x,z$ appear in
${T}_{{\mathcal{P}}}(w)$, while they are adjacent and $x$ is the parent of
$z$. This implies that the edge $e\in{\tt E}_{{\mathcal{P}},w}$. Hence, we
conclude that ${\tt E}_{{\mathcal{Q}},w}\subseteq{\tt E}_{{\mathcal{P}},w}$.

The above concludes the proof of the lemma. $\Box$

###  12.2. Proof of Lemma 6.2

Let ${\mathbold{C}}=\textstyle\sum^{k}_{\ell=0}(\zeta\cdot{\bf
A}_{G})^{\ell}$. We prove the lemma by showing that for any $k\geq 0$ and any
pair of vertices $u,v\in V$, we have that

$\displaystyle{{\mathbold{W}}}_{\textrm{MAX-$k$},{\mathbold{\psi}}}(u,v)$
$\displaystyle={\mathbold{C}}(u,v).$ (95)

Note that both
${{\mathbold{W}}}_{\textrm{MAX-$k$},{\mathbold{\psi}}},{\mathbold{C}}\in\mathbb{R}^{V\times
V}$.

For any $u,v\in V$ and any integer $\ell\geq 1$, let
${\mathcal{M}}^{\ell}_{u,v}\subseteq V^{\ell+1}$ contain every $\ell+1$-tuple
of vertices $w_{0},w_{1},\ldots,w_{\ell}\in V^{\ell+1}$ such that $w_{0}=u$
and $w_{\ell}=v$. Note that we allow $w_{i}=w_{j}$. We also define
${\mathcal{M}}^{\ell}_{u,v}$ for $\ell=0$. In this case, we have that
${\mathcal{M}}^{0}_{u,v}=\\{u\\}$ only if $u=v$. Otherwise, the set is empty.

For $\ell\geq 0$, let $S_{\ell}$ be the set of all walks of length exactly
$\ell$ that start from $u$ and end at $v$ in the graph $G$. From the
definition of the set MAX-$k$ we have that

$\displaystyle{{\mathbold{W}}}_{\textrm{MAX-$k$},{\mathbold{\psi}}}(u,v)$
$\displaystyle=\
\sum^{k}_{\ell=0}\sum_{w_{0},\ldots,w_{\ell}\in{\mathcal{M}}^{\ell}_{u,v}}\zeta^{\ell}\times{\bf
1}\\{w_{0},\ldots,w_{\ell}\in S_{\ell}\\}.$ (96)

Now, consider the adjacency matrix ${\bf A}_{G}$. It is standard that for any
$u,v\in V$ and any $\ell\geq 0$, we have that

$\displaystyle\left({\bf A}_{G}\right)^{\ell}(u,v)$
$\displaystyle=\sum_{w_{0},\ldots,w_{\ell}\in{\mathcal{M}}^{\ell}_{u,v}}\prod_{i\in[\ell]}{\bf
A}_{G}(w_{i-1},w_{i}).$

Note that each summad on the r.h.s. is equal to $1$ if
$w_{0},w_{1},\ldots,w_{\ell}$ is a walk from $u$ to $v$ in $G$. Otherwise the
summad is zero. Using this observation, we conclude that

$\displaystyle\left({\bf A}_{G}\right)^{\ell}(u,v)$
$\displaystyle=\sum_{w_{0},\ldots,w_{\ell}\in{\mathcal{M}}^{\ell}_{u,v}}{\bf
1}\\{w_{0},\ldots,w_{\ell}\in S_{\ell}\\}.$

The above implies that

$\displaystyle{\mathbold{C}}(u,v)$
$\displaystyle=\sum^{k}_{\ell=0}\sum_{w_{0},\ldots,w_{\ell}\in{\mathcal{M}}^{\ell}_{u,v}}\zeta^{\ell}\times{\bf
1}\\{w_{0},\ldots,w_{\ell}\in S_{\ell}\\}.$ (97)

Comparing (97) and (96) we immediately get (95). The lemma follows. $\Box$

###  12.3. Proof of Lemma 6.3

Let
${\mathbold{M}}=\sum^{k-1}_{\ell=0}\zeta^{\ell+1}\cdot\mathbold{H}^{\ell}_{G}$,
while let ${\mathbold{D}}={\mathbold{I}}+\textstyle{\bf
K}\cdot{\mathbold{M}}\cdot{\bf C}$, where ${\mathbold{I}}$ is the $V\times V$
identity matrix and ${\bf K},{\bf C}$ are defined in (45). Note that
${\mathbold{M}}$ is a $\overrightarrow{E}\times\overrightarrow{E}$ matrix,
while both ${{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}$ and
${\mathbold{D}}$ are $V\times V$.

We prove the lemma by showing that for any $k\geq 0$ and any pair of vertices
$u,v\in V$, we have that

$\displaystyle{{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}(u,v)$
$\displaystyle={\mathbold{D}}(u,v).$ (98)

For $(x,y),(r,s)\in V\times V$, allowing repetitions, for integer $\ell\geq
3$, let ${\mathcal{M}}^{\ell}_{(x,y),(r,s)}\subseteq V^{\ell+1}$ contain every
$\ell+1$-tuple of vertices $w_{0},w_{1},\ldots,w_{\ell}\in V^{\ell+1}$ such
that $w_{0}=x$, $w_{1}=y$, $w_{\ell-1}=r$ and $w_{\ell}=s$. Note that we allow
$w_{i}=w_{j}$.

We also define ${\mathcal{M}}^{\ell}_{(x,y),(r,s)}$ for $1\leq\ell\leq 2$, but
there are some restriction on $x,y,r,s$. For $\ell=1$, we have that
${\mathcal{M}}^{1}_{(x,y),(r,s)}=\\{(x,y)\\}$ only if $x=r$ and $y=s$.
Otherwise, we have ${\mathcal{M}}^{1}_{(x,y),(r,s)}=\emptyset$. Similarly, for
$\ell=2$, we have ${\mathcal{M}}^{2}_{(x,y),(r,s)}=\\{x,y,s\\}$ is only
defined for $y=r$. Otherwise, we have
${\mathcal{M}}^{2}_{(x,y),(r,s)}=\emptyset$.

Furthermore, for $\ell\geq 1$, let $S_{\ell}(e,f)$ be the set of all non-
backtracking walks in $G$ of length exactly $\ell$ that start with edge $e$,
while the last edge in the path is $f$. For $e=(x,y)$ and $f=(r,s)$,
$S_{\ell}(e,f)$ contains the non-backtracking walks such that the first vertex
in the walk is $x$, the second is $y$ while the one before the last vertex is
$r$ and the last vertex is $s$. Note that for the extreme case $\ell=1$,
$S_{\ell}(e,f)$ is non-empty only if $e=f$.

From the definition of the set NB-$k$ we have that

$\displaystyle{{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}(u,v)$
$\displaystyle={\bf
1}\\{u=v\\}+\sum_{\begin{subarray}{c}e=(x,y)\in\overrightarrow{E}:\\\
x=u\end{subarray}}\ \
\sum_{\begin{subarray}{c}f=(r,s)\in\overrightarrow{E}:\\\ s=v\end{subarray}}\
\ \sum_{\ell\in[k]}\ \
\sum_{w_{0},\ldots,w_{\ell}\in{\mathcal{M}}^{\ell}_{e,f}}\zeta^{\ell}\times{\bf
1}\\{w_{0},\ldots,w_{\ell}\in S_{\ell}(e,f)\\}.$ (99)

Working as in the proof of Lemma 6.2, we get the following: for any $\ell\geq
0$ and $e,f\in\overrightarrow{E}$, we have that

$\displaystyle\mathbold{H}^{\ell}_{G}(e,f)$
$\displaystyle=\textstyle\sum_{w_{0},\ldots,w_{\ell}\in{\mathcal{M}}^{\ell+1}_{e,f}}{\bf
1}\\{w_{0},\ldots,w_{\ell}\in S_{\ell+1}(e,f)\\}.$

Hence, we have that

$\displaystyle{\mathbold{M}}(e,f)$
$\displaystyle=\sum^{k-1}_{\ell=0}\zeta^{\ell+1}\times\sum_{w_{0},\ldots,w_{\ell}\in{\mathcal{M}}^{\ell+1}_{e,f}}{\bf
1}\\{w_{0},\ldots,w_{\ell}\in S_{\ell+1}(e,f)\\}.$

Combining the above with (99), we get that

$\displaystyle{{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}(u,v)$
$\displaystyle={\bf
1}\\{u=v\\}+\sum_{\begin{subarray}{c}e=(x,y)\in\overrightarrow{E}:\\\
x=u\end{subarray}}\ \
\sum_{\begin{subarray}{c}f=(r,s)\in\overrightarrow{E}:\\\
s=v\end{subarray}}{\mathbold{M}}(e,f)$ (100)

Furthermore, the definition of ${\mathbold{D}}$, ${\bf K}$ and ${\bf C}$,
implies that

$\displaystyle\textstyle{\mathbold{D}}(u,v)$ $\displaystyle=\
\left({\mathbold{I}}+{\bf K}\cdot{\mathbold{M}}\cdot{\bf C}\right)(u,v)\ =\
{\bf 1}\\{u=v\\}+\sum_{(x,z)}\sum_{(y,q)}{\bf
K}_{u,(x,z)}{\mathbold{M}}_{(x,z),(y,q)}{\bf C}_{(y,q),v}$ $\displaystyle={\bf
1}\\{u=v\\}+\sum_{(x,z)}\sum_{(y,q)}{\bf 1}\\{u=x\\}\times{\bf
1}\\{q=v\\}\times{\mathbold{M}}_{(x,z),(y,q)}$ $\displaystyle={\bf
1}\\{u=v\\}+\sum_{\begin{subarray}{c}e=(x,y)\in\overrightarrow{E}:\\\
x=u\end{subarray}}\sum_{\begin{subarray}{c}f=(r,s)\in\overrightarrow{E}:\\\
s=v\end{subarray}}{\mathbold{M}}_{e,f}.$ (101)

From (100) and (101) we conclude that (98) is true. The lemma follows.

###  12.4. Proof of Lemma 6.4

Consider ${{\mathbold{W}}}_{{\rm SAW},\mathbold{\beta}}$ where
$\mathbold{\beta}$ is defined in (48). From the definition of the matrix we
have that ${{\mathbold{W}}}_{{\rm SAW},\mathbold{\beta}}$ is indexed by the
vertices in $V$. Also, we have that both ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$
and ${{\mathbold{W}}}_{{\mathcal{P}},{\mathbold{\phi}}}$ are matrices indexed
by the vertices in $V\setminus\Lambda$.

The lemma will follow by showing the following two relations: for any $w,v\in
V\setminus\Lambda$, we have that

$\displaystyle{{\mathcal{I}}}^{\Lambda,\tau}_{G}(w,v)$
$\displaystyle={{\mathbold{W}}}_{{\rm SAW},\mathbold{\beta}}(w,v),$ (102)

while, for the same $w,v$ we also have that

$\displaystyle{{\mathbold{W}}}_{\mathcal{S},{\mathbold{\phi}}}(w,v)$
$\displaystyle={{\mathbold{W}}}_{{\rm SAW},\mathbold{\beta}}(w,v).$ (103)

Note that the lemma follows by combining the above with (102).

We start by proving that (102) is true. From the definition of walk-matrix,
for $\mathbold{\beta}\in\mathbb{R}^{{\tt E}_{{\rm SAW}}}$, we have that
${{\mathbold{W}}}_{{\rm SAW},\mathbold{\beta}}\in\mathbb{R}^{V\times V}$,
while

$\displaystyle{{\mathbold{W}}}_{{\rm
SAW},\mathbold{\beta}}(w,v)={\textstyle\sum_{M}\prod_{e\in
M}}\mathbold{\beta}(e),$ (104)

where $M$ varies over the paths in ${T_{\rm SAW}}(w)$ from the root to the set
${\tt A}_{{\rm SAW},w}(v)$, while, as mentioned above, $\mathbold{\beta}$ is
specified in (48). In light of the above, it is immediate that (102) is true
by showing formally that (49) is true.

Consider $T={T_{\rm SAW}}(w)$ and the Gibbs distribution $\mu_{T}(\cdot\ |\
\Gamma,\sigma)$, where $\Gamma$ and $\sigma\in\\{\pm 1\\}^{\Gamma}$ are
defined in Section 6.3. With respect to the aforementioned Gibbs distribution,
let ${{\mathcal{I}}}^{\Gamma,\sigma}_{T}$ be the corresponding pairwise
influence matrix. The following result from [5] shows a useful relationship
between the two influences matrices ${{\mathcal{I}}}^{\Lambda,\tau}_{G}$ and
${{\mathcal{I}}}^{\Gamma,\sigma}_{T}$.

######  Lemma 12.1.

Let vertex $r$ be the root of the tree ${T_{\rm SAW}}(w)$. We have that

$\displaystyle{{\mathcal{I}}}^{\Lambda,\tau}_{G}(w,v)=\sum_{u\in{{\tt
A}}(v)}{{\mathcal{I}}}^{\Gamma,\sigma}_{T}(r,u),$ (105)

where for $s\in V$, ${\tt A}(s)$ is the set of copies of vertex $s$ in
${T_{\rm SAW}}(w)$ which do not belong in $\Gamma$.

Combining results from [1] and [5], we have the following lemma, whose proof
appears in Section 12.4.1.

######  Lemma 12.2.

Let $r$ be the root in ${T_{\rm SAW}}(w)$. For any vertex $u$ in ${T_{\rm
SAW}}(w)$, different than $r$, the following holds: letting
$z_{0},\ldots,z_{\ell}$ be the path in ${T_{\rm SAW}}(w)$ that connects the
root of the tree with $u$, i.e., $z_{0}=r$ and $z_{\ell}=u$, we have that

$\displaystyle{{\mathcal{I}}}^{\Gamma,\sigma}_{T}(r,u)$
$\displaystyle=\textstyle\prod^{\ell}_{i=1}\mathbold{\beta}(\\{z_{i-1},z_{i}\\}),$
(106)

where $\mathbold{\beta}\in\mathbb{R}^{{\tt E}_{{\rm SAW}}}$ is specified in
(48). Furthermore, we have ${{\mathcal{I}}}^{\Gamma,\sigma}_{T}(r,r)=1$.

In light of Lemmas 12.2 and 12.1, (49) follows as a simple corollary. We
conclude that (102) is true.

Now, consider the matrix ${{\mathbold{W}}}_{\mathcal{S},{\mathbold{\phi}}}$.
Similarly to (104), we have that

$\displaystyle{{\mathbold{W}}}_{\mathcal{S},{\mathbold{\psi}}}(w,v)={\textstyle\sum_{M}\prod_{e\in
M}}{\mathbold{\psi}}(e),$ (107)

where $M$ varies over the paths in ${T}_{\mathcal{S}}(w)$ from the root to the
set ${\tt A}_{\mathcal{S},w}(v)$.

Comparing the trees ${T}_{\mathcal{S}}(w)$ and ${T}_{{\rm SAW}}(w)$, we have
that the first one is a subtree of the second one. One obtains
${T}_{\mathcal{S}}(w)$ be removing the subtrees of ${T}_{{\rm SAW}}(w)$ which
are rooted to vertices in $\Gamma$. Due to (50), we have that
${{\mathbold{W}}}_{\mathcal{S},{\mathbold{\psi}}}(w,v)$ and
${{\mathbold{W}}}_{{\rm SAW},\mathbold{\beta}}(w,v)$ differ only on the sum of
the weight of the paths that appear in ${T}_{{\rm SAW}}(w)$ but do not appear
in ${T}_{\mathcal{S}}(w)$. However, it is immediate that the weight of these
paths is equal to zero. Note that each one of these paths involves at least
one vertex in $\Gamma$, while all the edges $e$ incident to such vertex have
$\mathbold{\beta}(e)=0$, i.e., this is due to (48). Hence, (103) is true.

All the above, conclude the proof of Lemma 6.4. $\Box$

####  12.4.1. Proof of Lemma 12.2

In order to prove Lemma 12.2, we only need to use the following two results
from [1] and [5], respectively.

######  Lemma 12.3 ([1]).

Suppose that $x,y,z$ are three distinct vertices in $T={T_{\rm SAW}}(w)$ such
that $y$ is on the unique path from $x$ to $z$. Then

$\displaystyle{{\mathcal{I}}}^{\Gamma,\sigma}_{T}(x,z)={{\mathcal{I}}}^{\Gamma,\sigma}_{T}(x,y)\times{{\mathcal{I}}}^{\Gamma,\sigma}_{T}(y,z).$

######  Lemma 12.4 ([5]).

Let $v,u$ be two vertices in $T={T_{\rm SAW}}(w)$, while suppose
$v\notin\Gamma$ and $u$ is a child of $v$. Then we have

$\displaystyle{{\mathcal{I}}}^{\Lambda,\tau}_{T}(v,u)$
$\displaystyle=\left\\{\begin{array}[]{lcl}h(\log{R}^{\Lambda,\tau}_{u})&&\textrm{if
$u\notin\Gamma$}\\\ 0&&\textrm{otherwise}.\\\ \end{array}\right.$ (110)

###### Proof of Lemma 12.2.

Recall that $z_{0},z_{1},\ldots,z_{\ell}$ is the path in $T$ that starts from
the root to the vertex $u$.

If $\ell=0$, then we immediately have
${{\mathcal{I}}}^{\Gamma,\sigma}_{T}(r,r)=1$. For what follows, we focus on
the case $\ell\geq 1$. Lemma 12.3 implies that

$\displaystyle{{\mathcal{I}}}^{\Gamma,\sigma}_{T}(r,u)$
$\displaystyle=\textstyle\prod^{\ell}_{i=1}{{\mathcal{I}}}^{\Lambda,\tau}_{T}(z_{i-1},z_{i}).$

Furthermore, Lemma 12.4 implies the following: If there is $z_{i}\in\Gamma$,
then

$\displaystyle{{\mathcal{I}}}^{\Gamma,\sigma}_{T}(r,u)=0,$

while if all $z_{i}$’s are outside $\Gamma$, then we have

$\displaystyle{{\mathcal{I}}}^{\Gamma,\sigma}_{T}(z_{i-1},z_{i})=h(\log{R}^{\Lambda,\tau}_{z_{i}}).$

From (48), it is immediate that

$\displaystyle{{\mathcal{I}}}^{\Gamma,\sigma}_{T}(r,u)$
$\displaystyle=\textstyle\prod^{\ell}_{i=1}\mathbold{\xi}(\\{z_{i-1},z_{i}\\}).$

The above concludes the proof. ∎

##  13\. Proofs for results from Section 7

###  13.1. Proof of Theorem 7.1

W.l.o.g. assume that the sets ${\mathcal{P}}$ and ${\mathcal{Q}}$ are non-
empty. For $u,v\in V_{{\mathcal{Q}}}\subseteq V_{{\mathcal{P}}}$ consider the
trees ${T}_{{\mathcal{Q}}}(u)$ and ${T}_{{\mathcal{P}}}(u)$. Let the sets
${\tt A}_{{\mathcal{Q}}}(v)$ and ${\tt A}_{{\mathcal{P}}}(v)$ be the set of
copies of the vertex $v$ in these two trees, respectively.

Let ${\mathcal{M}}_{{\mathcal{Q}}}$ be the set of paths in
${T}_{{\mathcal{Q}}}(u)$ that connect the root with the vertex set ${\tt
A}_{{\mathcal{Q}}}(v)$. Similarly, for the tree ${T}_{{\mathcal{P}}}(u)$ we
define the set of paths ${\mathcal{M}}_{{\mathcal{P}}}$.

For each $M\in{\mathcal{M}}_{{\mathcal{Q}}}$ we consider the weight ${\tt
weight}_{{\mathcal{Q}}}(M)$ which is as follows:

$\displaystyle{\tt weight}_{{\mathcal{Q}}}(M)$
$\displaystyle={\textstyle\prod_{e\in M}}\mathbold{\xi}_{1}(e).$

Similarly, for each $M\in{\mathcal{M}}_{{\mathcal{P}}}$ we consider the weight
${\tt weight}_{{\mathcal{P}}}(M)$ and the weights of the edges are specified
by $\mathbold{\xi}_{2}$.

First we focus on proving (52). For this we use the following claim.

######  Claim 13.1.

There is an injective map
$H:{\mathcal{M}}_{{\mathcal{Q}}}\to{\mathcal{M}}_{{\mathcal{P}}}$ such that
for every $M\in{\mathcal{M}}_{{\mathcal{Q}}}$, we have that

$\displaystyle{\tt weight}_{{\mathcal{Q}}}(M)\leq{\tt
weight}_{{\mathcal{P}}}(H(M)).$ (111)

###### Proof.

From Lemma 6.1 we have the following: Since
${\mathcal{Q}}\subseteq{\mathcal{P}}$, the tree ${T}_{{\mathcal{Q}}}(u)$ is a
subtree of ${T}_{{\mathcal{P}}}(u)$. We construct the injective map
$H:{\mathcal{M}}_{{\mathcal{Q}}}\to{\mathcal{M}}_{{\mathcal{P}}}$ such that it
maps every path $M$ in the tree ${T}_{{\mathcal{Q}}}(u)$ to the same path in
the tree ${T}_{{\mathcal{P}}}(u)$. The fact that $H(\cdot)$ is injective
follows from that ${T}_{{\mathcal{Q}}}(u)$ is a subtree of
${T}_{{\mathcal{P}}}(u)$.

As far as (13.1) is concerned, recall that

$\displaystyle{\tt weight}_{{\mathcal{Q}}}(M)$
$\displaystyle=\textstyle{\prod_{e\in M}}\mathbold{\xi}_{1}(e)$ and
$\displaystyle{\tt weight}_{{\mathcal{Q}}}(H(M))$
$\displaystyle={\textstyle\prod_{e\in H(M)}}\mathbold{\xi}_{2}(e).$

However, from the definition of $H(\cdot)$ we have that the set of edges in
$M$ is exactly the same as the set of edges in $H(M)$. Then, we get (111) by
recalling that for any edge $e$ that appears in both
${T}_{{\mathcal{Q}}}(u),{T}_{{\mathcal{P}}}(u)$ we have that
$\mathbold{\xi}_{1}(e)\leq\mathbold{\xi}_{2}(e)$. The claim follows. ∎

Let ${\mathcal{S}}\subseteq{\mathcal{M}}_{{\mathcal{P}}}$ be such that
${\mathcal{S}}={\mathcal{M}}_{{\mathcal{P}}}\setminus{\mathcal{M}}_{{\mathcal{Q}}}$,
that is ${\mathcal{S}}$ contains every $M\in{\mathcal{M}}_{{\mathcal{P}}}$
such that there is no $M^{\prime}\in{\mathcal{M}}_{{\mathcal{Q}}}$ for which
$H(M^{\prime})=M$. Using the above claim, we have that

$\displaystyle{{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}(w,v)$
$\displaystyle\textstyle=\sum_{M\in{\mathcal{M}}_{{\mathcal{P}}}}{\tt
weight}(M)\ =\ \sum_{M\in{\mathcal{M}}_{{\mathcal{Q}}}}{\tt
weight}(H(M))+\sum_{M\in{\mathcal{S}}}{\tt weight}(M)$
$\displaystyle\textstyle\geq\sum_{M\in{\mathcal{M}}_{{\mathcal{Q}}}}{\tt
weight}(M)+\sum_{M\in{\mathcal{S}}}{\tt
weight}(M)\qquad\qquad\qquad\mbox{[from Claim \ref{claim:Injection2Edges}]}$
$\displaystyle\textstyle\geq\sum_{M\in{\mathcal{M}}_{{\mathcal{Q}}}}{\tt
weight}(M)\ =\ {{\mathbold{W}}}_{{\mathcal{Q}},\mathbold{\xi}_{1}}(w,v).$

The inequality in the last line follows by noting that for every
$M\in{\mathcal{S}}$ we have that ${\tt weight}_{{\mathcal{P}}}(M)\geq 0$,
i.e., since we have $\mathbold{\xi}_{2}\in\mathbb{R}^{{\tt
E}_{{\mathcal{P}}}}_{\geq 0}$. The above proves that (52) is true.

As far as (53) is concerned, let us first prove it by using the assumption
that $V_{{\mathcal{P}}}=V_{{\mathcal{Q}}}$. In this case, note that the two
matrices ${{\mathbold{W}}}_{{\mathcal{Q}},\mathbold{\xi}_{1}}$,
${{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$ are indexed by the same
set of vertices, and hence, they are of the same dimension. Furthermore, from
the assumption that $\mathbold{\xi}_{2}\in\mathbb{R}^{{\tt
E}_{{\mathcal{P}}}}_{\geq 0}$ we have that
${{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$ is non-negative matrix,
while (52) implies that

$\displaystyle|{{\mathbold{W}}}_{{\mathcal{Q}},\mathbold{\xi}_{1}}|\leq{{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}_{2}},$

where recall that for the matrices ${{\mathbold
A}},{\mathbold{B}},{\mathbold{C}}\in\mathbb{R}^{N\times N}$, we let
$|{{\mathbold A}}|$ denote the matrix having entries $|{{\mathbold
A}}_{i,j}|$. while we defined ${\mathbold{B}}\leq{\mathbold{C}}$ to mean that
${\mathbold{B}}_{i,j}\leq{\mathbold{C}}_{i,j}$ for each $i$ and $j$.

Then, (53) follows from the above by using Lemma 4.4.

We now proceed with (53) and assuming that
$|V_{{\mathcal{P}}}|>|V_{{\mathcal{Q}}}|$, and
${{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$ is symmetric. Consider
the matrix
${{\mathbold{W}}}^{V_{{\mathcal{Q}}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$,
this is the principle submatrix of
${{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$ obtained by removing the
rows and columns that correspond to the vertices in
$V_{{\mathcal{P}}}\setminus V_{{\mathcal{Q}}}$.

Note, now, that
${{\mathbold{W}}}^{V_{{\mathcal{Q}}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$ and
${{\mathbold{W}}}_{{\mathcal{Q}},\mathbold{\xi}_{1}}$ are indexed by the same
set of vertices. Additionally, we have that
$|{{\mathbold{W}}}_{{\mathcal{Q}},\mathbold{\xi}_{1}}|\leq{{\mathbold{W}}}^{V_{{\mathcal{Q}}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$,
which, together with Lemma 4.4, implies that

$\displaystyle{\rho}\left({{\mathbold{W}}}_{{\mathcal{Q}},\mathbold{\xi}_{1}}\right)$
$\displaystyle\leq{\rho}\left({{\mathbold{W}}}^{V_{{\mathcal{Q}}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}\right).$

However, since we assumed that
${{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$ is symmetric and
${{\mathbold{W}}}^{V_{{\mathcal{Q}}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$ is a
principal submatrix of ${{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}$,
we also have that

$\displaystyle{\rho}\left({{\mathbold{W}}}^{V_{{\mathcal{Q}}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}\right)\leq{\rho}\left({{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}_{2}}\right).$

The above is a consequence of the well-known Cauchy’s interlacing theorem,
e.g. see [17]. Combining the two inequalities above it is immediate to get
(53). The theorem follows. $\Box$

##  14\. Proof of results from Section 8

###  14.1. Proof of Theorem 8.3

We use Theorems 8.5, 8.6 and Corollary 8.7 to prove the theorem. Particularly,
using these results, we obtain the following:

For the walk-vector
$\mathbold{q}_{\textrm{MAX-$k$}}=\mathbold{q}_{\textrm{MAX-$k$}}\left(\textrm{MAX-$k$},{\mathbold{S}}^{\circ({1}/{s})},s,\delta,c\right)$,
where the $V\times V$ matrix $\mathbold{S}$ is defined in (25), we have that

$\displaystyle\left|\left|{{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}}\right|\right|_{\mathbold{S}_{{\mathcal{P}}},\frac{1}{s},\infty}$
$\displaystyle\leq\left|\left|\mathbold{q}_{\textrm{MAX-$k$}}\right|\right|_{\infty}.$
(112)

Recall that the diagonal matrix $\mathbold{S}_{{\mathcal{P}}}$ at the index of
the matrix norm, is obtained from $\mathbold{S}$ by removing the rows and
columns that correspond to vertices outside $V_{{\mathcal{P}}}$. In light of
(112), the theorem follows showing that

$\displaystyle\left|\left|\mathbold{q}_{\textrm{MAX-$k$}}\right|\right|_{\infty}$
$\displaystyle\leq
1+c\cdot\left({\Delta}\right)^{1-\frac{1}{s}}\cdot\left({\rho}_{G}\right)^{\frac{1}{s}}\cdot{\textstyle\sum^{k-1}_{\ell=0}}(\delta\cdot{\rho}_{G})^{\frac{\ell}{s}}.$
(113)

According to Definition 8.4, for every $r\in V$ the entry
$\mathbold{q}_{\textrm{MAX-$k$}}(r)$ satisfies

$\displaystyle\mathbold{q}_{\textrm{MAX-$k$}}(r)$
$\displaystyle\textstyle=1+\frac{c}{\left(\mathbold{S}(r,r)\right)^{\frac{1}{s}}}\times\sum^{d}_{i=1}\sum^{k-1}_{\ell=0}\left(\delta^{\ell}\cdot\sum_{w\in
V}|{\tt A}_{i,\ell}(w)|\cdot\mathbold{S}(w,w)\right)^{\frac{1}{s}}.$

In order to study the above quantity, note that the walk-tree of interest is
${T}_{\textrm{MAX-$k$}}(r)$.

Let us recall the quantities in the above expression. The quantity $d$ is the
degree of the root of the walk-tree ${T}_{\textrm{MAX-$k$}}(r)$. Letting
$T_{i}$ be the subtree that is induced by the $i$-th child of the root of
${T}_{\textrm{MAX-$k$}}(r)$ and its decedents, ${\tt A}_{i,\ell}(w)$ is the
set of copies of vertex $w$ in the subtree $T_{i}$ that are at distance $\ell$
from the root of $T_{i}$.

Using that $\mathbold{S}(w,w)={{\bf f}_{1}}(w)$ for every $w\in V$, we have
that

$\displaystyle\mathbold{q}_{\textrm{MAX-$k$}}(r)$
$\displaystyle\textstyle=1+\frac{c}{\left({{\bf
f}_{1}}(r)\right)^{\frac{1}{s}}}\times\sum^{d}_{i=1}\sum^{k-1}_{\ell=0}\left(\delta^{\ell}\cdot\sum_{w\in
V}|{\tt A}_{i,\ell}(w)|\cdot{{\bf f}_{1}}(w)\right)^{\frac{1}{s}}.$ (114)

For $\ell\geq 1$, for every $x,w\in V$, let ${\tt
A}_{i,x,\ell}(w)\subseteq{\tt A}_{i,\ell}(w)$ be the set which contains all
vertices $u$ in $T_{i}$, copies of $w$, such that the parent of $u$ is in
${\tt A}_{i,(\ell-1)}(x)$.

Since we assumed that the graph $G$ is simple, it is straightforward that for
all $w\in V$, there are no two copies of $w$ in ${T}_{\textrm{MAX-$k$}}(r)$
that have the same parent. This implies that $|{\tt A}_{i,(\ell-1)}(x)|$ is
equal to $|{\tt A}_{i,x,\ell}(w)|$, for any $w$ neighbour of $x$ in $G$. Using
this observation, we have that

$\displaystyle\sum_{w\in V}|{\tt A}_{i,\ell}(w)|\cdot{{\bf f}_{1}}(w)$
$\displaystyle=\sum_{w\in V}\sum_{x\in V}|{\tt A}_{i,x,\ell}(w)|\cdot{{\bf
f}_{1}}(w)$ $\displaystyle=\ \sum_{x\in V}\sum_{w\in V}|{\tt
A}_{i,x,\ell}(w)|\cdot{{\bf f}_{1}}(w)$ (115) $\displaystyle=\sum_{x\in
V}|{\tt A}_{i,\ell-1}(x)|\sum_{w\in V:\\{w,x\\}\in E}{{\bf f}_{1}}(w),$

where in the second equation changed order of summation. Using the definition
of ${{\bf f}_{1}}$, note that the last summation is equal $\theta_{\rm
max}({\bf A}_{G}){{\bf f}_{1}}(x)$. Hence, we have that

$\displaystyle{\textstyle\sum_{w\in V}}|{\tt A}_{i,\ell}(w)|\cdot{{\bf
f}_{1}}(w)$ $\displaystyle=\theta_{\rm max}({\bf
A}_{G})\cdot{\textstyle\sum_{x\in V}}|{\tt A}_{i,\ell-1}(x)|\cdot{{\bf
f}_{1}}(x)\ =\ {\rho}_{G}\cdot{\textstyle\sum_{x\in V}}|{\tt
A}_{i,\ell-1}(x)|\cdot{{\bf f}_{1}}(x).$

For the last equality we use that $\theta_{\rm max}({\bf A}_{G})={\rho}({\bf
A}_{G})$. This equality is a standard application of the Perron-Frobenius
Theorem 444Note that the assumption that $G$ is connected, implies that ${\bf
A}_{G}$ is a non-negative, irreducible matrix.. Repeating the above $\ell$
times in total, we get that

$\displaystyle{\textstyle\sum_{w\in V}}|{\tt A}_{i,\ell}(w)|\cdot{{\bf
f}_{1}}(w)$ $\displaystyle=\left({\rho}_{G}\right)^{\ell}\cdot{{\bf
f}_{1}}(k_{i}),$

where $k_{i}\in V$ is such that the root of $T_{i}$ belongs in ${\tt
A}(k_{i})$. Note that the above applies for $\ell\geq 1$. For $\ell=0$, it is
immediate that $\sum_{w\in V}|{\tt A}_{i,\ell}(w)|\cdot{{\bf f}_{1}}(w)={{\bf
f}_{1}}(k_{i})$.

Plugging the above into (114) and rearranging, we get that

$\displaystyle\mathbold{q}_{\textrm{MAX-$k$}}(r)$
$\displaystyle=1+c\cdot\sum^{k-1}_{\ell=0}\left(\delta\cdot{\rho}_{G}\right)^{\frac{\ell}{s}}\cdot\sum^{d}_{i=1}\left(\frac{{{\bf
f}_{1}}(k_{i})}{{{\bf f}_{1}}(r)}\right)^{\frac{1}{s}}.$ (116)

Note that the vertices $k_{1},\ldots,k_{d}$ are the neighbours of $r$ in the
graph $G$.

We need to bound the rightmost sum in the equation above. Recall that we have
$\theta_{\rm max}({\bf A}_{G})={\rho}({\bf A}_{G})$, which implies that
$\sum^{d}_{i=1}{{\bf f}_{1}}(k_{i})={\rho}_{G}\cdot{{\bf f}_{1}}(r)$. Using
this observation, we get that

$\displaystyle\sum^{d}_{i=1}\left(\frac{{{\bf f}_{1}}(k_{i})}{{{\bf
f}_{1}}(r)}\right)^{\frac{1}{s}}$
$\displaystyle\leq\max_{\begin{subarray}{c}z_{1},\ldots,z_{d}\ \in\
(0,{\rho}_{G}):\\\
\sum_{i}z_{i}={\rho}_{G}\end{subarray}}\sum^{d}_{i=1}(z_{i})^{\frac{1}{s}}\
\leq\ \sum^{d}_{i=1}\left(\frac{{\rho}_{G}}{d}\right)^{\frac{1}{s}}\ =\
d^{1-\frac{1}{s}}\left({\rho}_{G}\right)^{\frac{1}{s}}.$ (117)

In the above series of inequalities, we use the following observations: Since
we assumed that $s\geq 1$, it is elementary to show that for
$z_{1},\ldots,z_{d}>0$, the function
$f(z_{1},\ldots,z_{d})=\sum^{d}_{i=1}(z_{i})^{\frac{1}{s}}$ is concave. In the
interval specified by the restrictions $z_{1},\ldots,z_{d}\in\ (0,{\rho}_{G})$
and $\sum_{i}z_{i}={\rho}_{G}$, due to concavity, the function
$f(z_{1},\ldots,z_{d})$ attains its maximum when all $z_{i}$’s are equal with
each other, i.e., $z_{i}=\frac{{\rho}_{G}}{d}$, for $i=1,\ldots,d$.

Plugging (117) into (116) we get that

$\displaystyle\mathbold{q}_{\textrm{MAX-$k$}}(r)$ $\displaystyle\leq 1+c\cdot
d^{1-\frac{1}{s}}\cdot\left({\rho}_{G}\right)^{\frac{1}{s}}\cdot{\textstyle\sum^{k-1}_{\ell=0}}\left(\delta\cdot{\rho}_{G}\right)^{\frac{\ell}{s}}\
\leq\
1+c\cdot{\Delta}^{1-\frac{1}{s}}\cdot\left({\rho}_{G}\right)^{\frac{1}{s}}\cdot{\textstyle\sum^{k-1}_{\ell=0}}\left(\delta\cdot{\rho}_{G}\right)^{\frac{\ell}{s}}.$

For the last inequality we use that $d\leq{\Delta}$.

Noting that the above bound holds for any $r\in V$, it is immediate to get
(113). The theorem follows. $\Box$

###  14.2. Proof of Theorem 8.5

Let
${\mathbold{C}}=({\mathbold{D}}^{\circ\frac{1}{s}})^{-1}\cdot{{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}}\cdot{\mathbold{D}}^{\circ\frac{1}{s}}$.
The theorem follows by showing that

$\displaystyle{\textstyle\sum_{u\in
V_{{\mathcal{P}}}}}\left|{\mathbold{C}}(r,u)\right|$
$\displaystyle\leq\mathbold{q}(r)$ $\displaystyle\forall r\in
V_{{\mathcal{P}}},$ (118)

for the walk-vector
$\mathbold{q}=\mathbold{q}({\mathcal{P}},{\mathbold{D}}^{\circ\frac{1}{s}},s,\delta,c)$
specified in the statement of Theorem 8.5.

Before showing that (118) is indeed true, let us show how we can use it to
prove the theorem. From the definition of the norm
$\left|\left|\cdot\right|\right|_{{\mathbold{D}},\frac{1}{s},\infty}$, it is
immediate that

$\displaystyle\left|\left|{{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}}\right|\right|_{{\mathbold{D}},\frac{1}{s},\infty}=\left|\left|{\mathbold{C}}\right|\right|_{\infty}\
=\ \max_{r}\left\\{{\textstyle\sum_{w\in
V_{{\mathcal{P}}}}}|{\mathbold{C}}(r,w)|\right\\}.$ (119)

Recalling that $\mathbold{q}$ is a strictly positive vector, using (119) and
(118) we conclude that

$\displaystyle\left|\left|{{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}}\right|\right|_{{\mathbold{D}},\frac{1}{s},\infty}$
$\displaystyle\leq\max_{r}\mathbold{q}(r)\ =\
\left|\left|\mathbold{q}\right|\right|_{\infty}.$

It remains to show that (118) is true. For $r\in V_{{\mathcal{P}}}$, consider
the walk-tree $T={T}_{{\mathcal{P}}}(r)$. Also, consider a path $M$ of length
$\ell$ in $T$ that emanates from the root, while let
$e_{1},e_{2},\ldots,e_{\ell}$ be the edges on this path. In order to define
${{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}}$, we specify that $M$ has
weight such that

$\displaystyle{\tt weight}(M)$
$\displaystyle=\textstyle\prod^{\ell}_{i=1}\mathbold{\xi}(e_{i}),$

where the weights $\mathbold{\xi}$ are specified in the statement of Theorem
8.5.

We use a simple telescopic trick to write the weight of $M$ slightly
differently than what we have above, i.e., involve the potential vector
$\mathbold{\gamma}$.

######  Claim 14.1.

We have that

$\displaystyle{\tt weight}(M)$
$\displaystyle=\mathbold{\gamma}(e_{\ell})\frac{\mathbold{\xi}(e_{1})}{\mathbold{\gamma}(e_{1})}\prod^{\ell}_{i=2}\frac{\mathbold{\gamma}(e_{i-1})}{\mathbold{\gamma}(e_{i})}\mathbold{\xi}(e_{i}).$

###### Proof.

Since, for every $e_{i}\in{\tt E}_{{\mathcal{P}},r}$ we have that
$\mathbold{\gamma}(e_{i})>0$, it holds that

$\displaystyle{\tt weight}(M)$
$\displaystyle=\textstyle\prod^{\ell}_{i=1}\frac{\mathbold{\gamma}(e_{i})}{\mathbold{\gamma}(e_{i})}\mathbold{\xi}(e_{i})\
=\
\mathbold{\gamma}(e_{\ell})\frac{\mathbold{\xi}(e_{1})}{\mathbold{\gamma}(e_{1})}\prod^{\ell}_{i=2}\frac{\mathbold{\gamma}(e_{i-1})}{\mathbold{\gamma}(e_{i})}\mathbold{\xi}(e_{i}).$

The claim follows. ∎

For any $u\in V_{{\mathcal{P}}}$ and any integer $\ell\geq 0$, let
${{\mathcal{M}}}(\ell,u)$ be the set of paths of length $\ell$ in $T$ that
connect the root of the tree with a vertex $v\in{\tt A}(u)$.

From the definition of ${{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}}$,
recall that

$\displaystyle{{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}}(r,u)=\sum_{\ell\geq
0}\sum_{M\in{\mathcal{M}}(\ell,u)}{\tt weight}(M).$

Since
${\mathbold{C}}=({\mathbold{D}}^{\circ\frac{1}{s}})^{-1}\cdot{{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}}\cdot{\mathbold{D}}^{\circ\frac{1}{s}}$
and ${\mathbold{D}}^{\circ\frac{1}{s}}$ is diagonal, for any $u\in
V_{{\mathcal{P}}}$ we have that

$\displaystyle{\mathbold{C}}(r,u)$
$\displaystyle\textstyle=\frac{{\mathbold{D}}^{\circ\frac{1}{s}}(u,u)}{{\mathbold{D}}^{\circ\frac{1}{s}}(r,r)}\cdot{{\mathbold{W}}}_{{\mathcal{P}},\mathbold{\xi}}(r,u)\
=\
\frac{{\mathbold{D}}^{\circ\frac{1}{s}}(u,u)}{{\mathbold{D}}^{\circ\frac{1}{s}}(r,r)}\sum_{\ell\geq
0}\sum_{M\in{\mathcal{M}}(\ell,u)}{\tt weight}(M).$ (120)

For every integer $\ell\geq 0$, we let

$\displaystyle{\mathbold{C}}^{(\ell)}$
$\displaystyle\textstyle=\frac{1}{{\mathbold{D}}^{\circ\frac{1}{s}}(r,r)}\left|\sum_{u\in
V_{{\mathcal{P}}}}\sum_{M\in{\mathcal{M}}(\ell,u)}{\tt
weight}(M)\cdot{\mathbold{D}}^{\circ\frac{1}{s}}(u,u)\right|.$

It is easy to see that ${\mathbold{C}}^{(0)}=1$. From the definition of
${\mathbold{C}}^{(\ell)}$ and (120), it is immediate that

$\displaystyle{\textstyle\sum_{u\in
V_{{\mathcal{P}}}}}\left|{\mathbold{C}}(r,u)\right|$
$\displaystyle\leq{\textstyle\sum_{\ell\geq 0}}{\mathbold{C}}^{(\ell)}\ =\
1+\textstyle{\sum_{\ell\geq 1}}{\mathbold{C}}^{(\ell)}.$ (121)

Given some fixed $\ell\geq 1$, for $m=0,\ldots,\ell$ consider the vertex $z$
at distance $m$ from the root of $T$. Suppose that $d_{z}$ is the number of
children of $z$ in $T_{z}$, while let $x_{1},x_{2},\ldots,x_{d_{z}}$ be these
children. Recall that $T_{z}$ is the subtree that is induced by $z$ and all
its descendant in $T$.

With respect to vertex $z$, we define the quantity
${{\mathcal{J}}}_{z}(\ell-m)$ as follows: For $m=\ell$, we have that

$\displaystyle{{\mathcal{J}}}_{z}(0)$ $\displaystyle\textstyle=\sum_{u\in
V_{{\mathcal{P}}}}\mathbf{1}\\{z\in{\tt
A}(u)\\}\times{\mathbold{D}}^{\circ\frac{1}{s}}(u,u).$ (122)

For $0<m<\ell$, the quantity ${{\mathcal{J}}}_{z}(\ell-m)$ satisfies the
following recursive relation:

$\displaystyle{{\mathcal{J}}}_{z}(\ell-m)$
$\displaystyle=\textstyle\mathbold{\gamma}(e_{z})\sum^{d_{z}}_{j=1}\frac{|\mathbold{\xi}(e_{j})|}{\mathbold{\gamma}(e_{j})}\times{{\mathcal{J}}}_{x_{j}}(\ell-m-1),$

where $e_{z}$ is the edge that connect $z$ with its parent, while $e_{j}$ is
the edge that connects $z$ with its child $x_{j}$. Note that since we assumed
that $z$ is at level $m>0$ it has a parent, i.e., $z$ is not the root of $T$.

Finally, for $m=0$, i.e., $z$ and the root of $T$ are identical, we have that

$\displaystyle{{\mathcal{J}}}_{z}(\ell)$
$\displaystyle\textstyle=\frac{1}{{\mathbold{D}}^{\circ\frac{1}{s}}(r,r)}\max_{e_{1},e_{2}\in{\tt
E}_{{\mathcal{P}},r}}\left\\{\mathbold{\gamma}(e_{1})\cdot\frac{|\mathbold{\xi}(e_{2})|}{\mathbold{\gamma}(e_{2})}\right\\}\sum^{d_{z}}_{j=1}\left|{{\mathcal{J}}}_{x_{j}}(\ell-1)\right|.$
(123)

Claim 14.1 and an elementary induction imply that for any $\ell\geq 1$, we
have

$\displaystyle{\mathbold{C}}^{(\ell)}$
$\displaystyle\leq{{\mathcal{J}}}_{z}(\ell).$ (124)

Furthermore, the assumption that $\mathbold{\gamma}\in\mathbb{R}^{{\tt E}}$ is
a $(s,\delta,c)$-potential vector with respect to $\mathbold{\xi}$ and
${\mathcal{P}}$, together with (123) imply that

$\displaystyle{{\mathcal{J}}}_{z}(\ell)$
$\displaystyle\leq\textstyle\frac{c}{{\mathbold{D}}^{\circ\frac{1}{s}}(r,r)}\sum^{d_{z}}_{j=1}{{\mathcal{J}}}_{x_{j}}(\ell-1).$
(125)

The same assumption about $\mathbold{\gamma}$ implies that for any $0<m<\ell$
we have that

$\displaystyle\left[{{\mathcal{J}}}_{z}(\ell-m)\right]^{s}$
$\displaystyle\leq\textstyle\delta\times\sum^{d_{z}}_{j=1}\left[{{\mathcal{J}}}_{x_{j}}(\ell-m-1)\right]^{s}.$
(126)

Suppose that $k_{i}$ is the $i$-th child of the root, while the subtree
$T_{i}$ includes vertex $k_{i}$ and all of its decedents. Then, from (126) and
(122) it is elementary to get the that

$\displaystyle\left[{{\mathcal{J}}}_{k_{i}}(\ell-1)\right]^{s}$
$\displaystyle\textstyle\leq\left(\delta\right)^{\ell-1}\times\sum_{u\in
V_{{\mathcal{P}}}}|{\tt
A}_{i,\ell-1}(u)|\cdot\left[{\mathbold{D}}^{\circ\frac{1}{s}}(u,u)\right]^{s},$

where, recall that, ${\tt A}_{i,\ell-1}(u)$ is the set of copies of vertex $u$
in the subtree $T_{i}$ that are at distance $\ell-1$ from the root of $T_{i}$.
Plugging the above into (125) yields

$\displaystyle{{\mathcal{J}}}_{z}(\ell)$
$\displaystyle\textstyle\leq\frac{c}{{\mathbold{D}}^{\circ\frac{1}{s}}(r,r)}\sum^{d_{z}}_{i=1}\left(\delta^{\ell-1}\sum_{u\in
V_{{\mathcal{P}}}}|{\tt
A}_{i,\ell-1}(u)|\cdot\left[{\mathbold{D}}^{\circ\frac{1}{s}}(u,u)\right]^{s}\right)^{\frac{1}{s}}.$

Combining the above with (124) and (121) we get that

$\displaystyle\sum_{u\in V_{{\mathcal{P}}}}\left|{\mathbold{C}}(r,u)\right|$
$\displaystyle\textstyle\leq
1+\frac{c}{{\mathbold{D}}^{\circ\frac{1}{s}}(r,r)}\sum^{d_{z}}_{i=1}\sum_{\ell\geq
1}\left(\delta^{\ell-1}\sum_{u\in V_{{\mathcal{P}}}}|{\tt
A}_{i,\ell-1}(u)|\cdot\left({\mathbold{D}}^{\circ\frac{1}{s}}(u,u)\right)^{s}\right)^{\frac{1}{s}}$
$\displaystyle\textstyle=1+\frac{c}{{\mathbold{D}}^{\circ\frac{1}{s}}(r,r)}\sum^{d_{z}}_{i=1}\sum_{\ell\geq
0}\left(\delta^{\ell}\sum_{u\in V_{{\mathcal{P}}}}|{\tt
A}_{i,\ell}(u)|\cdot\left({\mathbold{D}}^{\circ\frac{1}{s}}(u,u)\right)^{s}\right)^{\frac{1}{s}},$

where, in the last equality we change variable. From the above and the
definition of walk-vector
$\mathbold{q}=\mathbold{q}({\mathcal{P}},{\mathbold{D}}^{\circ\frac{1}{s}},s,\delta,c)$,
it is immediate that (118) is true. The theorem follows. $\Box$

###  14.3. Proof of Theorem 8.6

Note that (61) follows immediately from (60) since, by definition, both
$\mathbold{q}_{{\mathcal{S}}}$ and $\mathbold{q}_{{\mathcal{P}}}$ have
positive entries. The rest of the proof focuses on proving (60).

Firstly, we note for any $r\in V_{{\mathcal{S}}}\subseteq V_{{\mathcal{P}}}$,
we have that that ${T}_{{\mathcal{S}}}(r)$ is a subtree of
${T}_{{\mathcal{P}}}(r)$. This follows from Lemma 6.1.

Suppose that the root of ${T}_{{\mathcal{S}}}(r)$ has degree
$d_{{\mathcal{S}}}$, while let $T_{{\mathcal{S}},i}$ be the subtree that is
induced by the $i$-th child of the root of ${T}_{{\mathcal{S}}}(r)$ and its
descendants. Also, for $\ell\geq 0$ and any vertex $v\in V_{{\mathcal{S}}}$,
let ${\tt A}_{{\mathcal{S}},i,\ell}(v)$ be the set of copies of vertex $v$ in
the subtree $T_{{\mathcal{S}},i}$ which is at distance $\ell$ from the root of
$T_{{\mathcal{S}},i}$.

Following the definition of walk-vector, i.e., Definition 8.4, we have that

$\displaystyle\mathbold{q}_{{\mathcal{S}}}(r)$
$\displaystyle\textstyle=1+\frac{c}{{\mathbold{D}}(r,r)}\times\sum^{d_{{\mathcal{S}}}}_{i=1}\sum_{\ell\geq
0}\left(\delta^{\ell}\cdot\sum_{w\in V_{{\mathcal{S}}}}|{\tt
A}_{{\mathcal{S}},i,\ell}(w)|\cdot({\mathbold{D}}(w,w))^{s}\right)^{\frac{1}{s}}.$
(127)

Suppose that the root of ${T}_{{\mathcal{P}}}(r)$ has degree
$d_{{\mathcal{P}}}$. In the same way as above, we define the subtrees
$T_{{\mathcal{P}},i}$ and the set of copies ${\tt
A}_{{\mathcal{P}},i,\ell}(v)$ for every $i\in[d_{{\mathcal{P}}}]$ and
$\ell\geq 0$. We also have that

$\displaystyle\mathbold{q}_{{\mathcal{P}}}(r)$
$\displaystyle\textstyle=1+\frac{c}{{\mathbold{D}}(r,r)}\times\sum^{d_{{\mathcal{P}}}}_{i=1}\sum_{\ell\geq
0}\left(\delta^{\ell}\cdot\sum_{w\in V_{{\mathcal{P}}}}|{\tt
A}_{{\mathcal{P}},i,\ell}(w)|\cdot({\mathbold{D}}(w,w))^{s}\right)^{\frac{1}{s}}.$
(128)

Note that, since $\delta,{\mathbold{D}}(w,w)>0$, the summands in both (127)
and (128) are non-negative quantities.

The theorem follows by observing that $d_{{\mathcal{S}}}\leq
d_{{\mathcal{P}}}$, $V_{{\mathcal{S}}}\subseteq V_{{\mathcal{P}}}$ and $|{\tt
A}_{{\mathcal{S}},i,\ell}(w)|\leq|{\tt A}_{{\mathcal{P}},i,\ell}(w)|$, for any
$w\in V_{{\mathcal{S}}}$, $i\in[d_{{\mathcal{S}}}]$ and $\ell\geq 0$. This is
due to the fact that ${T}_{{\mathcal{S}}}(r)$ is a subtree of
${T}_{{\mathcal{P}}}(r)$. The theorem follows. $\Box$

## References

  * [1] 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.
  * [2] I. Bezáková, A. Galanis, L. A. Goldberg, D. l Stefankovic: Fast sampling via spectral independence beyond bounded-degree graphs. CoRR abs/2111.04066, 2021.
  * [3] 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.
  * [4] 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.
  * [5] 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.
  * [6] 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.
  * [7] 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.
  * [8] 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.
  * [9] P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of Markov chains. The Annals of Applied Probability, pp. 36–61, 1991.
  * [10] 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.
  * [11] 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.
  * [12] 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.
  * [13] 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.
  * [14] C. D. Godsil. Algebraic Combinatorics. Chapman and Hall Math. Series, Chapman & Hall, New York, 1993. MR 1220704. Zbl 0784.05001.
  * [15] 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.
  * [16] T. 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.
  * [17] R. A. Horn and C. R. Johnson. Matrix Analysis, 2nd Edition. Cambridge University Press, New York, 2013.
  * [18] 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.
  * [19] F. P. Kelly. Stochastic Models of Computer Communication Systems. Journal of the Royal Statistical Society. Series B (Methodological), 47(3):379-395, 1985.
  * [20] M. Kempton. High Dimensional Spectral Graph Theory and Non-backtracking Random Walks on Graphs. PhD Thesis, University of California, San Diego, 2015.
  * [21] L. Li, P. Lu, and Y. Yin. Correlation Decay Up to Uniqueness in Spin Systems. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 67–84, 2013.
  * [22] C. D. Meyer. Matrix analysis and applied linear algebra. Society for Industrial and Applied Mathematics (SIAM), 2000.
  * [23] A. W. Marcus, D. A. Spielman and N. Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Annals of Mathematics 182 (2015), pp 307–325.
  * [24] A. Sinclair and M. Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82, pp. 93 – 133, 1989.
  * [25] 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.
  * [26] 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.
  * [27] 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.
  * [28] E. Vigoda. A Note on the Glauber Dynamics for Sampling Independent Sets. Electronic Journal of Combinatorics, 8(1): Research paper 8, 2001.
  * [29] 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 Basics in Algebra

###  A.1. Matrix and Vector Norms

For what follows, we let $N,M$ be positive integers. Furthermore, we denote
with $\mathbb{R}$ the set of real numbers, while $\mathbb{C}$ is the set of
complex numbers.

For $p\geq 1$, the $p$-norm of the vector ${\bf x}\in\mathbb{C}^{N}$, denoted
as $\left|\left|{\bf x}\right|\right|_{p}$, is defined such that

$\displaystyle\left|\left|{\bf x}\right|\right|_{p}$
$\displaystyle=\textstyle\left(\sum^{N}_{i=1}|{\bf x}_{i}|^{p}\right)^{1/p}.$

A matrix norms is a function $\left|\left|\cdot\right|\right|$ from the set of
all complex matrices (of all finite orders) into $\mathbb{R}$ that satisfies
the following properties:

P.1:

$\left|\left|{\bf A}\right|\right|\geq 0$, while $\left|\left|{\bf
A}\right|\right|=0\Leftrightarrow{\bf A}={\bf 0}$.

P.2:

$\left|\left|\alpha{\bf A}\right|\right|=|\alpha|\left|\left|{\bf
A}\right|\right|$, for any scalar $\alpha$.

P.3:

$\left|\left|{\bf A}+{\bf B}\right|\right|\leq\left|\left|{\bf
A}\right|\right|+\left|\left|{\bf B}\right|\right|$, for matrices of the same
size.

P.4:

$\left|\left|{\bf A}{\bf B}\right|\right|\leq\left|\left|{\bf
A}\right|\right|\cdot\left|\left|{\bf B}\right|\right|$, for all conformable
matrices.

For each norm $\left|\left|\cdot\right|\right|$ on $\mathbb{R}^{r}$, where
$r\in\\{N,M\\}$ there is a matrix norm that is “induced” by
$\left|\left|\cdot\right|\right|$ on $\mathbb{R}^{N\times M}$ by setting

$\displaystyle\left|\left|{\bf A}\right|\right|$
$\displaystyle=\max_{\left|\left|{\bf x}\right|\right|=1}\left|\left|{\bf
A}{\bf x}\right|\right|$ for ${\bf A}\in\mathbb{R}^{N\times M}$ and ${\bf
x}\in\mathbb{R}^{M}$.

It is standard that $\left|\left|{\bf A}\right|\right|_{\infty}$ corresponds
to the maximum absolute row sum in ${\bf A}$, while $\left|\left|{\bf
A}\right|\right|_{1}$ corresponds to the maximum absolute column sum, i.e.,

$\displaystyle\left|\left|{\bf A}\right|\right|_{\infty}$
$\displaystyle=\max_{i}\\{{\textstyle\sum_{j}|{\bf A}_{i,j}|}\\}$ and
$\displaystyle\left|\left|{\bf A}\right|\right|_{1}$
$\displaystyle=\max_{j}\\{{\textstyle\sum_{i}|{\bf A}_{i,j}|}\\}.$

###  A.2. Perron-Frobenius Theorem

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

We can associate ${\mathbold{M}}$ with the directed graph $G_{{\mathbold{M}}}$
on the vertex set $[N]$, while the edge $(i,j)$ is in $G_{{\mathbold{M}}}$ iff
${\mathbold{M}}_{i,j}>0$. Then, ${\mathbold{M}}$ is irreducible, if the
resulting graph $G_{{\mathbold{M}}}$ 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 A.1 (Perron-Frobenius Theorem).

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

  1. (1)

${\rho}({{\mathbold A}})>0$

  2. (2)

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

  3. (3)

there is a unique real vector ${\bf x}=({\bf x}_{1},\ldots,{\bf x}_{N})$ such
that ${{\mathbold A}}\cdot{\bf x}={\rho}({{\mathbold A}}){\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}{{\mathbold A}}={\rho}({{\mathbold A}}){\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}$.

##  Appendix B Basic Proporties of
${{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}$

Consider the graph $G=(V,E)$. For integer $k\geq 1$ and
$\zeta\in\mathbb{R}_{\geq 0}$, consider the walk matrix
${{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}$, where
${\mathbold{\psi}}\in\mathbb{R}^{{\tt E}_{\textrm{NB-$k$}}}_{\geq 0}$ is such
that ${\mathbold{\psi}}(e)=\zeta$, for all $e\in{\tt E}_{\textrm{NB-$k$}}$.
That is, ${{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}$ is induced by
all the non-backpacking walks in $G$ which are of length $\leq k$, while for
every walk-tree ${T}_{\textrm{NB-$k$}}(r)$ every edge $e$ has weight
${\mathbold{\psi}}(e)=\zeta$. Recall from Lemma 6.3 that we have

$\displaystyle{{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}$
$\displaystyle=\textstyle{\mathbold{I}}+{\bf
K}\cdot\left(\sum^{k-1}_{\ell=0}\zeta^{\ell+1}\cdot\mathbold{H}^{\ell}_{G}\right)\cdot{\bf
C},$ (129)

where $\mathbold{H}_{G}$ is the non-backtracking matrix of $G$, while ${\bf
K}$, ${\bf C}$ are $V\times\overrightarrow{E}$ and $\overrightarrow{E}\times
V$ matrices, respectively, such that for any $v\in V$ and for any
$(x,z)\in\overrightarrow{E}$ we have

$\displaystyle{\bf K}(v,(x,z))$ $\displaystyle={\bf 1}\\{x=v\\}$ and
$\displaystyle{\bf C}((x,z),v)$ $\displaystyle={\bf 1}\\{z=v\\}$

In what follows, we present we show that
${{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}$ is symmetric.

######  Lemma B.1.

For any $k\geq 0$ and any $\zeta>0$, the matrix
${{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}$ is symmetric.

###### Proof.

From the definition of ${{\mathbold{W}}}_{\textrm{NB-$k$},{\mathbold{\psi}}}$
in (129), we note that, since the identity matrix ${\mathbold{I}}$ is
symmetric, the lemma follows by showing that for any $\ell\geq 0$ the matrix

$\displaystyle{\mathbold{X}}$ $\displaystyle=\textstyle{\bf
K}\cdot\mathbold{H}^{\ell}_{G}\cdot{\bf C},$

is symmetric. Note that ${\mathbold{X}}$ is a $V\times V$ matrix.

Elementary calculations, imply that for any $u,w\in V$, different with each
other, we have that

$\displaystyle{\mathbold{X}}(u,w)$ $\displaystyle={\textstyle\sum_{z\in
V}\sum_{y\in V}}\mathbold{H}^{\ell}_{(u,z),(y,w)}.$

From the PT invariance of $\mathbold{H}^{\ell}$, i.e., (26), we get the
following:

$\displaystyle{\mathbold{X}}(u,w)$
$\displaystyle={\textstyle\sum_{z}\sum_{y}}\mathbold{H}^{\ell}_{(u,z),(y,w)}={\textstyle\sum_{z}\sum_{y}}\mathbold{H}^{\ell}_{(w,y),(z,u)}={\mathbold{X}}(w,u).$

It is in the second equality that we use the PT invariance of
$(\mathbold{H}_{G})^{\ell}$.

The above implies that ${\mathbold{X}}$ is a symmetric matrix. The lemma
follows. ∎

##  Appendix C Results for Unbounded spectral radius

In this section we present results which are analogous to Theorems 2.1 and 2.2
for graphs whose adjacency matrix ${\bf A}_{G}$ has unbounded spectral radius,
i.e., ${\rho}({\bf A}_{G})$ grows with the size of the graph $n$. We start
with the Ising model.

######  Theorem C.1.

For any $\delta\in(0,1)$ and for ${\rho}_{G}>1$, consider the graph $G=(V,E)$
whose adjacency matrix ${\bf A}_{G}$ has spectral radius ${\rho}_{G}$. Also,
let $\mu_{G}$ be the Ising model on $G$ with zero external field and parameter
$\beta\in{\mathbb{M}_{\rm Ising}}({\rho}_{G},\delta)$.

If ${\rho}_{G}$ is unbounded, there is a constant $C=C(\delta)$ such that the
mixing time of the Glauber dynamics on $\mu_{G}$ is at most
$Cn^{1+\frac{1}{\delta}}$.

Note that there is a discrepancy between the two mixing times we get from
Theorems 2.1 and C.1. This has to do with how we use spectral independence,
i.e., once this has been established, to bound the mixing time of Glauber
dynamics. In that respect, we make a direct use of results from [5, 6] and
hence, the discrepancy comes from the fact that these two papers derive
different bounds on the mixing time. In the related literature there is also
the work in [7] which can be considered for the unbounded case. However, it
seems that the result in [7] requires from the Gibbs distribution to satisfy a
strong condition called Gibbs uniqueness. The range of the parameters we
consider for the Gibbs distribution in Theorems C.1 and 2.1 is beyond this
region.

Theorem 2.1 improves on results in [16] for the Ising model by allowing a
wider rage for $\beta$. For ${\rho}_{G}=\omega(1)$, the range of $\beta$ is
wider than that in [16] but the increase is with regard to smaller order
terms. Note that the mixing time there is $O(n\log n)$.

###### Proof of Theorem C.1.

The proof of Theorem C.1 is almost identical to that of Theorem 2.1.
Specifically, using Lemma 9.1 and Theorem 5.2 in the same way as in the proof
of Theorem 2.1 we get the following: for $\Lambda\subseteq V$ and
$\tau\in\\{\pm 1\\}^{\Lambda}$, the pairwise influence matrix
${{\mathcal{I}}}^{\Lambda,\tau}_{G}$, induced by $\mu_{G}$, satisfies that

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

The theorem follows as a corollary from (130), Theorem 4.3 and (19). ∎

We proceed with the Hard-core model on a graph with unbounded spectral radius.
We prove the following result.

######  Theorem C.2.

For any $\epsilon\in(0,1)$, ${\Delta}\geq 2$ and ${\rho}_{G}\geq 2$, consider
the graph $G=(V,E)$ of maxim degree ${\Delta}$, whose adjacency matrix ${\bf
A}_{G}$ has spectral radius ${\rho}_{G}$. Also, let $\mu_{G}$ be the Hard-core
model on $G$ with fugacity $\lambda\leq(1-\epsilon){\lambda_{c}}({\rho}_{G})$.

If ${\rho}_{G}$ is unbounded, there are constants $C=C(\epsilon)$ and
$C^{\prime}=C^{\prime}(\epsilon)$ such that the mixing time of the Glauber
dynamics on $\mu_{G}$ is at most
$Cn^{2+C^{\prime}\sqrt{{\Delta}/{\rho}_{G}}}$.

Note that the above result implies a polynomial bound for the mixing time only
for the case where the ratio $\sqrt{{\Delta}/{\rho}_{G}}$ is bounded.

The above improves on [16] by allowing a wider rage for $\lambda$. The
improvement is the same as in the bounded case, i.e., get an extra factor $e$.
Note, though, the extra condition that the ratio of maximum degree ${\Delta}$
over ${\rho}_{G}({\bf A}_{G})$ must be bounded.

###### Proof of Theorem C.2.

The proof of Theorem C.2 is almost identical to that of Theorem 2.2.
Specifically, using Theorem 10.1 we get the following: There is a constant
$z>0$ which depend on $\epsilon$ such that for any $\Lambda\subseteq V$ and
$\tau\in\\{\pm 1\\}^{\Lambda}$ we have that

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

The theorem follows from the above inequality, Theorem 4.3 and (19). ∎

##  Appendix D Rapid mixing bound for General Gibbs Distributions

Note that Theorems 5.2 and 5.5 do not provide bounds for the spectral radius
of the influence matrix only for the Ising model and the Hard-core model. They
are general results and apply to any Gibbs distribution on $G$. In that
respect, it might be interesting to write the corresponding bounds we get from
these two theorems on the mixing time of Glauber dynamics on a general two-
spin Gibbs distribution.

Consider a graph $G=(V,E)$ and assume that ${\rho}({\bf A}_{G})$ is bounded.
Recall that this assumption implies that the maximum degree ${\Delta}$ is also
bounded.

For what follows, we need to introduce few useful concepts from [6]. For
$S\subset V$, let the Hamming graph ${\mathcal{H}}_{S}$ be the graph whose
vertices correspond to the configurations $\\{\pm 1\\}^{S}$, while two
configurations are adjacent iff they differ at the assignment of a single
vertex, i.e., their Hamming distance is one. Similarly, any subset
$\Omega_{0}\subseteq\\{\pm 1\\}^{S}$ is considered to be connected if the
subgraph induced by $\Omega_{0}$ is connected.

A distribution $\mu$ over $\\{\pm 1\\}^{V}$ is considered to be totally
connected if for every nonempty $\Lambda\subset V$ and every boundary
condition $\tau$ at $\Lambda$ the set of configurations in the support of
$\mu(\cdot\ |\ \Lambda,\tau)$ is connected.

We need to remark here that all Gibbs distribution with soft-constraints such
as the Ising model are totally connected in a trivial way. The same holds for
the Hard-core model and this follows with standard arguments.

######  Definition D.1.

For some number $b\geq 0$, we say that a distribution $\mu$ over $\\{\pm
1\\}^{V}$ is $b$-marginally bounded if for every $\Lambda\subset V$ and any
configuration $\tau$ at $\Lambda$ we have the following: for any
$V\setminus\Lambda$ and for any $x\in\\{\pm 1\\}$ which is in the support of
$\mu_{u}(\cdot\ |\ \Lambda,\tau)$, we have that

$\displaystyle\mu_{u}(x\ |\ \Lambda,\tau)\geq b.$

The following result is a part of Theorem 1.9 from [6] (arxiv version). This
is one of the results in the literature that improves on Theorem 4.2.

######  Theorem D.2 ([6]).

Let the integer ${\Delta}\geq 3$ and $b,\eta\in\mathbb{R}_{>0}$. Consider
$G=(V,E)$ a graph with $n$ vertices and maximum degree ${\Delta}$. Also, let
$\mu$ be a totally connected Gibbs distribution on $\\{\pm 1\\}^{V}$.

If $\mu$ is both $b$-marginally bounded and $\eta$-spectrally independent,
then there are constants $C_{1},C_{2}>0$ such the Glauber dynamics for $\mu$
exhibits mixing time

$\displaystyle T_{\rm mix}$
$\displaystyle\leq\left(\frac{{\Delta}}{b}\right)^{C_{1}\left(\frac{\eta}{b^{2}}+1\right)}\times
C_{2}\left(n\log n\right).$

We combine Theorems 5.2 and 5.5 with the above to get the following rapid
mixing results for the Glauber dynamics on ageneral Gibbs distributions on $G$
with bounded ${\rho}({\bf A}_{G})$.

######  Theorem D.3 ($\delta$-contraction).

Let the integer ${\Delta}\geq 3$, $b,\epsilon\in(0,1]$, ${\rho}_{G}>1$ and
$\beta,\gamma,\lambda\in\mathbb{R}$ such that $0\leq\beta\leq\gamma$,
$\gamma>0$ and $\lambda>0$.

Consider $G=(V,E)$ a graph with $n$ vertices and maximum degree at most
${\Delta}$, while ${\bf A}_{G}$ is of spectral radius ${\rho}_{G}$. Also, let
$\mu$ be a totally connected Gibbs distribution on $\\{\pm 1\\}^{V}$ specified
by the parameters $\beta,\gamma$ and $\lambda$ as in (1).

Setting $\delta=\frac{1-\epsilon}{{\rho}_{G}}$, suppose that $\mu$ is
$b$-marginally bounded while the set of functions
$\\{H_{d}\\}_{d\in[{\Delta}]}$ specified with respect to
$(\beta,\gamma,\lambda)$ exhibits $\delta$-contraction.

There are constants $C_{1},C_{2}>0$ such the Glauber dynamics on $\mu$
exhibits mixing time $T_{\rm mix}$ such that

$\displaystyle T_{\rm mix}$
$\displaystyle=\left(\frac{{\Delta}}{b}\right)^{C_{1}\left(\frac{1}{\epsilon
b^{2}}+1\right)}\times C_{2}\left(n\log n\right).$

Theorem D.3 is straightforward from Theorems D.2 and 5.2. For this reason, we
omit its proof.

######  Theorem D.4 ($(s,\delta,c)$-potential function).

Let the integer ${\Delta}\geq 3$, $b,\epsilon\in(0,1]$, $\zeta>0$,
${\rho}_{G}>1$ and $\beta,\gamma,\lambda\in\mathbb{R}$ such that
$0\leq\beta\leq\gamma$, $\gamma>0$ and $\lambda>0$.

Consider $G=(V,E)$ a graph with $n$ vertices and maximum degree at most
${\Delta}$, while ${\bf A}_{G}$ is of spectral radius ${\rho}_{G}$. Also, let
$\mu$ be a totally connected Gibbs distribution on $\\{\pm 1\\}^{V}$ specified
by the parameters $\beta,\gamma$ and $\lambda$ as in (1).

Setting $\delta=\frac{1-\epsilon}{{\rho}_{G}}$ and
$c=\frac{\zeta}{{\rho}_{G}}$, suppose that $\mu$ is $b$-marginally bounded,
while there is a $(s,\delta,c)$-potential function ${\Psi}$ with respect to
$(\beta,\gamma,\lambda)$.

There is a constant $C>0$ such the Glauber dynamics on $\mu$ exhibits mixing
time $T_{\rm mix}$ such that

$\displaystyle T_{\rm mix}$
$\displaystyle=\left(\frac{{\Delta}}{b}\right)^{C\left(\frac{\eta}{b^{2}}+1\right)}\times\left(n\log
n\right),$

where
$\eta=1+\zeta\cdot(1-(1-\epsilon)^{s})^{-1}\cdot\left({{\Delta}}/{{\rho}_{G}}\right)^{1-\frac{1}{s}}$.

Theorem D.4 is straightforward from Theorems D.2 and 5.5. For this reason, we
omit its proof.