the other hand, Lemma 5.15 implies that
$\lvert\mathcal{S}\rvert\leqslant\alpha n$, where
$\alpha=\exp(-c\varepsilon^{3}d)$, and we trivially have
$\lvert\mathcal{T}\rvert\leqslant n$.

Hence, we will verify the conditions for $\eta=\frac{2d}{n}$ and
$m^{\prime}=n$. Plugging these parameters in, we need $\delta$ to satisfy

$\displaystyle\frac{2d}{n}\cdot\sum_{C\in\mathcal{S}}\lvert C\rvert^{2}$
$\displaystyle<\delta$ $\displaystyle 2\cdot\left(\frac{2d}{n}\right)^{2}\cdot
n\cdot\sum_{C\in\mathcal{S}}\lvert C\rvert^{2}$ $\displaystyle<\delta.$

Applying Lemma 5.15 again, we see that the above inequalities are satisfied
for $\delta>8\alpha d^{2}$. Hence, we pick $\delta=8\alpha d^{2}$, and we
easily compute $1-\frac{\delta}{\eta n}=1-4\alpha d=1-o_{d}(1)$.

Turning now to $\theta$, we need $\theta$ to satisfy

$\max_{C\in\mathcal{S}}\lvert C\rvert\leqslant n^{\theta}.$

Lemma 5.16 implies that we can take
$\theta=\frac{c\log(d(1+\varepsilon))}{\varepsilon^{3}d}=o_{d}(1)$ for some
positive constant $c$. Next, due to Theorem 4.8, we can take
$\zeta=n^{-\theta-o_{n}(1)}=n^{-o_{d}(1)}$.

Finally, to plug these parameters into Lemma 5.14, we have

$\exp(-O(\eta\cdot n^{2\theta}))=1-O\left(\frac{d}{n^{1-2\theta}}\right)$

By picking the constant factor in $\varepsilon$ large enough, we can ensure
that $\theta$ is sufficiently small so that the above term is $1-o_{n}(1)$. ∎

Clearly, Lemma 5.17 directly proves Theorem 5.3.

###  5.2 Entropy conservation for centered Ising models

In this section, we prove Theorem 5.2, which establishes entropy conservation
for centered Ising models on sparse SBMs. Set $B=\bm{G}_{1}$ and
$H=\bm{G}_{2}$, with this being a $(\Delta,D)$-decomposition as guaranteed by
Theorem 4.9. As before, we will use Lemma 3.14 with

$M_{1}=(1-t)J_{B}+\theta I_{B}+\frac{\rho}{\Delta}I_{H}\quad\text{ and
}M_{2}=J_{R},$

where we can take $\theta=\eta+2\beta(1+\varepsilon)$ due to Lemma 3.29 and
$\rho$ as in the proof of Theorem 4.6.

Moreover, since $J_{B}$ is only supported on the bulk, one can follow the
proof of Theorem 4.6 to argue that to bound
$\bm{\mathrm{Cov}}(\mu_{M_{1}+M_{2},h})$, one only needs to bound covariances
of Ising models on $M_{2}$. Namely, it suffices to establish the following PSD
upper bounds for arbitrary external field $h^{\prime}$:

$\displaystyle\left\|\bm{\mathrm{Cov}}\left(\mu_{M_{2},h^{\prime}}\right)_{B}\right\|$
$\displaystyle\leqslant O(1)$
$\displaystyle\left\|\bm{\mathrm{Cov}}(\mu_{M_{2},h^{\prime}})_{H}\right\|$
$\displaystyle\leqslant O\left(\frac{\Delta}{D}\right).$

The main difficulty stems from the fact that $M_{2}=J_{R}$ has support outside
$H$; it is now supported on the complete graph on $H$, as well as the edges
between $B$ and $H$.

To analyze $\bm{\mathrm{Cov}}(\mu_{M_{2},h})$, the high level strategy will be
to use Observation 3.9 and transfer over to the case of having interactions
purely supported on $H$. To do so, we will prove an optimal Poincaré
inequality for a Markov chain where the states are the connected components of
$H$. Let us illustrate this argument informally; the subsequent lemmas will
justify why we can execute these steps.

Recall that $\mathsf{cc}(H)$ denotes the set of connected components of $H$,
and let $C\in\mathsf{cc}(H)$ be an arbitrary component. By a slight abuse of
notation, let $M_{C}=(M_{H})_{C}$ denote the restriction of $M_{H}$ to $C$ and
$E_{C}=(E_{H})_{C}$ denote the restriction for the error in the near-forest.
For any $v\in\mathbb{R}^{n}$ supported on $S\subseteq[n]$, we have

$\displaystyle\operatorname*{\bm{\mathrm{Var}}}_{x\sim\mu_{M_{2},h^{\prime}}}(\langle
v,x\rangle)$ $\displaystyle\leqslant
O(1)\sum_{C\in\mathsf{cc}(H)}\bm{\mathrm{E}}_{x_{-C}}\operatorname*{\bm{\mathrm{Var}}}_{x\sim\mu_{M_{C}+E_{C},h(x_{-C})}}(\langle
v_{C},x_{C}\rangle)$ (Poincaré) $\displaystyle\leqslant
O(1)\sum_{C\in\mathsf{cc}(H)}\bm{\mathrm{E}}_{x_{-C}}\operatorname*{\bm{\mathrm{Var}}}_{x\sim\mu_{M_{C},h(x_{-C})}}(\langle
v_{C},x_{C}\rangle)$ (Perturbation) $\displaystyle\leqslant
O(1)\sum_{C\in\mathsf{cc}(H)}\lVert
v_{C}\rVert^{2}\cdot\bm{\mathrm{E}}_{x_{-C}}\left[\lVert\bm{\mathrm{Cov}}(\mu_{M_{C},h(x_{-C})})_{S}\rVert\right]\,.$
($v$ supported on $S$)

By selecting $S=B$ and $S=H$, we can transfer over the covariance bounds
computed for near-forest Ising models in Lemma 4.5 to finish off the proof.

For the remainder of this section, we will justify the above steps and
complete the proof of Theorem 5.2.

Establishing an optimal Poincaré inequality. Let us first recall the
definition of the Poincaré inequality on product domains.

######  Definition 5.18.

Suppose that $\nu$ is a distribution on a product domain
$\mathcal{P}=\mathcal{P}_{1}\times\cdots\times\mathcal{P}_{k}$, and let
$C_{\mathrm{PI}}(\nu)$ be the Poincaré constant for Glauber dynamics on $\nu$.
Then for any $f:\mathcal{P}\to\mathbb{R}$, we have

$\bm{\mathrm{Var}}_{\nu}(f)\leqslant\frac{1}{k\cdot
C_{\mathrm{PI}}(\nu)}\sum_{i\in[k]}\bm{\mathrm{E}}_{y_{-i}}\bm{\mathrm{Var}}_{y_{i}|y_{-i}}(f).$

We claim that the block Glauber dynamics studied in Section 5.1 has an optimal
Poincaré constant. In particular, for us $k=m+m^{\prime}$ is the total number
of connected components of $H$ (including isolated vertices). Indeed, due to
Lemmas 5.17 and 5.11, we have

$\displaystyle\lVert\mathcal{R}_{\nu}\rVert$ $\displaystyle\leqslant 8\alpha
d^{2}+\sqrt{8\alpha d^{2}}$
$\displaystyle\leqslant\exp(-\Omega(\varepsilon^{3}d)).$ (Lemma 5.15)

Hence, by [Hay06] this implies an optimal mixing time bound for the block
dynamics, and in turn an $\Omega(\frac{1}{k})$ bound on
$C_{\mathrm{PI}}(\nu)$.

Perturbation. Next, we justify the transfer from $\mu_{M_{C}+E_{C},h}$ to
$\mu_{M_{C},h}$, thereby removing the pesky additional weak interactions
$E_{C}$. To accomplish this, we will use the simple perturbation bound Lemma
3.8. Indeed, we already proved such a density bound for perturbed Ising models
in Lemma 5.12. Plugging in the explicit parameters for SBMs, as we did in the
proof of Lemma 5.17, we see that we can take $c=1+o_{n}(1)$ in Lemma 3.8. In
other words, we barely incur any loss transferring to $M_{C}$.

With the above lemmas in hand, we can finish off the proof of the theorem.

###### Proof of Theorem 5.2.

By Observation 3.9, if $v\in\mathbb{R}^{n}$ is a unit norm vector supported on
$S\subseteq[n]$, then there is a positive constant $c>0$ such that

$\displaystyle\operatorname*{\bm{\mathrm{Var}}}_{x\sim\mu_{M_{R},h^{\prime}}}(\langle
v,x\rangle)$ $\displaystyle\leqslant
c\sum_{C\in\mathsf{cc}(H)}\bm{\mathrm{E}}_{x_{-C}}\operatorname*{\bm{\mathrm{Var}}}_{x\sim\mu_{M_{C}+E_{C},h(x_{-C})}}(\langle
v_{C},x_{C}\rangle)$ (Definition 5.18) $\displaystyle\leqslant
c(1+o_{n}(1))\sum_{C\in\mathsf{cc}(H)}\bm{\mathrm{E}}_{x_{-C}}\operatorname*{\bm{\mathrm{Var}}}_{x\sim\mu_{M_{C},h(x_{-C})}}(\langle
v_{C},x_{C}\rangle)$ (Lemma 3.8) $\displaystyle\leqslant
c(1+o_{n}(1))\sum_{C\in\mathsf{cc}(H)}\lVert
v_{C}\rVert^{2}\bm{\mathrm{E}}_{x_{-C}}\left[\lVert\bm{\mathrm{Cov}}(\mu_{M_{C},h(x_{-C})})_{S}\rVert\right]\,.$
($v$ supported on $S$)

Recall that $M_{H}=\frac{\beta}{\sqrt{d}}(\overline{A}_{H}\circ A_{H})$. Since
the centering interaction is $O(\frac{d}{n})$, it follows that the
interactions are in
$\left[-\frac{\beta}{\sqrt{d}},\frac{\beta}{\sqrt{d}}\right]=\left[-\frac{\beta\sqrt{1+\varepsilon}}{\sqrt{d(1+\varepsilon)}},\frac{\beta\sqrt{1+\varepsilon}}{\sqrt{d(1+\varepsilon)}}\right]$,
so we can apply Lemma 4.5 with $\gamma=\beta\sqrt{1+\varepsilon}$.

Taking $S=B$ and applying Lemma 4.5 uniformly on each component $C$ yields

$\displaystyle\lVert\bm{\mathrm{Cov}}(\mu_{M_{R},h^{\prime}})_{B}\rVert\leqslant
c(1+o(1))\cdot\left(\frac{e^{2\beta/\sqrt{d}}}{(1-\beta\sqrt{1+\varepsilon})^{2}}\right),$

and for $S=H$ we obtain that

$\displaystyle\lVert\bm{\mathrm{Cov}}(\mu_{M_{R},h^{\prime}})_{H}\rVert\leqslant
c(1+o(1))\cdot\left(\frac{e^{2\beta/\sqrt{d}}}{(1-\beta\sqrt{1+\varepsilon})^{2}}\right)\cdot\frac{\Delta}{D}.$

By following the same calculations as in Theorem 4.1, the upshot is that for
sufficiently small constant $\beta>0$, we have

$\displaystyle\bm{\mathrm{Cov}}(\mu_{(1-t)J_{B}+J_{R},h})\preceq
O\left(\frac{\Delta}{D}\right).$

Finally, as Theorem 4.9 ensures that $\Delta=o(\log n)$, the proof is
completed. ∎

##  6 Near-forest decomposition for stochastic block models

In this section, we prove Theorem 4.9, a statement about the existence of a
near-forest decomposition for sparse random graphs. See 4.9

######  Notation ($\varepsilon,\,d,\,\bm{G}$).

Throughout this section, let $\varepsilon$ and $d$ be as in the statement of
Theorem 4.9, and let $\bm{G}\sim\mathrm{SBM}(n,d,\lambda)$.

We begin the proof by first defining the construction of $\bm{G}_{1}$ and
$\bm{G}_{2}$.

######  Definition 6.1 (Excision of a graph).

For a graph $G$, and for each vertex $v\in V(G)$, define $N_{\ell}(v)$ to be
the set of vertices at distance exactly $\ell$ from $v$ and $B_{\ell}(v)$ to
be the induced subgraph on $G$ on those vertices within distance $\ell$ of
$v$. We say that $v$ is $\ell$-heavy if
$|B_{\ell}(v)|>(d(1+\varepsilon))^{\ell}$, and conversely that $v$ is
$\ell$-light if $|B_{\ell}(v)|\leqslant(d(1+\varepsilon))^{\ell}$, and set

$\ell(v)=\min\\{\ell\geqslant 0:v\text{ is $L$-light for all
$L\geqslant\ell$}\\}.$

Note in particular that if $|B_{L}(v)|\leqslant(d(1+\varepsilon))^{L}$ for all
$L\geqslant 0$, then $\ell(v)=0$ and $B_{\ell(v)}(v)$ has no edges. Finally,
we define the excision of a graph $G$ as

$H\coloneqq\bigcup_{v\in V}B_{\ell(v)}(v),$

and refer to the graph after the removal of edges in $H$ as the bulk of $G$.

The ingredients to prove Theorem 4.9 are:

  * •

Observation 6.2, which says that the bulk of any graph has bounded degree, and
the excision of any graph is $(\Delta,D)$-pseudorandom for some $\Delta$ and
$D=(1+\varepsilon)d$.

  * •

Lemma 6.3, which says that the excision of a sparse random graph is a near-
forest with high probability.

  * •

Lemma 6.4, which shows that $\Delta=o(\log n)$ with high probability.

######  Notation ($\bm{H}$).

We will use $\bm{H}$ to refer to the excision of $\bm{G}$.

######  Observation 6.2.

For any graph $G$, let $G_{1}$ and $G_{2}$ denote its bulk and excision
respectively. Then, for some $\Delta>0$ and $D\coloneqq(1+\varepsilon)d$:

  1. 1.

The maximum degree of $G_{1}$ is at most $D$.

  2. 2.

$G_{2}$ is $(\Delta,D)$-pseudorandom with respect to $S\coloneqq
V^{\prime}(G_{1})\cap V^{\prime}(G_{2})$.

######  Lemma 6.3.

With probability $1-o(1)$, $\bm{H}$ is a near-forest.

The following statement establishes the claimed bound on $\Delta$.

######  Lemma 6.4.

With probability $1-o(1)$, for every vertex $v$ in $\bm{G}$ and $\ell\geqslant
0$, $\frac{|B_{\ell}(v)|}{(d(1+\varepsilon))^{\ell}}=o(\log n)$.

We are now ready to prove Theorem 4.9.

###### Proof of Theorem 4.9.

Choose $\bm{G}_{1}$ as the bulk of $\bm{G}$, and $\bm{G}_{2}$ as the excision
of $\bm{G}$. The statement then immediately follows from Observations 6.2, 6.3
and 6.4. ∎

It now remains to prove the above statements. The statement of Lemma 6.4 is a
mild strengthening of [BGGŠ24, Lemma 9 of arXiv version] and follows standard
arguments involving branching processes (see, e.g., [BGGŠ24, Lemma 29]), and
hence, we defer its proof to Appendix A.

The rest of this section is dedicated to proving Lemma 6.3, which establishes
that $\bm{H}$ is a near forest with high probability.

###  6.1 Excisions of sparse random graphs are near-forests

The key technical ingredient in the proof of Lemma 6.3 is the following.

######  Lemma 6.5.

With probability $1-o(1)$, for any connected component $C$ of $\bm{H}$,
$\operatorname{diam}(C)\leqslant O\left\lparen\tfrac{\log
n}{\varepsilon^{3}d}\right\rparen$.

As foreshadowed in the technical overview, we will also need the following
structural result about small sets in sparse random graphs.

######  Lemma 6.6 ([BLM15, Lemma 30], also see [BGGŠ24, Lemma 31]).

For $\bm{G}\sim\mathrm{SBM}(n,d,\lambda)$, with high probability, there is no
connected set $S$ of vertices with $|S|<\frac{1}{2}\cdot\frac{\log n}{\log d}$
that has tree-excess larger than $1$.

Assuming the above, let us present a proof of Lemma 6.3.

###### Proof of Lemma 6.3.

Condition on the event in Lemma 6.5, so we have that every component $C$ of
$H$ has diameter at most $\log n/d$. Suppose instead that $C$ had tree-excess
at least $2$, and let $C_{1},C_{2}$ be minimal cycles in $C$ (in that they do
not have any chords). Consider the induced subgraph on the set $S$ of vertices
in $C$ comprised of $C_{1},C_{2}$, and a shortest path (in $C$) between the
two. Note in particular that $S$ is connected, and $|S|\leqslant
5\operatorname{diam}(C)$. Since $\varepsilon=\Omega_{d}(\log d/d)^{1/3}$, we
may apply Lemma 6.6 to conclude that the tree-excess of the induced subgraph
on $S$ is at most $1$, a contradiction. ∎

We now turn our attention to proving Lemma 6.5, which bounds the diameter of
each connected component of $\bm{H}$. A key auxiliary graph in our proof is
the cluster graph.

######  Definition 6.7.

Given a graph $G$ on $[n]$, the associated cluster graph $\mathsf{Cluster}(G)$
has vertex set $[n]$, with an edge between $u$ and $v$ iff $\ell(u),\ell(v)>0$
and $B_{\ell(u)}(u)\cap B_{\ell(v)}(v)\neq\varnothing$. Furthermore, each
vertex $u$ in this graph has associated weight
$\operatorname{wt}(u)=(1+\varepsilon)^{\ell(u)}$, and each edge $uv$ has
weight $\operatorname{wt}(u,v)=\ell(u)+\ell(v)$.

Observe that Lemma 6.5 follows immediately from the following two statements:

  1. 1.

Lemma 6.8, which shows that if a connected component of $\bm{H}$ has large
diameter, then it causes a high-weight induced path in
$\mathsf{Cluster}(\bm{G})$.

  2. 2.

Lemma 6.9, which establishes that there are no high-weight induced paths in
$\mathsf{Cluster}(\bm{G})$.

######  Lemma 6.8.

Suppose the diameter of a connected component of $\bm{H}$ exceeds $\tau$. Then
there are vertices $u_{1},\dots,u_{k}\in[n]$ such that the induced subgraph in
$\mathsf{Cluster}(\bm{G})$ is the path $u_{1}\dots u_{k}$, and

$\sum_{i\in[k]}\ell(u_{i})\geqslant\frac{\tau}{2}\,.$

######  Lemma 6.9.

Define $\eta$ as
$\min\left\\{\frac{\varepsilon^{2}}{54},\frac{1}{18}\right\\}$. With
probability $1-o(1)$, for any $U=\\{u_{1},\dots,u_{k}\\}$ such that the
induced subgraph on $U$ in $\mathsf{Cluster}(\bm{G})$ is the path $u_{1}\dots
u_{k}$, we have:

$\sum_{i\in[k]}\ell(u_{i})<\frac{32\log n}{\eta\varepsilon d}\,.$

The proof of Lemma 6.8 is fairly short and self-contained, and we present it
below.

###### Proof of Lemma 6.8.

There must be vertices $a$ and $b$ in a single connected component of $\bm{H}$
such that $\mathsf{dist}_{\bm{H}}(a,b)>\tau$. Let $u$ and $v$ be vertices such
that $B_{\ell(a)}(a)$ and $B_{\ell(b)}(b)$ contain $u$ and $v$ respectively.

Let $u_{1}u_{2}\dots u_{k}$ be the weighted shortest path between $u$ and $v$
in $\mathsf{Cluster}(\bm{G})$ where $u_{1}=u$ and $u_{k}=v$. The path between
$a$ and $b$ has length bounded by $2\sum_{i\in[k]}\ell_{i}$, and hence:

$\sum_{i\in[k]}\ell_{i}\geqslant\frac{\tau}{2}\,.$

The induced subgraph on $\\{u_{1},\dots,u_{k}\\}$ certainly contains the
claimed path by construction. It remains to show that there are no other edges
besides the ones in the path. If there is an edge between $u_{i}$ and $u_{j}$
for $j\neq i\pm 1$ for $i<j$, then the path $u_{1}\cdots
u_{i}u_{j}u_{j+1}\cdots u_{k}$ is a shorter path than the original one, which
leads to a contradiction. Indeed, since the edge weights are positive and
$\operatorname{wt}(u,v)=\ell(u)+\ell(v)$, any path between $u_{i}$ and
$u_{j}$, in particular $u_{i}u_{i+1}\cdots u_{j-1}u_{j}$, has weight at least
$\ell(u_{i})+\ell(u_{j})$, with equality if and only if the path is just the
edge $u_{i}u_{j}$. ∎

We now begin the proof of Lemma 6.9 by setting up some terminology.

######  Definition 6.10 (Violating set and minimal violating set).

We say a subset of vertices $U$ is a violating set if the induced subgraph on
$U$ in $\mathsf{Cluster}(\bm{G})$ is a path of weight exceeding $\tfrac{32\log
n}{\eta\varepsilon d}$. We say $U$ is a minimal violating set if it is a
violating set, and no subset of $U$ is a violating set.

######  Definition 6.11 (Signature).

The signature of a minimum violating set is the tuple $\left\lparen
k,\vec{u},\vec{\ell}\right\rparen$ where $k$ is the number of vertices in the
minimum violating set, $\vec{u}=(u_{1},\dots,u_{k})$ is the vertices in the
minimum violating set in the order they appear in the path, and
$\vec{\ell}=(\ell(u_{1}),\dots,\ell(u_{k}))$.

######  Notation ($\mathcal{S}_{\kappa}$).

For any positive integer $\kappa$, define $\mathcal{S}_{\kappa}$ as all
signatures $({k,\vec{u},\vec{\ell}})$ for which $k\geqslant 1$ and
$\vec{\ell}$ is in $[\kappa]^{k}$.

To prove Lemma 6.9, it suffices to prove that there are no violating sets in
$\mathsf{Cluster}(\bm{G})$. Our goal is to prove that with high probability,
there are no violating sets in $\mathsf{Cluster}(\bm{G})$. We observe that it
suffices to prove there are no minimal violating sets (Observation 6.12), and
then bound the probability of containing a minimal violating set in
Observation 6.13.

######  Observation 6.12.

If $U\subseteq[n]$ is a violating set in $\mathsf{Cluster}(\bm{G})$, then it
contains a minimal violating set $U^{\prime}\subseteq U$.

######  Observation 6.13.

For any positive integer $\kappa$, the probability that
$\mathsf{Cluster}(\bm{G})$ contains a minimal violating set is bounded by

$\sum_{\left\lparen
k,\vec{u},\vec{\ell}\right\rparen\in\mathcal{S}_{\kappa}}\bm{\mathrm{Pr}}\left[\exists\text{MVS
with signature }\left\lparen k,\vec{u},\vec{\ell}\right\rparen\text{ in
}\mathsf{Cluster}\left\lparen\bm{G}\right\rparen\right]+\bm{\mathrm{Pr}}\left[\exists
v\in[n]\text{ s.t. }\ell(v)>\kappa\right],$

where MVS is short for “minimal violating set”.

The following, proved in Appendix A, gives a choice of $\kappa$ for which the
second term of the above is negligible.

######  Lemma 6.14.

For $\kappa=\frac{4}{\varepsilon}\log\frac{\log n}{\eta d}$, we have:

$\bm{\mathrm{Pr}}\left[\exists v\in[n]\text{ s.t.
}\ell(v)>\kappa\right]=o(1)\,.$

The following gives us a handle on the first term of the bound in Observation
6.13.

######  Lemma 6.15.

For $\kappa=\frac{4}{\varepsilon}\log\frac{\log n}{\eta d}$ and for any
$(k,\vec{u},\vec{\ell})\in\mathcal{S}_{\kappa}$ where
$\vec{\ell}=(\ell_{1},\dots,\ell_{k})$, we have:

$\displaystyle\bm{\mathrm{Pr}}$ $\displaystyle\left[\exists\text{MVS with
signature }\left\lparen k,\vec{u},\vec{\ell}\right\rparen\text{ in
}\mathsf{Cluster}(\bm{G})\right]$
$\displaystyle\qquad\leqslant\frac{1}{n^{k-1}}\prod_{i\in[k]}2\ell_{i}^{2}\cdot\left\lparen
d(1+\varepsilon)\right\rparen^{2\ell_{i}}\cdot\exp\left\lparen-\frac{\eta
d}{2}\left\lparen
1+\frac{\varepsilon}{4}\right\rparen^{\ell_{i}}\right\rparen\,.$

######  Remark 6.16.

The way to interpret the above is to think of the probability bound as
decaying at a doubly exponential rate in each $\ell_{i}$, and for the events
$\\{u_{i}\text{ is }\ell_{i}\text{-heavy}\\}$ as being approximately
independent. See Lemma A.1 and its proof to understand the doubly exponential
decay rate.

We first show how to complete the proof of Lemma 6.9, and then later prove
Lemma 6.15.

###### Proof of Lemma 6.9.

By Observation 6.12 it suffices to prove that there is no minimal violating
set in $\mathsf{Cluster}(\bm{G})$. The definition of a signature $\left\lparen
k,\vec{u},\vec{\ell}\right\rparen$ of a minimal violating set implies that
$\sum_{i}\ell_{i}\geqslant\frac{32\log n}{\eta\varepsilon d}$. Hence, by
Observations 6.13, 6.14 and 6.15, we get that the probability of containing a
violating set is at most:

$\displaystyle n\sum_{k\geqslant
1}\sum_{\begin{subarray}{c}\ell_{1},\ldots\ell_{k}\\\
\sum\ell_{i}\geqslant\tfrac{32\log n}{\eta\varepsilon
d}\end{subarray}}\prod_{i\in[k]}2\ell_{i}^{2}\cdot(d(1+\varepsilon))^{2\ell_{i}}\cdot\exp\left(-\frac{\eta
d}{2}\left(1+\frac{\varepsilon}{4}\right)^{\ell_{i}}\right).$ (11)

Consider one of the terms in the product, which is

$\exp\left(\log(2\ell_{i}^{2})+2\ell_{i}\log(d(1+\varepsilon))-\frac{\eta
d}{2}\left(1+\frac{\varepsilon}{4}\right)^{\ell_{i}}\right)\leqslant\exp\left(\ell_{i}(2\log(d(1+\varepsilon))+2)-\frac{\eta
d}{2}\left(1+\frac{\varepsilon}{4}\right)^{\ell_{i}}\right).$

We claim that for

$\varepsilon\geqslant 1500\left(\frac{100+\log d}{d}\right)^{1/3},$ (12)

the above is at most $\exp\left(-\ell_{i}\left(1+\frac{\eta\varepsilon
d}{16}\right)\right)$. Indeed, since
$\left(1+\frac{\varepsilon}{4}\right)^{\ell_{i}}\geqslant\frac{\varepsilon}{4}\cdot\ell_{i}$,
the above quantity is at most

$\exp\left(-\ell_{i}\left(\frac{\eta\varepsilon
d}{8}-2-2\log\left(d(1+\varepsilon)\right)\right)\right).$

Therefore, it suffices for $\varepsilon$ to satisfy

$\frac{\eta\varepsilon d}{16}\geqslant 2\log\left(d(1+\varepsilon)\right)+3.$

It is straightforward to verify that $\varepsilon$ as in (12) satisfies the
above. Given this, (11) is at most

$\displaystyle n\sum_{k\geqslant
1}\sum_{\begin{subarray}{c}\ell_{1},\ldots\ell_{k}\\\
\sum\ell_{i}\geqslant\tfrac{32\log n}{\eta\varepsilon
d}\end{subarray}}\exp\left(-\left(\frac{\eta\varepsilon
d}{16}+1\right)\sum_{i\in[k]}\ell_{i}\right)$
$\displaystyle\leqslant\frac{1}{n}\sum_{k\geqslant
1}\sum_{\begin{subarray}{c}\ell_{1},\ldots\ell_{k}\\\
\sum\ell_{i}\geqslant\tfrac{32\log n}{\eta\varepsilon
d}\end{subarray}}\exp\left(-\sum_{i\in[k]}\ell_{i}\right)$
$\displaystyle\leqslant\frac{1}{n}\sum_{k\geqslant
1}\sum_{\ell_{1},\ldots\ell_{k}\geqslant
1}\exp\left(-\sum_{i\in[k]}\ell_{i}\right)$
$\displaystyle\leqslant\frac{1}{n}\sum_{k\geqslant 1}\exp(-\Omega(k))=o(1),$

as desired. ∎

We now turn our attention to proving Lemma 6.15. The following two statements
(Lemmas 6.19 and 6.17) will be used in the proof. We defer their proofs to
Appendix A.

######  Lemma 6.17.

Let $u_{1},u_{2},\ldots,u_{r}\in[n]$ and
$\ell_{1},\ell_{2},\ldots,\ell_{r}>0$. Then,

$\bm{\mathrm{Pr}}\left[\ell(u_{i})=\ell_{i}\,\,\forall i\in[r]\text{ and
}B_{\ell_{i}}(u_{i})\cap B_{\ell_{j}}(u_{j})=\varnothing\,\,\forall i\neq
j\in[r]\right]\leqslant\prod_{i\in[r]}\exp\left(-\eta
d\left(1+\frac{\varepsilon}{4}\right)^{\ell_{i}}\right).$

######  Remark 6.18.

In the above bound, the reader should treat the events
$\\{\ell_{i}=\ell(u_{i})\\}$ as roughly independent. Informally, the
approximate independence can be justified by the fact that the union of the
balls covers only a small fraction of the graph, and hence for a vertex
$u_{r}$ disjoint from $B_{\ell(u_{1})}(u_{1})\cup\dots\cup
B_{\ell(u_{r-1})}(u_{r-1})$, the probability that $B_{\ell(u_{r})}(u_{r})$
intersects the rest is very small — it is roughly the probability that two
small subsets of $[n]$ intersects. Furthermore, when the ball around $u_{r}$
is disjoint from the remaining balls, its size is not influenced by the other
balls, resulting in approximate independence.

######  Lemma 6.19.

Let $S,T_{1},T$ be disjoint subsets of vertices, and say $T=T_{2}\sqcup
T^{\prime}$. Let $\mathcal{E}$ be an (arbitrary) conditioning of the edges
adjacent to vertices in $S,T_{1},T$ such that for any $A=S,T_{1},T$, we can
write $A=A_{\mathrm{in}}\sqcup A_{\mathrm{out}}$ such that the following
holds.

  * •

$|A|=o(n)$.

  * •

Every edge incident on vertices in $A_{\mathrm{in}}$ is fixed in a way that
there are no edges between $A_{\mathrm{out}}$ and $A^{c}$.

  * •

Further, there is no conditioning done on the edges between $A_{\mathrm{out}}$
and $(S_{\mathrm{in}}\cup(T_{1})_{\mathrm{in}}\cup T_{\mathrm{in}})^{c}$.

Let $u\in[n]$ and $\ell>0$. Then, for $n$ sufficiently large,

$\bm{\mathrm{Pr}}\left[\text{$u$ is $\ell$-light and }B_{\ell}(u)\cap
T_{i}\neq\varnothing\text{ for
}i\in\\{1,2\\}\mid\mathcal{E}\right]\leqslant\frac{2\ell^{2}\cdot(d(1+\varepsilon))^{2\ell}\cdot|T_{1}|\cdot|T_{2}|}{n^{2}}.$

######  Remark 6.20.

Put more intuitively, Lemma 6.19 is a generalization of the following simple
observation: for any small set of vertices of size $C$, then the probability
that a random vertex is contained in said set scales like $C/n$. The technical
assumptions on $S,T_{1},$ and $T$ are present to ensure that the lemma applies
throughout the proof of Lemma 6.9; see Figure 4 for a depiction of these sets.

$G$$B_{\ell_{3}}(u_{3})$$B_{\ell_{5}}(u_{5})$$B_{\ell_{4}}(u_{4})$$G$Legend$T^{\prime}$$T_{2}$$B_{\ell}(u)$$T_{1}$$S$$B_{\ell_{1}}(u_{1})$$B_{\ell_{2}}(u_{2})$$B_{\ell_{7}}(u_{7})$$B_{\ell_{9}}(u_{9})$
Figure 4: A depiction of the sets $T_{1},T_{2},T^{\prime},S$, and
$B_{\ell}(u)$. The event of interest in Lemma 6.19 is when the random set of
interest $B_{\ell}(u)$ (shaded blue) intersects the two target sets $T_{1}$
(solid purple) and $T_{2}$ (solid green). The other two sets of vertices $S$
and $T^{\prime}$ cover the additional edges that need to be conditioned on to
apply the lemma inductively to bound the length of the path $u_{1}\ldots
u_{k}$ in the cluster graph. In our setting, all the sets involved are unions
of balls centered at the vertices $u_{i}$.

We now prove Lemma 6.15.

###### Proof of Lemma 6.15.

Assume, without loss of generality, that

$\sum_{i\text{ odd}}(1+\varepsilon)^{\ell_{i}}\geqslant\sum_{i\text{
even}}(1+\varepsilon)^{\ell_{i}}\,.$

Thus, for the independent set $\\{u_{i}:i\text{ odd}\\}$, we have

$\sum_{i\text{
odd}}(1+\varepsilon)^{\ell_{i}}\geqslant\frac{1}{2}\sum_{i}(1+\varepsilon)^{\ell_{i}}\,.$

Let $\mathcal{E}_{\text{independent}}$ be the event that
$\ell(u_{i})=\ell_{i}$ for all odd $i$ and $B_{\ell_{i}}(u_{i})\cap
B_{\ell_{j}}(u_{j})=\varnothing$ for distinct odd $i,j$. Let
$\mathcal{E}_{\text{cross}}$ be the event that for all even $i$ and $j=i\pm
1$, $B_{\ell_{i}}(u_{i})\cap B_{\ell_{j}}(u_{j})\neq\varnothing$. Then,

$\displaystyle\bm{\mathrm{Pr}}\left[\exists\text{MVS with signature
}\left\lparen k,\vec{u},\vec{\ell}\right\rparen\text{ in
}\mathsf{Cluster}(\bm{G})\right]$
$\displaystyle\quad\quad\leqslant\bm{\mathrm{Pr}}\left[\mathcal{E}_{\text{independent}},\,\mathcal{E}_{\text{cross}}\right]$
(13)
$\displaystyle\quad\quad=\bm{\mathrm{Pr}}[\mathcal{E}_{\text{independent}}]\cdot\bm{\mathrm{Pr}}[\mathcal{E}_{\text{cross}}\mid\mathcal{E}_{\text{independent}}]$
$\displaystyle\quad\quad\leqslant\prod_{i\text{ odd}}\exp(-\eta
d(1+\varepsilon)^{\ell_{i}})\cdot\prod_{i\text{
even}}2\ell_{i}^{2}\cdot\frac{(d(1+\varepsilon))^{2\ell_{i}+\ell_{i-1}+\ell_{i+1}}}{n^{2}}$
(14)
$\displaystyle\quad\quad\leqslant\frac{1}{n^{k-1}}\prod_{i\in[k]}2\ell_{i}^{2}\cdot(d(1+\varepsilon))^{2\ell_{i}}\cdot\exp\left(-\frac{\eta
d}{2}\left(1+\frac{\varepsilon}{4}\right)^{\ell_{i}}\right).$ (15)

To explain the above chain of inequalities, in (13) we dropped the condition
that $\ell(u_{i})=\ell_{i}$ for even $i$. In (14), we applied Lemma 6.17 and
Lemma 6.19 inductively with the setting

$T_{1}=B_{\ell_{i+1}}(u_{i+1}),\,S=\bigcup_{\begin{subarray}{c}i\text{ odd}\\\
j>i+1\end{subarray}}B_{\ell_{j}}(u_{j}),\,T^{\prime}=\bigcup_{j<i-1}B_{\ell_{j}}(u_{j}),\,T_{2}=B_{\ell_{i-1}}(u_{i-1})\setminus
T^{\prime}\,.$

When applying Lemma 6.19, we use the bound of $\kappa$ on $\ell_{i}$ to
conclude that the size of the union of all these balls is $o(n)$. See Figure 4
for an illustration. In (15), we used the fact that the odd vertices have at
least half of the total vertex weight. ∎

###  6.2 Bounding the sizes of components

In this section, we prove high probability bounds on the sizes of connected
components in $\bm{H}$, which are of interest when studying the Ising model on
centered interaction matrices.

Lemma 5.16, which states that the maximum size of a connected component is
$n^{o_{d}(1)}$, is a consequence of Lemma 6.5. See 5.16

###### Proof.

By Lemma 6.5, we know that for any connected component $C$, there is an
absolute positive constant $c$ such that
$\operatorname{diam}(C)\leqslant\frac{c\log n}{\varepsilon^{3}d}$. Note that
any vertex $u\in C$ is $\operatorname{diam}(C)$-light. Furthermore, we have
$B_{\operatorname{diam}(C)}(u)\supseteq C$, so

$\lvert
C\rvert\leqslant(d(1+\varepsilon))^{\operatorname{diam}(C)}\leqslant\exp\left(\log(d(1+\varepsilon))\cdot\frac{c\log
n}{\varepsilon^{3}d}\right)=n^{\tfrac{c\log(d(1+\varepsilon))}{\varepsilon^{3}d}},$

as desired. ∎

Using similar ingredients, we are also able to establish the following
quantitative bound on the sum of squared component sizes, from which Lemma
5.15 follows.

######  Lemma 6.21.

Write $H=\sqcup_{C\in\mathsf{cc}(H)}C$, where $\mathsf{cc}(H)$ denotes the
connected components of $H$. There are absolute constants $c_{1},c_{2}>0$ such
that for $\varepsilon\geqslant c_{1}(\log d/d)^{1/3}$, with probability
$1-o(1)$,

$\sum_{\begin{subarray}{c}C\in\mathsf{cc}(H)\\\ \lvert
C\rvert>1\end{subarray}}\lvert
C\rvert^{2}\leqslant\exp(-c_{2}\varepsilon^{3}d)n.$

We now turn our attention to proving Lemma 6.21, which gives a high
probability bounds on the sizes of component sizes in $H$. The proof
essentially amounts to bounding the first and second moments. For the first
moment bound, many of the key ingredients are already contained in the proof
of Lemma 6.5; for the variance bound, we use the Efron-Stein inequality.

###### Proof of Lemma 6.21.

For succinctness, define the random variable

$\displaystyle X\coloneqq\sum_{C\in\mathsf{cc}(H)}\lvert
C\rvert^{2}\cdot\bm{1}[\lvert C\rvert>1].$

For distinct $u,v\in[n]$, define the random variable $X_{uv}=\bm{1}[u,v\text{
are in the same component}]$. Notice that

$\displaystyle X=\sum_{u\neq v}X_{uv}\,.$

Hence for the first moment it suffices to upper bound
$\bm{\mathrm{E}}[X_{uv}]=\bm{\mathrm{Pr}}[u,v\text{ are in the same
component}]$. In fact, bounding $\bm{\mathrm{E}}[X_{uv}]$ uses tools similar
to what we used in the proof of Lemma 6.5.

Observe that for distinct $u$ and $v$, they are in the same connected
component only if there are $u^{\prime}$ and $v^{\prime}$ (which need not be
distinct) which satisfy the following:

  * •

$\ell_{u^{\prime}},\ell_{v^{\prime}}>0$, so that $u^{\prime}$ and $v^{\prime}$
belong to nontrivial connected components.

  * •

$u\in B_{\ell_{u^{\prime}}}(u^{\prime})$ and $v\in
B_{\ell_{v^{\prime}}}(v^{\prime})$.

  * •

There is a path between $u^{\prime}$ and $v^{\prime}$ in
$\mathsf{Cluster}(\bm{G})$.

Note that if $u^{\prime}=v^{\prime}$, we allow for self loops, as long as
$\ell_{u^{\prime}}>0$; this is consistent with Definition 6.7. Hence, we have

$\displaystyle\sum_{u\neq v}X_{uv}$
$\displaystyle\leqslant\sum_{u^{\prime},v^{\prime}\in[n]}\lvert
B_{\ell_{u^{\prime}}}(u^{\prime})\rvert\lvert
B_{\ell_{v^{\prime}}}(v^{\prime})\rvert\bm{1}[u^{\prime},v^{\prime}\text{
connected in }\mathsf{Cluster}(\bm{G})].$

Fix a path length $k$, positive integers $\ell_{i}$ for $i\in[k]$, and a path
$w_{1}\cdots w_{k}$ with $w_{1}=u^{\prime}$ and $w_{k}=v^{\prime}$. Consider
the event $\mathcal{E}$ whose probability we bounded in Lemma 6.9:

$\mathcal{E}\coloneqq\\{\ell_{i}=\ell(w_{i})\text{ for $i\in[k]$ and
}B_{\ell_{i}}(w_{i})\cap B_{\ell_{j}}(w_{j})\neq\varnothing\text{ iff $j=i\pm
1$ for $i\in[k]$}\\}$

For the term at $u^{\prime},v^{\prime}$ in the sum to be nonzero, the above
event $\mathcal{E}$ must occur for some choice of $k$, positive $\ell_{i}$,
and path from $u^{\prime}$ to $v^{\prime}$. On $\mathcal{E}$, we can upper
bound

$\lvert B_{\ell_{u^{\prime}}}(u^{\prime})\rvert\cdot\lvert
B_{\ell_{v^{\prime}}}(v^{\prime})\rvert\cdot\bm{1}[u^{\prime},v^{\prime}\text{
connected in
}\mathsf{Cluster}(\bm{G})]\leqslant(d(1+\varepsilon))^{\ell_{1}+\ell_{k}},$

and a careful inspection of the proof of Lemma 6.9 establishes that

$\displaystyle(d(1+\varepsilon))^{\ell_{1}+\ell_{k}}\bm{\mathrm{Pr}}[\mathcal{E}]\leqslant\prod_{i\in[k]}2\ell_{i}^{2}\cdot(d(1+\varepsilon))^{2\ell_{i}}\cdot\exp\left(-\tfrac{\eta
d}{2}(1+\tfrac{\varepsilon}{4})^{\ell_{i}}\right).$

Indeed, in (14), only one factor of $(d(1+\varepsilon))^{\ell_{i}}$ is picked
up for $i\in\\{1,k\\}$, as they have only one neighbor in the chain.

Now choose $\varepsilon$ such that

$\frac{\eta\varepsilon d}{16}\geqslant 2\log\left(d(1+\varepsilon)\right)+2,$

which is satisfied for $\varepsilon\geqslant 1500\left(\frac{100+\log
d}{d}\right)^{1/3}$. Summing up now over all $k$, $\ell_{i}$, and paths from
$u^{\prime}$ to $v^{\prime}$, we obtain

$\displaystyle\bm{\mathrm{E}}\left[\sum_{u^{\prime},v^{\prime}\in[n]}\lvert
B_{\ell_{u^{\prime}}}(u^{\prime})\rvert\cdot\lvert
B_{\ell_{v^{\prime}}}(v^{\prime})\rvert\cdot\bm{1}[u^{\prime},v^{\prime}\text{
connected in }\mathsf{Cluster}(\bm{G})]\right]$
$\displaystyle\quad\quad\leqslant n\sum_{k\geqslant
1}\sum_{\ell_{1},\ldots\ell_{k}\geqslant
1}\prod_{i\in[k]}2\ell_{i}^{2}\cdot(d(1+\varepsilon))^{2\ell_{i}}\cdot\exp\left(-\tfrac{\eta
d}{2}(1+\tfrac{\varepsilon}{4})^{\ell_{i}}\right)$
$\displaystyle\quad\quad\leqslant n\sum_{k\geqslant
1}\sum_{\ell_{1},\ldots\ell_{k}\geqslant 1}\exp\left(-\frac{\eta\varepsilon
d}{16}\sum_{i\in[k]}\ell_{i}\right)$ $\displaystyle\quad\quad\leqslant
n\sum_{k\geqslant 1}\exp\left(-\frac{\eta\varepsilon
kd}{16}\right)\prod_{i\in[k]}\frac{\exp\left(-\frac{\eta\varepsilon
d}{16}\right)}{1-\exp\left(-\frac{\eta\varepsilon d}{16}\right)}$
$\displaystyle\quad\quad\leqslant n\sum_{k\geqslant
1}\exp\left(-\frac{\eta\varepsilon kd}{16}\right)$
$\displaystyle\quad\quad\leqslant 2\exp\left(-\frac{\eta\varepsilon
d}{16}\right)n,$

where in the second-to-last line we have used the fact that
$\frac{\eta\varepsilon d}{16}\geqslant 2$ and
$\tfrac{\exp(-2)}{1-\exp(-2)}\leqslant 1$, and in the last line we have used
$\tfrac{1}{1-\exp(-2)}\leqslant 2$. Hence, $\bm{\mathrm{E}}[X]\leqslant
2\exp(-\tfrac{\eta\varepsilon d}{16})n$.

We now show that $\bm{\mathrm{Var}}(X)=o(\bm{\mathrm{E}}[X]^{2})$, which
implies the desired result by applying Chebyshev. To establish this, we appeal
to the Efron-Stein inequality. Consider rerandomizing an edge $e$ in $\bm{G}$.
With probability at most $1-2d/n$, the rerandomized edge $e$ agrees with the
original edge, so the value of $X$ does not change. If it disagrees, then $X$
changes only if $e$ connects two connected components or if $e$ breaks a
connected component into two smaller connected components. Either way, we can
upper bound the magnitude of the difference by
$\max_{C\in\mathsf{cc}(H)}2\lvert C\rvert^{2}$.

By Lemma 5.16, $\max_{C\in\mathsf{cc}(H)}\lvert C\rvert^{2}\leqslant
n^{\tfrac{c\log d}{\varepsilon^{3}d}}$ for some absolute constant $c>0$, so

$\displaystyle\bm{\mathrm{Var}}(X)$ $\displaystyle\leqslant\frac{4d}{n}\cdot
n^{\tfrac{c\log d}{\varepsilon^{3}d}}\cdot n^{2}$ $\displaystyle\leqslant
4\exp\left(\log d+\frac{c\log d}{\varepsilon^{3}d}\log n\right)n.$

To conclude, it suffices to verify that for our choice of parameters

$\log d+\frac{c\log d}{\varepsilon^{3}d}\log
n<-\varepsilon^{3}d+\frac{1}{2}\log n.$

Indeed, for $\varepsilon\geqslant\left(\frac{K\log d}{d}\right)^{1/3}$ and any
$d=O(\log n)$, the left-hand-side of the above inequality is $O(\log\log
n)+\frac{c}{K}\log n$, whereas the right-hand-side is $\frac{1}{2}\log
n-O(\log\log n)$. Hence, the above inequality is satisfied for $K$ a
sufficiently large constant, which finishes the proof. ∎

## Acknowledgments

S.M. would like to thank Frederic Koehler for helpful conversations about
Ising models. S.M. was supported by CSAIL. A.R. is grateful for support from
an Akamai Presidential Fellowship. D.X.W. acknowledges support from NSF
Graduate Research Fellowship DGE-2146752.

## References

  * [AASV21] Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong.  Fractionally log-concave and sector-stable polynomials: counting planar matchings and more.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 433–446, 2021.
  * [Abb18] Emmanuel Abbe.  Community detection and stochastic block models: Recent developments.  Journal of Machine Learning Research, 18(177):1–86, 2018.
  * [AHL+23] Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu.  Parallel discrete sampling via continuous walks.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 103–116, 2023.
  * [AJK+21a] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong.  Entropic independence I: Modified log-Sobolev inequalities for fractionally log-concave distributions and high-temperature ising models.  arXiv preprint arXiv:2106.04105, 2021.
  * [AJK+21b] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong.  Entropic independence II: optimal sampling and concentration via restricted modified log-Sobolev inequalities.  arXiv preprint arXiv:2111.03247, 2021.
  * [AJK+24] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong.  Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses, pages 5029–5056.  2024\.
  * [AS15] Emmanuel Abbe and Colin Sandon.  Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 670–688. IEEE, 2015.
  * [BB19] Roland Bauerschmidt and Thierry Bodineau.  A very simple proof of the lsi for high temperature spin systems.  Journal of Functional Analysis, 276(8):2582–2588, 2019.
  * [BBD23] Roland Bauerschmidt, Thierry Bodineau, and Benoit Dagallier.  Kawasaki dynamics beyond the uniqueness threshold.  arXiv preprint arXiv:2310.04609, 2023.
  * [BCC+22] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda.  On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3670–3692. SIAM, 2022.
  * [BD97] Russ Bubley and Martin Dyer.  Path coupling: A technique for proving rapid mixing in Markov chains.  In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 223–231. IEEE, 1997.
  * [BGGŠ24] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič.  Fast Sampling via Spectral Independence Beyond Bounded-degree Graphs.  ACM Trans. Algorithms, 20(1), jan 2024.
  * [BLM15] Charles Bordenave, Marc Lelarge, and Laurent Massoulié.  Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347–1357. IEEE, 2015.
  * [BT06] Sergey G. Bobkov and Prasad Tetali.  Modified logarithmic sobolev inequalities in discrete settings.  Journal of Theoretical Probability, 19(2):289–336, Jun 2006.
  * [CE22] Y. Chen and R. Eldan.  Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract).  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 110–122, Los Alamitos, CA, USA, nov 2022. IEEE Computer Society.
  * [CLV21] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Optimal mixing of glauber dynamics: entropy factorization via high-dimensional expansion.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1537–1550. Association for Computing Machinery, 2021.
  * [DKMZ11] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.  Phys. Rev. E, 84:066106, Dec 2011.
  * [Dob68] PL Dobruschin.  The description of a random field by means of conditional probabilities and conditions of its regularity.  Theory of Probability & Its Applications, 13(2):197–224, 1968.
  * [DSS23] Jian Ding, Jian Song, and Rongfeng Sun.  A new correlation inequality for Ising models with external fields.  Probability Theory and Related Fields, 186(1):477–492, 2023.
  * [EAM22] Ahmed El Alaoui and Andrea Montanari.  An information-theoretic view of stochastic localization.  IEEE Transactions on Information Theory, 68(11):7423–7426, 2022.
  * [EAMS22] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke.  Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 323–334. IEEE, 2022.
  * [EAMS23] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke.  Sampling from Mean-Field Gibbs Measures via Diffusion Processes.  arXiv preprint arXiv:2310.08912, 2023.
  * [EF23] Charilaos Efthymiou and Weiming Feng.  On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on $\mathsf{G}(n,d/n)$.  In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:17, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [EKPS00] William Evans, Claire Kenyon, Yuval Peres, and Leonard J. Schulman.  Broadcasting on trees and the ising model.  Ann. Appl. Probab., 10(2):410–433, 2000.
  * [EKZ22] Ronen Eldan, Frederic Koehler, and Ofer Zeitouni.  A spectral condition for spectral gap: fast mixing in high-temperature ising models.  Probability theory and related fields, 182(3):1035–1051, 2022.
  * [Eld13] Ronen Eldan.  Thin shell implies spectral gap up to polylog via a stochastic localization scheme.  Geometric and Functional Analysis, 23(2):532–569, March 2013.
  * [EZ24] Charilaos Efthymiou and Kostas Zampetakis.  On sampling diluted spin glasses using glauber dynamics.  arXiv preprint arXiv:2403.08921, 2024.
  * [FM17] Zhou Fan and Andrea Montanari.  How well do local algorithms solve semidefinite programs?  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 604–614, 2017.
  * [FV17] Sacha Friedli and Yvan Velenik.  Statistical mechanics of lattice systems. a concrete mathematical introduction.  2017\.
  * [Goe04] Sharad Goel.  Modified logarithmic sobolev inequalities for some models of random walk.  Stochastic processes and their applications, 114(1):51–79, 2004.
  * [Gri06] Geoffrey Grimmett.  The random-cluster model, volume 333.  Springer, 2006.
  * [GT04] Francesco Guerra and Fabio Lucio Toninelli.  The high temperature region of the viana–bray diluted spin glass model.  Journal of statistical physics, 115:531–555, 2004.
  * [Hay06] Thomas P Hayes.  A simple condition implying rapid mixing of single-site dynamics on spin systems.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 39–46. IEEE, 2006.
  * [HMP24] Brice Huang, Andrea Montanari, and Huy Tuan Pham.  Sampling from spherical spin glasses in total variation via algorithmic stochastic localization.  arXiv preprint arXiv:2404.15651, 2024.
  * [HS86] Richard Holley and Daniel W Stroock.  Logarithmic sobolev inequalities and stochastic ising models.  1986\.
  * [JS93] Mark Jerrum and Alistair Sinclair.  Polynomial-time approximation algorithms for the ising model.  SIAM Journal on computing, 22(5):1087–1116, 1993.
  * [KLR22] Frederic Koehler, Holden Lee, and Andrej Risteski.  Sampling approximately low-rank ising models: Mcmc meets variational methods.  In Conference on Learning Theory, pages 4945–4988. PMLR, 2022.
  * [Kun23] Dmitriy Kunisky.  Optimality of glauber dynamics for general-purpose ising model sampling and free energy approximation.  arXiv preprint arXiv:2307.12581, 2023.
  * [Led01] Michel Ledoux.  Logarithmic sobolev inequalities for unbounded spin systems revisited.  Séminaire de Probabilités XXXV, pages 167–194, 2001.
  * [Liu21] Kuikui Liu.  From coupling to spectral independence and blackbox comparison with the down-up walk.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [LMR22] Siqi Liu, Sidhanth Mohanty, and Prasad Raghavendra.  On statistical inference when fixed points of belief propagation are unstable.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 395–405. IEEE, 2022.
  * [Mas14] Laurent Massoulié.  Community detection thresholds and the weak ramanujan property.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 694–703, 2014.
  * [MM09] Marc Mézard and Andrea Montanari.  Information, Physics, and Computation.  Oxford University Press, 01 2009.
  * [MNS14] Elchanan Mossel, Joe Neeman, and Allan Sly.  Belief propagation, robust reconstruction and optimal recovery of block models.  In Conference on Learning Theory, pages 356–370. PMLR, 2014.
  * [MNS15] Elchanan Mossel, Joe Neeman, and Allan Sly.  Reconstruction and estimation in the planted partition model.  Probability Theory and Related Fields, 162(3-4):431–461, 2015.
  * [MNS18] Elchanan Mossel, Joe Neeman, and Allan Sly.  A proof of the block model threshold conjecture.  Combinatorica, 38(3):665–708, jun 2018.
  * [Mon98] Rémi Monasson.  Optimization problems and replica symmetry breaking in finite connectivity spin glasses.  Journal of Physics A: Mathematical and General, 31(2):513, 1998.
  * [Mon23] Andrea Montanari.  Sampling, diffusions, and stochastic localization.  arXiv preprint arXiv:2305.10690, 2023.
  * [MP01] Marc Mézard and Giorgio Parisi.  The bethe lattice spin glass revisited.  The European Physical Journal B, 20:217–233, 2001.
  * [MP03] Marc Mézard and Giorgio Parisi.  The cavity method at zero temperature.  Journal of Statistical Physics, 111:1–34, 2003.
  * [MS13] Elchanan Mossel and Allan Sly.  Exact thresholds for ising–gibbs samplers on general graphs.  2013\.
  * [MW23] Andrea Montanari and Yuchen Wu.  Posterior sampling from the spiked models via diffusion processes.  arXiv preprint arXiv:2304.11449, 2023.
  * [Roc24] Sebastien Roch.  Modern Discrete Probability: An Essential Toolkit.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2024.
  * [SM22] Ludovic Stephan and Laurent Massoulié.  Non-backtracking spectra of weighted inhomogeneous random graphs.  Mathematical Statistics and Learning, 5(3):201–271, 2022.
  * [SS12] Allan Sly and Nike Sun.  The computational hardness of counting in two-spin models on d-regular graphs.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 361–369, 2012.
  * [ST96] Harold M Stark and Audrey A Terras.  Zeta functions of finite graphs and coverings.  Advances in Mathematics, 121(1):124–165, 1996.
  * [Tal11] Michel Talagrand.  Mean Field Models for Spin Glasses: Volume I: Basic Examples, volume 54 of A Series of Modern Surveys in Mathematics.  Springer-Verlag, 2011.
  * [WJ08] Martin J. Wainwright and Michael I. Jordan.  Graphical Models, Exponential Families, and Variational Inference, volume 1 of Foundations and Trends in Machine Learning.  Now Publishers Inc, 2008.
  * [YP23] Qian Yu and Yury Polyanskiy.  Ising model on locally tree-like graphs: Uniqueness of solutions to cavity equations.  IEEE Transactions on Information Theory, 2023.

##  Appendix A Proofs omitted from the main text

###  A.1 Generalized MLSI for Ising models on pseudorandom near-forests

We begin with a proof of Lemma 4.19. While the proof we state in the main text
which assumes that all nonzero interactions are equal suffices for our
purposes, a more general result holds.

See 4.19

###### Proof.

To prove this statement, as in the simpler proof given in the main text, we
will use Lemmas 3.18 and 3.19, albeit with the stochastic localization using a
time-varying control matrix. Again, set $s_{0}=\frac{\gamma}{\sqrt{D}}$.
Consider the graph $H_{t}$ on $V(H)$ with edge set

$E(H_{t})=\left\\{ij\in E(H):J_{ij}>t\cdot\frac{\gamma}{\sqrt{D}}\right\\}.$

In particular, $H_{1}$ is empty. The control matrix at time $t$ is defined by
$C_{t}=\left((1-s_{0}^{2})\cdot\operatorname{BH}_{H_{t}}\left(-\frac{\gamma}{\sqrt{D}}\right)\right)^{1/2}$.
As in the simpler proof, this is a non-negative matrix that is well-defined
due to Corollary 3.24. At time $t$, the interaction matrix $J_{t}$ is, on the
off-diagonal elements, supported on the graph $H_{t}$, with the interactions
being at most $\frac{\gamma}{\sqrt{D}}$. In particular, $J_{1}$ is a diagonal
matrix so $\mu_{1}$ is a product measure. Now, for an arbitrary tilt $h$,

$\bm{\mathrm{Cov}}\left(\mu_{J_{t},h}\right)\leqslant\sum_{\ell\geqslant
0}\left(\frac{\gamma}{\sqrt{D}}\right)^{\ell}A^{(\ell)}_{H_{t}}\leqslant\sum_{\ell\geqslant
0}\left(\frac{\gamma}{\sqrt{D}}\right)^{\ell}A^{(\ell)}_{H}=\operatorname{BH}_{H}(s_{0})^{-1},$

where the inequalities mean that the entries of the (non-negative) matrix on
the left are at most that of the corresponding entries on the right.
Similarly, because $H_{t}$ is a subgraph of $H$,
$C_{t}^{2}\leqslant(1-s_{0}^{2})\operatorname{BH}_{H}(-s_{0})$. Using
Corollaries 4.16 and 4.18, we have that

$\displaystyle\left\lVert
C_{t}\cdot\bm{\mathrm{Cov}}\left(\mu_{J_{t},h}\right)\cdot C_{t}\right\rVert$
$\displaystyle\leqslant\left\lVert\bm{\mathrm{Cov}}\left(\mu_{J_{t},h}\right)\cdot
C_{t}^{2}\right\rVert$
$\displaystyle\leqslant(1-s_{0}^{2})\left\lVert\operatorname{BH}_{H}(s_{0})^{-1}\cdot\operatorname{BH}_{H}(-s_{0})\right\rVert$
$\displaystyle=(1-s_{0}^{2})\left\lVert\operatorname{BH}_{H}(s_{0})^{-1}\cdot\left(\operatorname{BH}_{H}(s_{0})+\frac{2s_{0}}{1-s_{0}^{2}}\cdot
A_{H}\right)\right\rVert$
$\displaystyle\leqslant(1-s_{0}^{2})+\frac{2s_{0}}{1-s_{0}^{2}}\left\lVert\operatorname{BH}_{H}(s_{0})^{-1}\cdot
A_{H}\right\rVert$ $\displaystyle\leqslant
1+\frac{8}{(1-\gamma)^{2}}\cdot\frac{\Delta}{D}.$

The measure at time $1$ is almost surely a product measure, therefore

$\displaystyle C_{\mathrm{MLSI}}(\mu_{J,h})$
$\displaystyle\geqslant\frac{1}{n}\cdot\exp\left(-\int_{0}^{1}\sup_{h\in\mathbb{R}^{n}}\left\|C_{t}\cdot\bm{\mathrm{Cov}}\left(\mu_{J_{t},h}\right)\cdot
C_{t}\right\|\right)$
$\displaystyle\geqslant\frac{1}{n}\cdot\exp\left(-\left(1+\frac{8}{(1-\gamma)^{2}}\cdot\frac{\Delta}{D}\right)\right)=n^{-(1+o(1))}.\qed$

###  A.2 Bounds on various probabilities in sparse random graphs

Next, we prove numerous lemmas from Section 6, including Lemmas 6.19, 6.14,
6.4 and 6.17. In the sequel, we study random graphs $\bm{G}$ sampled from
$\mathrm{SBM}(n,d,\lambda)|\bm{\sigma}$ where $\bm{\sigma}$ is a “balanced”
community assignment. In particular, we assume that
$\frac{1}{n}|\left\langle\bm{1},\bm{\sigma}\right\rangle|<O\left\lparen\sqrt{\frac{\log
n}{n}}\right\rparen$. This holds with probability $1$ if $\bm{G}$ is an
Erdős–Rényi graph, and more generally with probability $1-o_{n}(1)$ for
2-community SBMs with nontrivial priors.

######  Lemma A.1.

For any vertex $v$ in $V(\bm{G})$ and $r\geqslant 1$, for
$\eta=\min\left\\{\frac{\varepsilon^{2}}{54},\frac{1}{18}\right\\}$,

$\bm{\mathrm{Pr}}[|B_{r}(v)|\geqslant(d(1+\varepsilon))^{r}]\leqslant\exp\left(-\eta
d\left(1+\frac{\varepsilon}{4}\right)^{r}\right).$

###### Proof.

Consider a Galton-Watson tree $T$ with branching random variable
$\operatorname{Poi}(d(1+o_{n}(1))$. It is well-known (see e.g. [Roc24, Example
4.2.8]) that $\operatorname{Poi}(d)$ stochastically dominates
$\operatorname{Bin}(n-1,\frac{d}{n})$, so one can construct a monotone
coupling between the local neighborhoods of $G$ and the Galton-Watson tree $T$
in the following way. Suppose $\alpha$ is the fraction of vertices $v$ such
that $\bm{\sigma}(v)=+1$. Then, the number of neighbors of a given vertex $v$
is distributed as $\operatorname{Bin}\left(\alpha
n-1,\frac{d+\lambda\sqrt{n}}{n}\right)+\operatorname{Bin}\left((1-\alpha)n,\frac{d-\lambda\sqrt{n}}{n}\right)$,
which is dominated by
$\operatorname{Poi}\left\lparen\alpha\cdot\frac{d+\lambda\sqrt{d}}{2}+(1-\alpha)\cdot\frac{d-\lambda\sqrt{d}}{2}\right\rparen$.
Since $\alpha=\frac{1}{2}\pm O\left\lparen\sqrt{\frac{\log
n}{n}}\right\rparen$, the number of neighbors is stochastically dominated by
$\operatorname{Poi}\left\lparen d\left\lparen
1+o_{n}(1)\right\rparen\right\rparen$. For simplicity of notation, for the
rest of the proof we replace $d(1+o_{n}(1))$ with $d$. Since
$\varepsilon=\Omega(\log d/d)^{1/3}$, we can increase the implicit constant to
ensure that the original tail bound as stated holds.

Let $u$ be the root of $T$. Set $N^{\mathsf{GW}}_{\ell}(u)$ to be the set of
vertices at depth exactly $\ell$ in the Galton-Watson tree, and
$B^{\mathsf{GW}}_{\ell}(u)$ to be the set of vertices at depth at most $\ell$.
By the above monotone coupling, $|B_{L}(v)|$ is stochastically dominated by
$|B^{\mathsf{GW}}_{L}(u)|$, so it suffices to show the relevant tail bound for
$|B_{\ell}^{\mathsf{GW}}(u)|$.
For ease of notation, set $R_{t}=|N^{\mathsf{GW}}_{t}(u)|$ and
$B_{t}=|B^{\mathsf{GW}}_{t}(u)|$. Also let $B_{t}=0$ for $t<0$. Markov’s
inequality implies that for any $s>0$,

$\bm{\mathrm{Pr}}\left[|B_{r}|\geqslant(d(1+\varepsilon))^{r}\right]\leqslant
e^{-s(d(1+\varepsilon))^{r}}\bm{\mathrm{E}}\left[e^{sB_{r}}\right].$

Now, for $t\geqslant 2$, using the recursion $B_{t}=B_{t-1}+R_{t}$, we have

$\displaystyle\bm{\mathrm{E}}\left[e^{sB_{t}}\right]$
$\displaystyle=\bm{\mathrm{E}}\left[e^{sB_{t-1}}\cdot e^{sR_{t}}\right]$
$\displaystyle=\bm{\mathrm{E}}\left[e^{sB_{t-1}}\cdot
e^{d(e^{s}-1)R_{t-1}}\right]$ (Poisson MGF)
$\displaystyle=\bm{\mathrm{E}}\left[e^{sB_{t-2}}\cdot
e^{(d(e^{s}-1)+s)R_{t-1}}\right].$

Define $g:\mathbb{R}_{\geqslant 0}^{2}\to\mathbb{R}_{\geqslant 0}$ by

$g(x,s)=d(e^{x}-1)+s,$

so for any $r\geqslant 1$, $\bm{\mathrm{E}}[e^{sB_{r}}]\leqslant e^{g^{\circ
r}(s,s)}$, where $g^{\circ 1}(x,y)=g(x,y)$ and $g^{\circ(t+1)}(x,y)=g(g^{\circ
t}(x,y),y)$. Now, define $s_{k}=\delta(d+2\delta)^{-k}$ for some
$\delta\geqslant 1/d$ that we shall set later. Then, for any $1\leqslant
t\leqslant r$,

$\displaystyle g(s_{t},s_{r})$ $\displaystyle=d(e^{s_{t}}-1)+s_{r}$
$\displaystyle\leqslant ds_{t}e^{s_{t}}+s_{r}$ $\displaystyle\leqslant
s_{t-1}\cdot\left(\frac{de^{s_{t}}}{d+2\delta}+\frac{s_{r}}{s_{t-1}}\right)$
$\displaystyle\leqslant
s_{t-1}\cdot\left(\frac{de^{s_{t}}}{d+2\delta}+\frac{1}{d+2\delta}\right)$
$\displaystyle\leqslant
s_{t-1}\cdot\left(\frac{d\exp\left(\frac{\delta}{d+2\delta}\right)}{d+2\delta}+\frac{d}{d+2\delta}\right)$
($t\geqslant 1$) $\displaystyle\leqslant s_{t-1}.$

Here, the final inequality follows from the fact that

$\frac{\exp\left(\frac{x}{1+2x}\right)}{1+2x}+\frac{1}{1+2x}\leqslant 1$

for $x\geqslant 1$, which we have applied with $x=\frac{\delta}{d}$. We also
have

$g(s_{0},s_{r})=d(e^{s_{0}}-1)+s_{r}\leqslant d\delta
e^{\delta}+s_{r}\leqslant d\delta e^{\delta}+\delta.$

Consequently,

$\bm{\mathrm{E}}\left[e^{s_{r-1}B_{r}}\right]\leqslant e^{d\delta
e^{\delta}+\delta}.$

Therefore,

$\displaystyle\bm{\mathrm{Pr}}\left[|B_{r}|\geqslant(d(1+\varepsilon))^{r}\right]$
$\displaystyle\leqslant e^{d\delta e^{\delta}+\delta}\cdot
e^{-s_{r-1}(d(1+\varepsilon))^{r}}$ $\displaystyle=\exp\left(d\delta
e^{\delta}+\delta\right)\cdot\exp\left(-\delta\cdot\frac{(d(1+\varepsilon))^{r}}{(d+2\delta)^{r-1}}\right)$
$\displaystyle\leqslant\exp\left(d\delta
e^{\delta}+\delta\right)\cdot\exp\left(-\delta
d\cdot\left(\frac{1+\varepsilon}{1+\frac{2\delta}{d}}\right)^{r}\right).$

Now, choose
$\delta=\min\left\\{\frac{\varepsilon}{4+2\varepsilon},\log\left(1+\frac{\varepsilon}{8}\right)\right\\}$.
Recall that $\varepsilon=\Omega\left(\frac{\log d}{d}\right)^{1/3}$, so this
is indeed at least $1/d$. This implies that
$\frac{1+\varepsilon}{1+\frac{2\delta}{d}}\geqslant 1+\frac{\varepsilon}{2}$.
Furthermore,

$\displaystyle\frac{\exp\left(d\delta
e^{\delta}+\delta\right)\cdot\exp\left(-\delta
d\left(1+\frac{\varepsilon}{2}\right)^{r}\right)}{\exp\left(-\frac{\delta\varepsilon
d}{4+\varepsilon}\left(1+\frac{\varepsilon}{4}\right)^{r}\right)}$
$\displaystyle=\exp\left(d\delta
e^{\delta}+\delta-d\delta\left(\left(1+\frac{\varepsilon}{2}\right)^{r}-\frac{\varepsilon}{4+\varepsilon}\left(1+\frac{\varepsilon}{4}\right)^{r}\right)\right)$
$\displaystyle\leqslant\exp\left(d\delta
e^{\delta}+\delta-d\delta\left(1+\frac{\varepsilon}{2}-\frac{\varepsilon}{4+\varepsilon}\left(1+\frac{\varepsilon}{4}\right)\right)\right)$
$\displaystyle=\exp\left(d\delta
e^{\delta}+\delta-d\delta\left(1+\frac{\varepsilon}{4}\right)\right)$
$\displaystyle=\exp\left(d\delta\left(e^{\delta}+\frac{1}{d}-\left(1+\frac{\varepsilon}{4}\right)\right)\right)$
$\displaystyle\leqslant\exp\left(d\delta\left(e^{\delta}-\left(1+\frac{\varepsilon}{8}\right)\right)\right)\leqslant
1,$

where in the last line we used $\varepsilon\geqslant\frac{8}{d}$. To conclude,
we set

$\displaystyle\eta\coloneqq\frac{\delta\epsilon}{4+\varepsilon}$
$\displaystyle=\frac{\varepsilon}{4+\varepsilon}\cdot\min\left\\{\frac{\varepsilon}{4+2\varepsilon},\log\left(1+\frac{\varepsilon}{8}\right)\right\\}$
$\displaystyle\geqslant\min\left\\{\frac{\varepsilon}{6},\frac{1}{3}\right\\}\cdot\min\left\\{\frac{\varepsilon}{9},\frac{1}{6}\right\\}$
$\displaystyle\geqslant\min\left\\{\frac{\varepsilon^{2}}{54},\frac{1}{18}\right\\}.\qed$

First, observe that Lemma 6.14, restated below, is an immediate corollary of
the above. See 6.14

Now, we proceed to fill in other missing proofs. See 6.4

###### Proof.

As in the proof of Lemma A.1, set $R_{\ell}$ to be the number of vertices at
depth $\ell$ in a Galton-Watson tree with branching random variable
$\operatorname{Poi}(d)$ rooted at $v$. We shall show that

$\bm{\mathrm{Pr}}\left[R_{\ell}\geqslant(d(1+\varepsilon))^{\ell}\cdot\Delta\right]\leqslant\frac{1}{n^{3}}$

for some $\Delta=o(\log n)$ ($\Delta$ is $o(\log n)$ uniformly for all
$\ell$). Given this, we are done by taking a union bound over
$0\leqslant\ell\leqslant n$ and then all $n$ vertices $v$. Again, define

$g(x)=d(e^{x}-1),$

so for any $s>0$,

$\bm{\mathrm{Pr}}\left[R_{\ell}\geqslant(d(1+\varepsilon))^{\ell}\cdot\Delta\right]\leqslant
e^{-s\Delta(d(1+\varepsilon))^{\ell}}\cdot e^{g^{\circ\ell}(s)}.$

Alternately, set

$h(x)=g^{-1}(x)=\log\left(\frac{x}{d}+1\right),$

so we get that for any $q>0$,

$\bm{\mathrm{Pr}}\left[R_{\ell}\geqslant(d(1+\varepsilon))^{\ell}\cdot\Delta\right]\leqslant
e^{-h^{\circ\ell}(q)\Delta(d(1+\varepsilon))^{\ell}}\cdot e^{q}.$

Now, set $q=\log n$ and

$\Delta=\frac{4\log n}{(d(1+\varepsilon))^{\ell}\cdot h^{\circ\ell}(\log n)}.$

Clearly, this yields the $1/n^{3}$ bound claimed earlier. Further, we have

$\min_{\ell\geqslant 0}\left\\{(d(1+\varepsilon))^{\ell}\cdot
h^{\circ\ell}(\log n)\right\\}=\omega(1),$

so $\Delta=o(\log n)$. ∎

The key idea in the proof of Lemma 6.19 is the following observation.

######  Observation A.2.

Let $S\subseteq V$ be any set of vertices in $G$ and $\ell$ be a positive
integer. For any vertex $v\in V$ and conditioning on the induced subgraph on
$S$, we have that $N_{\ell}(v)\setminus S$ is a uniformly random subset of
$V\setminus S$ of size $\lvert N_{\ell}(v)\setminus S\rvert$.

See 6.19

###### Proof of Lemma 6.19.

The idea is that due to Observation A.2 — since the sets $S,T_{1},T$ are all
$o(n)$ in size, we are essentially picking uniformly random small subsets of
vertices on $V$ and checking whether they intersect.

To formalize this, consider growing out the ball around $u$ incrementally. Let
us first introduce some additional notation. Set $\mathcal{L}$ to be the event
that $u$ is $\ell$-light, and let $\mathcal{F}$ be the event in the lemma
statement whose conditional probability we wish to bound:

$\mathcal{F}\coloneqq\mathcal{L}\cap\\{B_{\ell}(u)\cap
T_{i}\neq\varnothing\text{ for }i\in\\{1,2\\}\\}$

For $r\geqslant 1$ and $i\in[2]$, let $\mathcal{E}_{r,i}$ denote the event
that $B_{r}(u)\cap T_{i}\neq\varnothing$ but $B_{r-1}(u)\cap
T_{i}=\varnothing$, that is, $r$ is the smallest radius at which the ball
intersects $T_{i}$. Noting that $\mathcal{E}_{r,i}$ are disjoint events for
fixed $i$, we have

$\bm{\mathrm{Pr}}\left[\mathcal{F}\mid\mathcal{E}\right]=\sum_{r_{1},r_{2}=1}^{\ell}\bm{\mathrm{Pr}}\left[\mathcal{L}\cap\mathcal{E}_{r_{1},1}\cap\mathcal{E}_{r_{2},2}\mid\mathcal{E}\right].$
(16)

In words, we are splitting this into cases depending on when $T_{1}$ and
$T_{2}$ are hit. To complete the proof, we shall bound each of the terms in
this summation by

$\frac{2(d(1+\varepsilon))^{2\ell}\cdot|T_{1}|\cdot|T_{2}|}{n^{2}}.$

Fix $r_{1},r_{2}$ with $r_{1}\leqslant r_{2}$. Let $\mathcal{L}_{r}$ be the
event that $|B_{r}(u)|\leqslant(d(1+\varepsilon))^{\ell}$. We have

$\displaystyle\bm{\mathrm{Pr}}\left[\mathcal{E}_{r_{1},1}\cap\mathcal{E}_{r_{2},2}\cap\mathcal{L}\mid\mathcal{E}\right]$
$\displaystyle\leqslant\bm{\mathrm{Pr}}\left[\mathcal{E}_{r_{1},1}\cap\mathcal{E}_{r_{2},2}\cap\mathcal{L}_{r_{2}}\mid\mathcal{E}\right]$
$\displaystyle\leqslant\bm{\mathrm{Pr}}\left[\mathcal{E}_{r_{1},1}\cap\mathcal{L}_{r_{2}}\mid\mathcal{E}\right]\cdot\bm{\mathrm{Pr}}\left[\mathcal{E}_{r_{2},2}\mid\mathcal{L}_{r_{2}}\cap\mathcal{E}_{r_{1},1}\cap\mathcal{E}\right]$
$\displaystyle\leqslant\bm{\mathrm{Pr}}\left[\mathcal{E}_{r_{1},1}\mid\mathcal{L}_{r_{1}}\cap\mathcal{E}\right]\cdot\bm{\mathrm{Pr}}\left[\mathcal{E}_{r_{2},2}\mid\mathcal{L}_{r_{2}}\cap\mathcal{E}_{r_{1},1}\cap\mathcal{E}\right].$

Let us start by bounding the first of these two probabilities; refer to Figure
4 for a depiction of the sets involved. For convenience, we will denote
$V^{\prime}=V\setminus(T_{2}\cup S)$. Suppose that $B_{r_{1}-1}(u)$,
$|N_{r_{1}}(u)|$ and $|N_{r_{1}}(u)\cap V^{\prime}|$ were fixed in a way that
$B_{r_{1}-1}(u)$ does not intersect $T_{1}$ or $T^{\prime}$, and
$\mathcal{L}_{r_{1}}$ is satisfied. Then, $N_{r_{1}}(u)\cap V^{\prime}$ is in
fact a uniformly random subset of $V^{\prime}\setminus B_{r_{1}-1}(u)$ of the
appropriate size. Since $T_{1}$ is assumed to be contained in $V^{\prime}$, it
follows that

$\bm{\mathrm{Pr}}\left[\mathcal{E}_{r_{1},1}\mid\mathcal{L}_{r_{1}}\cap\mathcal{E}\right]\leqslant\frac{\bm{\mathrm{E}}\left[|N_{r_{1}}(u)|\Big{|}\mathcal{L}_{r_{1}}\cap\mathcal{E}\right]\cdot|T_{1}|}{n-o(n)}\leqslant\frac{2(d(1+\varepsilon))^{\ell}\cdot|T_{1}|}{n}.$

Similarly, we also get that

$\bm{\mathrm{Pr}}\left[\mathcal{E}_{r_{2},2}\mid\mathcal{L}_{r_{2}}\cap\mathcal{E}_{r_{1},1}\cap\mathcal{E}\right]\leqslant\frac{2(d(1+\varepsilon))^{\ell}\cdot|T_{2}|}{n}.$

Plugging these two bounds into (16), we get that

$\bm{\mathrm{Pr}}\left[\mathcal{F}\mid\mathcal{E}\right]\leqslant\frac{2\ell^{2}\cdot(d(1+\varepsilon))^{2\ell}\cdot|T_{1}|\cdot|T_{2}|}{n^{2}},$

as claimed. ∎

See 6.17

The key observation for this proof is the following.

######  Observation A.3.

Let $S\subseteq V$ be a (small) subset of vertices in $G$. Consider a partial
conditioning of the edges for which

  * •

the edges within $S$ are arbitrarily conditioned on.

  * •

for any potential edge $e$ from $S$ to $S^{c}$, either $e$ is not conditioned
on at all, or is conditioned to be absent.

Now, fix some vertex $u$, and suppose we grow out a radius $r$ ball from $v$,
conditioned on it not intersecting $S$. Then, this is equivalent to growing
out a radius $r$ ball from $v$ within a smaller completely random graph on
$V\setminus S$, and then adding back the edges corresponding to $S$, with a
further conditioning that there are no edges between $B_{r-1}(u)$, the
interior vertices of the ball, and $V\setminus B_{r}(u)$ (which, in
particular, includes $S$).

Consequently, any monotonically nondecreasing function of the sizes of
neighborhoods in the conditioned graph are stochastically dominated by their
versions without conditioning. In particular, the random variable $\ell(v)$ in
the conditioned graph is stochastically dominated by $\ell(v)$ in $G(n,d/n)$.

###### Proof of Lemma 6.17.

We will upper bound the probability inductively; the base case immediately
follows from Lemma A.1.

Let $\mathcal{A}_{r}$ denote the event that $\ell(u_{i})=\ell_{i}$ for every
$i\in[r]$, i.e. the first $r$ balls are heavy. Further, let $\mathcal{B}_{r}$
denote the event that $B_{\ell_{i}}(u_{i})\cap
B_{\ell_{j}}(u_{j})=\varnothing$ for all distinct $i,j\in[r]$, i.e. the first
$r$ balls are pairwise disjoint. Noting that
$\mathcal{B}_{r}=\mathcal{B}_{r-1}\cap\\{B_{\ell_{r}}(u_{r})\cap
B_{\ell_{i}}(u_{i})=\varnothing\,\,\forall i\in[r-1]\\}$, we have

$\displaystyle\bm{\mathrm{Pr}}\left[\mathcal{A}_{r}\cap\mathcal{B}_{r}\right]$
$\displaystyle=\bm{\mathrm{Pr}}[\mathcal{A}_{r-1}\cap\mathcal{B}_{r-1}]\cdot\bm{\mathrm{Pr}}\left[B_{\ell_{r}}(u_{r})\cap
B_{\ell_{i}}(u_{i})=\varnothing\,\,\forall
i\in[r-1]\Big{|}\mathcal{A}_{r-1}\cap\mathcal{B}_{r-1}\right]$
$\displaystyle\quad\quad\cdot\bm{\mathrm{Pr}}\left[\ell(u_{r})=\ell_{r}\Big{|}\mathcal{A}_{r-1}\cap\mathcal{B}_{r}\right]$
$\displaystyle\leqslant\prod_{i\in[r-1]}\exp(-\eta
d(1+\varepsilon)^{\ell_{i}})\cdot\bm{\mathrm{Pr}}\left[\ell(u_{r})=\ell_{r}\Big{|}\mathcal{A}_{r-1}\cap\mathcal{B}_{r}\right]$
$\displaystyle\leqslant\prod_{i\in[r]}\exp(-\eta
d(1+\varepsilon)^{\ell_{i}}),$

where in the last line we have used Observation A.3 and Lemma A.1 with
$S=\bigcup_{i=1}^{r-1}B_{\ell_{i}}(u_{i})$. ∎