Factor models on locally tree-like graphs

Introduction

Let $G=(V,E)$ be a finite undirected graph, and $\mathscr{X}$ a finite alphabet of spins. A factor model on $G$ is a probability measure on the space of (spin) configurations $\underline{\sigma}\in\mathscr{X}^{V}$ of form

and to determine its value. [In the literature, $\phi(\beta,B)$ is also referred to as the “free entropy density” or “pressure.”]

The primary example we consider is the Potts model for a system of interacting spins on a graph. Formally, the $q$-Potts model on $G$ with inverse temperature $\beta$ and magnetic field $B$ is the probability measure on $\mathscr{X}^{V}=[q]^{V}$ (with $[q]\equiv\{1,\ldots,q\}$) given by

For $\beta>0$ the system favors monochromatic edges and is said to be ferromagnetic, while for $\beta<0$ the system favors edge disagreements and is said to be anti-ferromagnetic; the magnetic field $B$ biases vertices toward the distinguished spin $1$. The $q$-Potts model generalizes the Ising model which corresponds to the case $q=2$. In analogy with the Potts model, in the general factor model setting we continue to refer to $\beta$ as the interaction or temperature parameter and to $B$ as the magnetic field.

Potts models have been intensively studied in statistical mechanics because of their key role in the theory of phase transitions MR641370, critical phenomena MR1227790 and conformally invariant scaling limits MR2280251. As demonstrated, for instance, in MR2875752 for the Ising model, determining the limit (2) plays a key role in characterizing the asymptotic structure of the measures $\nu^{\beta,B}_{G_{n}}$ in the thermodynamic limit. Potts models are also of great interest in combinatorics: recall in fact that the partition function admits a random-cluster representation (MR0359655; MR2243761; see also Section 4.2), which at $B=0$ reads

with $k(F)$ denoting the number of connected components induced by the subset of edges $F\subseteq E$; cf. (53). Up to a multiplicative constant this coincides with the Tutte polynomial $T_{G}(x,y)$ of $G$ evaluated at $x=1+q(e^{\beta}-1)^{-1}$, $y=e^{\beta}$; see, for example, MR2187739.

Mathematical statistical mechanics has focused so far on specific graph sequences $G_{n}$, for example, on finite exhaustions of the rectangular grid or other regular lattices in $d$ dimensions with $d$ fixed. Under mild conditions on the sequence, existence of the free energy density is a consequence of the following well-known argument (see, e.g., MR0289084, Proposition 2.3.2): each graph $G_{n}$ can be decomposed into smaller blocks by deleting a collection of edges whose number is negligible in comparison with the volume. Consequently the sequence $\log Z_{G_{n}}$ is approximately sub-additive in $n$, implying existence of the limit; see MR0137800.

so that as $\lambda$ increases the measure becomes more biased toward the larger independent sets (and we write $B\equiv\log\lambda$ for the magnetic field). Due to the hard constraint preventing neighboring $1$s, this system always has anti-ferromagnetic interactions and is of significant interest in computer science. The independent set decision problem is np-complete (via the clique decision problem Cook1971CTP800157805047; MR0378476). As $\lambda$ increases the measure $\nu^{\lambda}_{G}$ becomes increasingly concentrated on the maximal independent sets; the optimization problem of finding such sets is np-hard MR584512 and hard to approximate (Zuckerman2006LDE11325161132612 and references therein). The problem of counting independent sets [i.e., computing $Z_{G}(1)$] for graphs of maximum degree $\Delta$ is #p-complete for $\Delta\geq 3$ (MR1791090 and references therein). Although there exists a ptas (polynomial-time approximation scheme) for $Z_{G}(\lambda)$ for $\lambda$ below a certain “uniqueness threshold” MR2277139, a series of previous works (see MR2475668; 101109FOCS201034; springerlink101007978364222935048 and references therein) gave strong evidence that computation is hard for any $\lambda$ above this threshold. This question was resolved simultaneously in the subsequent works arXiv12032226; arXiv12032602, with arXiv12032602 building on methods from this paper.

There is no good argument for why the limit (2) exists; the heuristic replica or cavity methods compute this limit starting from the postulate that it exists. A significant breakthrough was achieved by the interpolation method first developed by Guerra and Toninelli MR1930572 for the Sherrington–Kirkpatrick model from spin-glass theory, and then generalized to a number of statistical physics models on sparse graphs MR1972121; MR2025238; MR2095932 and related constraint satisfaction problems MR2743259. This method establishes super-additivity of $\log Z_{G_{n}}$ which implies existence of the limit (2). Unfortunately, this approach appears limited to models with repulsive interactions, that is, in which higher weight is given to configurations in which neighboring vertices take different values. In particular, it does not apply to the ferromagnetic Potts model. This is especially puzzling because the heuristic physics predictions do not distinguish between the two cases, and there is no fundamental reason why the limit should be computable in one case and not in the other. Further, this interpolation method only applies to very restricted classes of graph sequences (typically, uniformly random given the degree sequence); notably, existence of the limit is not proved for deterministic graph sequences. Finally, the method gives no way to actually compute the limit, although interpolation has been used to prove upper bounds MR1972121; MR2025238; MR2095932.

In this paper we follow a different approach relying only on local weak convergence of the graph sequence $(G_{n})_{n\geq 1}$ to some limiting (random) tree. The general idea is that the corresponding factor models (1) must converge (passing to a subsequence as needed), to a Gibbs measure on the limiting tree; the task then “reduces” to the one of identifying the correct limit. This is still a substantial challenge because, in general, there is an uncountable number of “candidate” Gibbs measures for the limit. Nevertheless, this program was carried through in MR2650042 for Ising models on graphs converging locally to a Galton–Watson tree, under a “uniform sparsity” assumption (Definition 1.3), on the degree distribution. (It is further assumed in MR2650042 that the distribution has finite second moment; this condition was relaxed in MR2733399, thereby handling the case of power law graphs.) The result of MR2650042; MR2733399 provides also a fairly explicit expression $\Phi(\beta,B)$ for the free energy density, defined solely in terms of the limiting tree. This expression coincides with the so-called “Bethe prediction” of statistical physics, derived earlier for random graphs with given degree distribution using the “replica” or “cavity” methods.

We develop this approach here in more generality. Rather than considering a specific model such as the Ising, we establish results for general abstract factor models satisfying mild regularity conditions [see (H1) below], covering in particular the Potts and independent set models. We also make no distributional assumptions on the graphs $G_{n}$ or the limiting random tree, other than some integrability conditions [see Definition 1.3 and (H2) below]. In this setting we develop a general interpolation scheme (Theorem 1.15) which, under appropriate assumptions, bounds differences $\phi_{n}(\beta,B)-\phi_{n}(\beta_{0},B_{0})$ in the limit $n\to\infty$ by differences $\Phi(\beta,B)-\Phi(\beta_{0},B_{0})$ for $\Phi$ a functional defined solely in terms of the limiting tree; see (13). We refer the reader to MR2023650 for a discussion of the computation of limits of finite large random structures through optimization procedures on the limiting infinite structure. Although we continue to refer to this $\Phi(\beta,B)$ as the “Bethe prediction,” we remark that it is a considerable generalization of earlier formulas obtained in the special case of Galton–Watson trees by statistical physics methods. It is defined as the evaluation of the “Bethe free energy functional” (10) at a specific Gibbs measure on the limiting tree, and corresponds to what physicists call the “replica symmetric solution”: whereas it is expected to hold in the high-temperature regime (i.e., with small enough interactions), for many factor models it is incorrect at low temperature. However, we will show that in “uniqueness regimes,” where the set of Gibbs measures on the limiting tree corresponding to the factor model specification $\underline{\psi}$ is a singleton, the upper and lower bounds of Theorem 1.15 match to completely verify the Bethe prediction (Theorem 1.16).

Theorem 1.15 can give useful bounds even beyond uniqueness regimes. As an illustration, we study the Potts model in the case that $G_{n}$ converges locally to the $d$-regular tree ${{\textsf{T}}_{d}}$. In Theorem 1.11 we explicitly characterize the nonuniqueness regime of this model and use Theorem 1.15 to give bounds for $\phi_{n}(\beta,B)$ within this regime. In a subsequent work arXiv12075500 we prove that in this setting, $\phi(\beta,B)$ exists and matches the lower bound of Theorem 1.11. We also compute there the asymptotic free energy $\phi(\lambda)$ (all $\lambda\geq 0$) for the independent set model on $d$-regular bipartite graphs. In contrast, for generic nonbipartite $G_{n}$ the consensus in physics is for a full replica symmetry breaking for large enough $\lambda$, and consequently there does not exist even a heuristic prediction for the free energy density in this regime.

As mentioned above, the Bethe prediction $\Phi(\beta,B)$ is the evaluation of the Bethe free energy functional at a specific Gibbs measure on the limiting tree. This Gibbs measure has a characterization in terms of “messages” $h_{x\to y}\equiv h_{(T,x\to y)}$ defined on the directed edges $x\to y$ of each tree $T$, such that the entire collection of messages is a fixed point of a certain “belief propagation” or “Bethe recursion” (1.6). Motivated by the finite-graph optimization of MR2246363, we provide a variational characterization of the Bethe prediction (Theorem 1.18) which is of independent interest. In particular, this formulation suggests nontrivial connections with large deviation principles.

Let $G_{n}=(V_{n},E_{n})$ ($n\geq 1$) be a sequence of random graphs, and let $I_{n}$ be a vertex chosen uniformly at random from $V_{n}$. We say $G_{n}$ converges locally (weakly) to the random tree $T$ if for each $t\geq 0$, $B_{t}(I_{n})$ converges in law to ${T}^{t}$ in the space ${\mathcal{G}_{{\bullet}}}$. We say in this case that the $G_{n}$ are locally tree-like.

We will make repeated use of the fact that any local weak limit of graph sequences satisfies the “unimodularity” or “mass-transport” property whose definition we recall here; for a detailed account, see MR2354165. Let ${\mathcal{G}_{{\bullet}{\bullet}}}$ denote the space of isomorphism classes of bi-rooted, connected graphs with a distinguished ordered pair, denoted $(G,i,j)$ (we do not require $i\sim j$); ${\mathcal{G}_{{\bullet}{\bullet}}}$ is metrizable in a similar manner as ${\mathcal{G}_{{\bullet}}}$.

A Borel probability measure $\mu$ on ${\mathcal{G}_{{\bullet}}}$ is said to be unimodular if it obeys the mass-transport principle,

We say that $\mu$ is involution invariant if (1.2) holds when restricted to $f$ supported only on those $(G,x,y)$ with $x\sim y$.

A measure $\mu$ on $\mathcal{G}$ is involution invariant if and only if it is unimodular (MR2354165, Proposition 2.2). Unimodularity corresponds to “indistinguishability of the root;” the concept first appeared in MR1873300 where it was observed that local weak limits of graph sequences must be unimodular (MR1873300, Section 3.2). The converse of this implication remains a well-known open question; see MR2354165.

The graph sequence $G_{n}$ is uniformly sparse if the $D_{I_{n}}$ are uniformly integrable, that is, if

We assume throughout that $G_{n}$ ($n\geq 1$) is a uniformly sparse graph sequence converging locally weakly to the random tree $T$ of (unimodular) law $\mu$ such that the root degree $D_{o}$ is nonzero with positive $\mu$-probability; this entire setting is hereafter denoted $G_{n}\to_{\mathit{lwc}}\mu$. In this setting we will describe general conditions under which the asymptotic free energy $\phi(\beta,B)$ for the factor model (1) exists and agrees with the “Bethe energy prediction,” which we now describe. [If the sequence of random graphs $G_{n}$ is such that $G_{n}\to_{\mathit{lwc}}\mu$ for almost every realization of the sequence—as is the case for Erdös–Rényi random graphs or random graphs with given degree distribution (see, e.g., MR2643563, Propositions 2.5 and 2.6)—then our results apply instead to the a.s. limit of $n^{-1}\log Z_{n}(\beta,B)$.]

(where $o$ corresponds to $x$ on the left-hand side and to $y$ on the right-hand side), so in particular $\mu^{\uparrow}$ and $\mu^{\downarrow}$ are mutually absolutely continuous.

The message space is the space $\mathcal{H}\equiv\mathcal{H}_{\mu}$ of measurable functions

taken up to $\mu^{\uparrow}$-equivalence.

For $T\in{\mathcal{T}_{\bullet}}$ and $h\in\mathcal{H}$, let

the log-partition function of the star graph ${T}^{1}$ with boundary conditions $h$ [see Figure 1(a)] and

half the log-partition function on $D_{o}$ disjoint edges with boundary conditions $h$; see Figure 1(b). (See Definition 1.8 below for a detailed discussion of boundary conditions.)

We take the usual convention that the empty sum is zero, and the empty product is one, so $\Phi_{T}=\log(\sum_{\sigma}{\bar{\psi}}(\sigma))$ in case $T={T}^{0}$. Although we suppress it from the notation, in the above equations $\underline{\psi}$ and $h$ are taken to be evaluated at $(\beta,B)$. The Bethe free energy functional on $\mathcal{H}$ for the factor model (1) on $G_{n}\to_{\mathit{lwc}}\mu$ is defined by

provided the expectation exists; see Lemma 2.2.

The belief propagation or Bethe recursion is the mapping ${\textsf{BP}}\equiv{\textsf{BP}}^{\beta,B}\colon\;\mathcal{H}\to\mathcal{H}$,

The Bethe prediction is that the asymptotic free energy $\phi(\beta,B)$ of (2) exists and equals

In the case that the recursion (12) has multiple solutions ($|\mathcal{H}^{\star}_{\mu}(\beta,B)|>1$), the Bethe prediction is defined to be the supremum of $\Phi(\beta,B,h^{\star})$ over admissible fixed points $h^{\star}$. While in the abstract factor model setting all fixed points are admissible, in specific models typically there are “natural” criteria restricting the set of admissible fixed points. We will demonstrate this in the Ising and Potts models where restrictions are imposed by monotonicity and symmetry considerations.

The rationale behind the Bethe recursions and Bethe prediction is explained in detail in MR2643563, Section 3; see also MR2518205. In brief, solutions to the Bethe recursions correspond to consistent “boundary laws” for the factor model on tree-like graphs; for further details, see Remark 1.13 below. When $G$ is a finite tree, and $\mu_{G}$ is the law of $(G,I)$ for $I$ a uniform element of $V$ (here $\mu_{G}$ is a measure on ${\mathcal{T}_{\bullet}}$, but not necessarily unimodular), the Bethe recursions have a unique solution, given by the so-called “standard message set;” see MR2643563, Remark 3.5. In this setting it holds exactly (see MR2643563, Proposition 3.7) that

The following is a terminology which we adopt throughout the paper:

If $G$ is any graph and $U$ a sub-graph, the external boundary $\partial U$ of $U$ is the set of vertices of $G\setminus U$ adjacent to $U$. Let $U^{+}$ denote the sub-graph of $G$ induced by the vertices in $V_{U}\cup\partial U$. For $U$ finite (so $U^{+}$ is finite, since $G$ is locally finite), and $\nu^{\ddagger}$ a measure on $\mathscr{X}^{\partial U}$, the factor model on $U$ with $\nu^{\ddagger}$ boundary conditions is the probability measure on configurations $\underline{\sigma}_{U}\in\mathscr{X}^{V_{U}}$ given by

2 Application to Ising, Potts and independent set

Before formally stating our main theorem for general factor models, we mention its consequences in some models of interest: we verify the Bethe prediction for the ferromagnetic Ising model at all temperatures, the ferromagnetic Potts model with field $B\geq 0$ in uniqueness regimes, and the independent set model with low fugacity $\lambda$.

The Ising model is the Potts model (3) with $q=2$. For convenience we use the equivalent formulation which takes $\mathscr{X}=\{\pm 1\}$ and defines the probability measure on $\mathscr{X}^{V}$

For the Ising model (15) on $G_{n}\to_{\mathit{lwc}}\mu$,

for $\beta\geq 0$, $B>0$. Also $\phi(\beta,B)=\phi(\beta,-B)$ and $\phi(\beta,0)=\lim_{B\to 0}\phi(\beta,B)$.

2.2 Potts model

Throughout the remainder let $(\beta_{0},B_{0})\leq(\beta_{1},B_{1})$, where $\leq$ means coordinate-wise less than or equal to. An interpolation path is a piecewise linear path, with each piece parallel to a coordinate axis, increasing from $(\beta_{0},B_{0})$ to $(\beta_{1},B_{1})$ with respect to the partial order $\leq$.

For the Potts model (3) with $q>2$ and $\beta,B\geq 0$ on $G_{n}\to_{\mathit{lwc}}\mu$, the following hold (with $\Phi\equiv\Phi_{\mu}$, $\mathcal{R}\equiv\mathcal{R}_{\mu}$):

If there exists an interpolation path contained in $\mathcal{R}$ joining $(\beta,B)$ and $\mathcal{R}_{\infty}$, then

We obtain more explicit results when the limiting tree is the $d$-regular tree ${{\textsf{T}}_{d}}$.

For the Potts model (3) with $q>2$ and $\beta,B\geq 0$ on $G_{n}\to_{\mathit{lwc}}{{\textsf{T}}_{d}}$, the following hold (with $\Phi\equiv\Phi_{{{\textsf{T}}_{d}}}$, $\mathcal{R}\equiv\mathcal{R}_{{{\textsf{T}}_{d}}}$, and $\mathcal{R}_{\neq}\equiv\{\beta,B\geq 0\}\setminus\mathcal{R}$):

2.3 Independent set model

We consider the independent set model (4) in the regime of low fugacity. For $\ddagger\in\{0,1\}$ let $\bar{h}^{t,\ddagger}_{T}\equiv\bar{h}^{t,\ddagger,\lambda}_{T}$ denote the root marginal on ${T}^{t}$ with $\ddagger$ boundary conditions on $\partial{T}^{t}$: that is, $\bar{h}^{t,1}_{T}$ (resp., $\bar{h}^{t,0}_{T}$) is calculated conditional on the event of being fully occupied (unoccupied) at level $t+1$ of $T$. Let $\bar{h}^{\ddagger}_{T}\equiv\lim_{t\to\infty}\bar{h}^{2t-1,\ddagger}_{T}$ (existence of the limits $\bar{h}^{0}_{T},\bar{h}^{1}_{T}$ for the independent set model follows from anti-monotonicity; see Section 2.4). We then define messages $h^{\ddagger}\in\mathcal{H}_{\mu}$ by $h^{\ddagger}_{x\to y}=\bar{h}^{\ddagger}_{{T}_{{x\to y}}}$, and let

denote the uniqueness threshold. For $T\in{\mathcal{T}_{\bullet}}$ we write

(where the limit is taken over cutsets $\Pi$ of $T$ with distance $|\Pi|$ from the root tending to infinity) for the branching number of $T$; see MR1062053, Section 2.

Consider the independent set model (4) on $G_{n}\to_{\mathit{lwc}}\mu$, and write $\lambda_{c}\equiv\lambda_{c,\mu}$.

If $\lambda<\lambda_{c}$ and the function $\lambda\mapsto h^{0,\lambda}=h^{1,\lambda}$ has total variation bounded by a deterministic constant on $[0,\log\lambda]$, then

which converges to $\phi(\lambda_{c})$ as $\lambda\uparrow\lambda_{c}$.

If $\operatorname{br}T_{x\to y}\leq\Delta-1$ $\mu^{\uparrow}$-a.s. for $\Delta$ a deterministic constant, then (17) holds for $\lambda<\lambda_{c}$ with $\lambda(\Delta-2)<1$.

If $\mu=\delta_{{{\textsf{T}}_{d}}}$, then (17) holds for $\lambda\leq\lambda_{c}$.

For the $d$-regular tree ${{\textsf{T}}_{d}}$, the uniqueness threshold $\lambda_{c}(d)$ is $(d-1)^{d-1}/(d-2)^{d}$ (see MR844469, Section 2), and MR2277139, Theorem 2.3, shows that ${{\textsf{T}}_{d}}$ has the lowest value of $\lambda_{c}$ among trees with maximum degree at most $d$. The identity (17) has been proved in the case that the $G_{n}$ are random $d$-regular graphs MR2373815; MR2462251. It is also suggested by Weitz’s ptas for $Z_{G}(\lambda)$ on a finite graph $G$ of maximum degree $\Delta$ and with $\lambda<\lambda_{c}(\Delta)$ (MR2277139, Corollary 2.8). For $\mu$ a unimodular measure on ${\mathcal{T}_{\bullet}}$ giving a local tree approximation to $G$ (in the sense of Definition 1.1), $\lambda_{c,\mu}$ is often an improvement over $\lambda_{c}(\Delta)$, making it possible to compute $\phi(\lambda)$ above $\lambda_{c}(\Delta)$ provided (H3B) can be verified. In arXiv12032602 the interpolation scheme of Theorem 1.12 is refined to give a verification of the Bethe prediction on locally tree-like $d$-regular bipartite graphs for all $\lambda>0$; this result is then leveraged to show inapproximability of the hard-core partition function on $d$-regular graphs above $\lambda_{c}(d)$.

3 Results for general factor models

We now state our results for the factor model (1). With the convention $\log 0\equiv-\infty$, let $\log\psi\equiv\xi$ and $\log{\bar{\psi}}\equiv{\bar{\xi}}$, and impose the following regularity condition:

For any $\sigma\in\mathscr{X}$, ${\bar{\xi}}^{B}(\sigma)$ is continuously differentiable in $B$. For any $\sigma,\sigma^{\prime}\in\mathscr{X}$, $\xi^{\beta}(\sigma,\sigma^{\prime})$ is either identically $-\infty$ over all $\beta$, or finite and continuously differentiable in $\beta$.

Recalling Definition 1.4 of the message space $\mathcal{H}\equiv\mathcal{H}_{\mu}$, for $h\in\mathcal{H}_{\mu}$ we can define $\bar{h}\colon\;{\mathcal{T}_{\bullet}}\to\Delta_{\mathscr{X}}$ up to $\mu$-equivalence by

In particular, if $h\in\mathcal{H}^{\star}_{\mu}(\beta,B)$ and $T\in{\mathcal{T}_{\bullet}^{+}}$, then comparing (18) with (1.6) gives

independently of the choice of $j\in\partial o$. From now on, for $h\in\mathcal{H}_{\mu}$, we will write $h\in\mathcal{H}^{\star}$ to indicate that $h^{\beta,B}\in\mathcal{H}^{\star}_{\mu}(\beta,B)$ for $(\beta,B)$ in the range being considered.

The elements of $\mathcal{H}^{\star}$ are consistent with the recursion structure of the tree in the following precise sense: for $T\in{\mathcal{T}_{\bullet}}$ and $U$ a finite connected sub-graph of $T$, consider the factor model $\nu^{h}_{U,T}$ on $U$ with boundary conditions $\sigma_{v}\sim h_{v\to p(v)}$ independently for $v\in\partial U$, where $p(v)$ denotes the (necessarily unique) neighbor of $v$ inside $U$. Then the marginal of $\nu^{h}_{{T}^{t},T}$ on ${T}^{t-1}$ is exactly the factor model $\nu^{\scriptsize{{\textsf{BP}}}h}_{{T}^{t-1},T}$ on ${T}^{t-1}$ with boundary conditions $\sigma_{u}\sim({\textsf{BP}}h)_{u\to p(u)}$ independently for $u\in\partial{T}^{t-1}$, including any $u$ which are leaves of ${T}^{t}$. This statement remains valid if $\partial{T}^{t}$ or even $\partial{T}^{t-1}$ is empty, since if $\partial{T}^{t}=\varnothing$ then $\nu^{h}_{{T}^{t},T}$ is simply $\nu_{T}$ as defined by (1). Continuing the recursion up the tree, we see that $h\in\mathcal{H}^{\star}$ implies that the marginal law of $\sigma_{o}$ will be $\bar{h}_{T}$ as defined by (18). From this it is easy to see that the measures $\nu^{h}_{U,T}$ form a consistent family of finite-dimensional marginals (see Figure 5), so by the Kolmogorov consistency theorem they uniquely determine a probability measure $\nu_{T}\equiv\nu^{h}_{T}$ belonging to $\mathscr{G}_{T}$, the set of Gibbs measures (or Markov random fields) associated to the specification $\underline{\psi}\equiv(\psi,{\bar{\psi}})$ on $T$. Strictly speaking the term “Gibbs measures” refers to the case $\psi>0$, but we will follow common practice and say Gibbs measures also for the general case. For the general theory of Gibbs measures see, for example, MR956646. (In fact this mapping is one-to-one, e.g., by Remark 2.3 below.) Each $\nu_{T}$ belongs to a special class of measures in $\mathscr{G}_{T}$ which are called Markov chains or splitting Gibbs measures in the literature, and the entire collection $(\nu_{T})_{T\in{\mathcal{T}_{\bullet}}}$ arising from $h\in\mathcal{H}^{\star}_{\mu}$ has a consistency property which leads us to term them “unimodular Markov chains” or “Bethe Gibbs measures;” see Section 2.3.

Note that if $G_{n}\to_{\mathit{lwc}}\mu$ and $\psi>0$, then (H2) holds trivially by the assumption of uniform sparsity. We will in fact justify our interpolation scheme under a weaker assumption than (H2); for the exact condition see (H2β), (H2B) in Section 2.2.

We will deduce the results of Section 1.2 from the abstract interpolation method given by Theorem 1.15 below, which bounds differences of $\phi(\beta,B)$ by differences of $\Phi(\beta,B,h)$ ($h\in\mathcal{H}^{\star}$) when the limiting expectation of a certain edge or vertex functional in the finite graph (capturing resp. $\partial_{\beta}\phi_{n}$ or $\partial_{B}\phi_{n}$) is bounded by the expectation of an analogous functional on the infinite tree.

To be more precise, recall that $I_{n}$ denotes a uniformly random vertex of $V_{n}$. Let $\langle\cdot\rangle^{\beta,B}_{n}$ denote expectation with respect to $\nu_{G_{n},\underline{\psi}}$, conditioned on $G_{n}$. For $h\in\mathcal{H}^{\star}_{\mu}(\beta,B)$ and $T\in{\mathcal{T}_{\bullet}}$, let $[\![]\!]^{h,\beta,B}_{T}$ denote expectation with respect to $\nu^{h}_{T}$ (as defined in Remark 1.13), conditioned on $T$, and define

The left-hand side expressions are the derivatives $\partial_{\beta}\phi_{n}$, $\partial_{B}\phi_{n}$ (Lemma 2.1). The right-hand side expressions are the infinite-tree analogues, which, as we will show in Proposition 2.4, may be thought of as derivatives in $\beta$ and $B$ of $\Phi_{\mu}$.

the $\nu^{h}_{T}$-probability (averaged over $T\sim\mu$) that the root spin takes value $1$ and

the $\nu^{h}_{T}$-expectation (averaged over $T\sim\mu$) of half the number of edge agreements incident to the root.

For interpolation in $\beta$ on a compact interval $[\beta_{0},\beta_{1}]$ using some particular $h\in\mathcal{H}^{\star}$, we require the following regularity condition on $h$:

On $[\beta_{0},\beta_{1}]$, for all $\sigma\in\mathscr{X}$ it holds $\mu^{\uparrow}$-a.s. that the function $\beta\mapsto h^{\beta}_{x\to y}(\sigma)$ is continuous with total variation in $\beta$ bounded by a deterministic constant depending only on $\beta_{0},\beta_{1}$.

Likewise for interpolation in $B$ on a compact interval $[B_{0},B_{1}]$ using $h\in\mathcal{H}^{\star}$ we require

On $[B_{0},B_{1}]$, for all $\sigma\in\mathscr{X}$ it holds $\mu^{\uparrow}$-a.s. that the function $B\mapsto h^{B}_{x\to y}(\sigma)$ is continuous with total variation in $B$ bounded by a deterministic constant depending only on $B_{0},B_{1}$.

The condition of boundedness in total variation is implied for example whenever the functions $h$ are (anti-)monotone in the interpolation parameter.

Let $\underline{\psi}\equiv(\psi,{\bar{\psi}})$ specify a factor model (1) on $G_{n}\to_{\mathit{lwc}}\mu$ such that (H1) and (H2) are satisfied.

If on $[\beta_{0},\beta_{1}]$ we have $h\in\mathcal{H}^{\star}$ satisfying (H3β), and

then $\limsup_{n\to\infty}[\phi_{n}(\beta_{1},B)-\phi_{n}(\beta_{0},B)]\leq\Phi(\beta_{1},B,h)-\Phi(\beta_{0},B,h)$.

If on $[B_{0},B_{1}]$, we have $h\in\mathcal{H}^{\star}$ satisfying (H3B), and

then $\limsup_{n\to\infty}[\phi_{n}(\beta,B_{1})-\phi_{n}(\beta,B_{0})]\leq\Phi(\beta,B_{1},h)-\Phi(\beta,B_{0},h)$.

The same results hold if all inequalities are reversed, replacing limit superior with inferior.

Conditions (20), (21) (and their reverses) are automatically verified in the following special case, where we recall that $\mathscr{G}_{T}$ denotes the set of Gibbs measures associated to the specification $\underline{\psi}$ on $T$; cf. Remark 1.13:

Let $\underline{\psi}\equiv(\psi,{\bar{\psi}})$ specify a factor model (1) on $G_{n}\to_{\mathit{lwc}}\mu$ satisfying (H1) and (H2). We say that uniqueness holds if $\mathscr{G}_{T}$ at $(\beta,B)$ consists of a single measure $\nu_{T}$, $\mu$-a.s. In this case, $\mathcal{H}^{\star}_{\mu}(\beta,B)$ is a singleton.

If on $[\beta_{0},\beta_{1}]\times\{B\}$ uniqueness holds and the unique element $h\in\mathcal{H}^{\star}$ satisfies (H3β), then

If on $\{\beta\}\times[B_{0},B_{1}]$ uniqueness holds and the unique element $h\in\mathcal{H}^{\star}$ satisfies (H3B), then

Uniqueness for $\mathscr{G}_{T}$ corresponds to the vanishing effect of boundary conditions on $\partial{T}^{t}$ as $t\to\infty$ (MR956646, Chapter 7). Dobrushin’s uniqueness theorem (see, e.g., MR543198) gives a sufficient condition for uniqueness to hold, together with a bound on the rate of convergence of the root marginal in ${T}^{t}$ to the limit as $t\to\infty$. Note that if the convergence rate is uniform in $\beta,B$ then the continuity required in (H3β) and (H3B) immediately follows. We will obtain continuity in uniqueness regimes via a different route, making use of certain monotonicity properties; see the proof of Theorem 1.9.

3.2 Variational principle

The local polytope $\mathcal{H}_{\operatorname{loc}}\equiv\mathcal{H}_{\operatorname{loc},\mu}$ is the space of measurable functions

taken up to $\mu^{\uparrow}$-equivalence, such that:

$\mathbf{h}_{xy}(\sigma,\sigma^{\prime})=\mathbf{h}_{yx}(\sigma^{\prime},\sigma)$ for all $\sigma,\sigma^{\prime}\in\mathscr{X}$, and

for $T\in{\mathcal{T}_{\bullet}^{+}}$, the one-point marginal $\bar{h}_{x}(\sigma)\equiv\bar{h}_{(T,x)}(\sigma)\equiv\sum_{\sigma_{y}}\mathbf{h}_{xy}(\sigma,\sigma_{y})$ is well-defined, that is, does not depend on the choice of $y\in\partial x$.

For fixed $(\beta,B)$, by symmetry of $\psi^{\beta}$ and (19), the space $\mathcal{H}^{\star}_{\mu}(\beta,B)$ has a natural mapping into $\mathcal{H}_{\operatorname{loc}}$ given by

With $\underline{\psi}$ permissive this is in fact an embedding; see Remark 2.3. We define the Bethe free energy functional on $\mathcal{H}_{\operatorname{loc}}$ by

where $(\bar{h}_{o}\times_{\psi}\bar{h}_{j})(\sigma_{o},\sigma_{j})\equiv\bar{h}_{o}(\sigma_{o})\psi(\sigma_{o},\sigma_{j})\bar{h}_{j}(\sigma_{j})$, and unimodularity is used in the second identity.

This extended definition of $\Phi_{\mu}$ provides the following variational principle for the Bethe free energy:

$\widetilde{\Phi}_{\mu}(\beta,B)\equiv\sup_{\mathbf{h}\in\mathcal{H}_{\operatorname{loc}}}\Phi_{\mu}(\beta,B,\mathbf{h})$ is continuous in $(\beta,B)$.

Any local maximizer of $\Phi_{\mu}(\beta,B)$ belongs to $\mathcal{H}_{\operatorname{loc}}^{\circ}[\psi]$. Any stationary point of $\Phi_{\mu}(\beta,B)$ belonging to $\mathcal{H}_{\operatorname{loc}}^{\circ}[\psi]$ is the image under (23) of an element of $\mathcal{H}^{\star}_{\mu}(\beta,B)$. In particular, if $\Phi_{\mu}$ attains its supremum on $\mathcal{H}_{\operatorname{loc}}$, then

so that the Bethe free energy is also continuous in $(\beta,B)$.

In case $G_{n}\to_{\mathit{lwc}}{{\textsf{T}}_{d}}$ the $d$-regular tree, $\mathcal{H}_{\operatorname{loc}}$ is parametrized by a single measure $\mathbf{h}_{xy}$ on $\mathscr{X}^{2}$ whose one-point marginals are required to agree, and the formula (26) simplifies to

where $\bar{u}\equiv\bar{u}_{1}$. If this were the case, it would be an immediate consequence of Varadhan’s lemma (see MR1619036, Section 4.3.1) that $\phi_{n}\to\widetilde{\Phi}_{\mu}(\beta,B)$ (as defined in Theorem 1.18) for any factor model satisfying (H1). However, for many of these models the Bethe prediction is known to fail at low temperature for $d\geq 3$. So, while Theorem 1.18 suggests a potential connection to large deviations theory, such a connection would be highly nontrivial and applicable only in certain regimes of $(\beta,B)$.

where $\rho$ and $m$ are the Perron–Frobenius eigenvalue and eigenvector of the symmetric positive $|\mathscr{X}|$-dimensional matrix with entries $\widetilde{\psi}(\sigma,\sigma^{\prime})\equiv\psi(\sigma,\sigma^{\prime})\times{\bar{\psi}}(\sigma)^{1/2}{\bar{\psi}}(\sigma^{\prime})^{1/2}$. The Bethe free energy functional (27) is then maximized at $\mathbf{h}_{01}(\sigma,\sigma^{\prime})=\widetilde{\psi}(\sigma,\sigma^{\prime})m(\sigma)m(\sigma^{\prime})/\rho$, where it takes the value $\Phi_{\mu}(\mathbf{h})=\log\rho$ which coincides with $\phi$ by the Perron–Frobenius theorem; see, for example, MR1619036, Theorem 3.1.1.

Outline of the paper

In Section 2 we prove the abstract interpolation results. Section 2.1 presents some preliminary lemmas which will be useful in our proofs. Our main result for abstract factor models, Theorem 1.15, is proved in Section 2.2. Section 2.3 contains the specialization of this theorem to the uniqueness case (Theorem 1.16) and also contains discussion on unimodular Markov chains (or Bethe Gibbs measures). Section 2.4 shows how to deduce our result for independent set (Theorem 1.12) from Theorem 1.15.

In Section 3 we prove the variational characterization Theorem 1.18 for the Bethe free energy prediction, establishing in particular the correspondence between interior stationary points $\mathbf{h}\in\mathcal{H}_{\operatorname{loc}}^{\circ}[\psi]$ of $\Phi_{\mu}$ and fixed points $h\in\mathcal{H}^{\star}$ of the Bethe recursion. We further provide in Proposition 3.4 a simple criterion for such stationary points to be local maximizers.

Section 4 contains applications of our abstract results to the Ising and Potts models. In Section 4.1 we prove Theorem 1.9, generalizing the results of MR2650042; MR2733399. In Section 4.2 we prove Theorem 1.10 by appealing to a random-cluster representation. Finally, Section 4.3 analyzes the $d$-regular case and proves Theorem 1.11.

Bethe interpolation for general factor models

We begin with some straightforward observations on the boundedness of the free energy $\phi_{n}$ and the Bethe free energy $\Phi_{\mu}$ as defined on $\mathcal{H}$, and we prove that the mapping (23) of $\mathcal{H}^{\star}$ into $\mathcal{H}_{\operatorname{loc}}$ is in fact an embedding for permissive specifications.

For the factor model (1) satisfying (H1) on $G_{n}\to_{\mathit{lwc}}\mu$, the functions $\phi_{n}(\beta,B)$ are uniformly bounded and equicontinuous on compact regions of $(\beta,B)$, with

with the convention $\partial_{\beta}\xi(\sigma,\sigma^{\prime})\equiv 0$ in case $\xi(\sigma,\sigma^{\prime})\equiv-\infty$.

The expressions for $n^{-1}\partial_{\beta}\log Z_{n}(\beta,B)$ and $n^{-1}\partial_{B}\log Z_{n}(\beta,B)$ are obtained by a straightforward computation. Now note that if $G_{n}\to_{\mathit{lwc}}\mu$, then the uniform sparsity assumption gives

Let $\underline{\psi}\equiv(\psi,{\bar{\psi}})$ specify a factor model (1) satisfying (H1), and let $\mu$ be a unimodular measure on ${\mathcal{T}_{\bullet}}$. For any compact region of $(\beta,B)$ there exists a deterministic constant $C<\infty$ such that:

$|\Phi_{T}(\beta,B,h)|\leq C(D_{o}^{2}+1)$ for any $h\in\mathcal{H}^{\star}$, and

if further $\psi>0$, then $|\Phi_{T}(\beta,B,h)|\leq C(D_{o}+1)$ for any $h\in\mathcal{H}$.

Let $\xi_{\min},\xi_{\max}$ be as in the proof of Lemma 2.1. Then, for any $h\in\mathcal{H}$,

It is now easy to see that the mapping (23) of $\mathcal{H}^{\star}_{\mu}(\beta,B)$ into $\mathcal{H}_{\operatorname{loc}}$ is injective: if $h,h^{\prime}\in\mathcal{H}$ give rise to the same $\mathbf{h}$, then

2 Bethe interpolation

We now prove Theorem 1.15(a). The result is for fixed $B$, so we suppress it from the notation. The proof of Theorem 1.15(b) is very similar and will be given in brief at the end of this section.

Our interpolation procedure relies on the proposition below which expresses $\Phi_{\mu}$ as the integral of its partial derivative with respect to $\beta$ only, ignoring the dependence on $\beta$ through the function $h$. Recall that although it is suppressed from the notation, $\underline{\psi}$ and $h$ depend on $\beta$, and are taken to be evaluated at $\beta$ in expressions such as $\Phi_{T}(\beta,B)$. We will prove our result under the following integrability condition, which by (31) is a relaxation of (H2):

We define the analogous condition (H2B) on an interval $[B_{0},B_{1}]$.

Let $\underline{\psi}\equiv(\psi,{\bar{\psi}})$ be a specification satisfying (H1), and $\mu$ a unimodular measure on ${\mathcal{T}_{\bullet}}$. If on $[\beta_{0},\beta_{1}]$ we have $h\in\mathcal{H}^{\star}$ satisfying (H2β) and (H3β), then

For fixed $T\in{\mathcal{T}_{\bullet}}$ we shall regard $\Phi_{T}$ simply as a function of a vector $(\beta,h_{x\to y})_{x\to y\in{T}^{1}}$ in $(1+2|\mathscr{X}|D_{o})$-dimensional euclidean space (with $h$ depending on $\beta$). We begin by computing the partial derivatives of this function with respect to $\beta$ and $h$. We abbreviate $\widehat{h}^{\beta}_{o\to j}(\sigma)\equiv({\textsf{BP}}^{\beta}h)_{o\to j}(\sigma)$ for the belief propagation mapping of (1.6), which for fixed $T$ and each $j\in\partial o$ is a well-defined function on the same euclidean space as $\Phi_{T}$. Making use of (H1) we find

If $h\in\mathcal{H}^{\star}$, then $\widehat{h}^{\beta}=h$, therefore (recalling the notation $[\![]\!]^{h,\beta}_{T}$ from Section 1.3.1) we re-express the above as

Likewise we compute that for $T\in{\mathcal{T}_{\bullet}^{+}}$,

where $g^{\beta}_{\sigma}$ is the same as $\widehat{g}^{\beta}_{\sigma}$ but with $h$ in place of $\widehat{h}$. Note that for permissive $\psi$ and any $\sigma\in\mathscr{X}$,

If further $\psi>0$ everywhere, then $\widehat{g}^{\beta}_{\sigma}(x\to y;h)\leq\psi^{\beta}_{\max}/\psi^{\beta}_{\min}$ is uniformly bounded on $[\beta_{0},\beta_{1}]$.

Consider now a small sub-interval $[\beta,\beta+\delta]$ of $[\beta_{0},\beta_{1}]$. Writing $\Delta_{\beta,\delta}h\equiv h^{\beta+\delta}-h^{\beta}$ and applying the mean value theorem to the differentiable function $t\mapsto\Phi_{T}(\beta+t\delta,h+t\Delta_{\beta,\delta}h)$ for $t\in$ gives

for some $t\equiv t_{\beta,\delta}\in$, where

and $\sum^{*}_{x\to y}$ indicates the sum over the $2D_{o}$ directed edges $x\to y$ within ${T}^{1}$.

Setting $\delta\equiv\delta_{m}\equiv(\beta_{1}-\beta_{0})/m$, we now sum $\Phi(\beta+\delta_{m},h)-\Phi(\beta,h)$ over $\beta\in\Pi_{m}\equiv\{\beta_{0}+k\delta_{m}\colon\;0\leq k<m\}$ and analyze separately the contribution of each term on the right-hand side of (2.2):

The result then follows from unimodularity of $\mu$, subject to $\mu$-integrability of

The total contribution of the first term on the right-hand side of (2.2) is

Observe that $A_{m}=\int Y_{m}\,d(\lambda\times\mu)$ where $\lambda$ is Lebesgue measure on $[\beta_{0},\beta_{1}]$ and

Indeed, it is not hard to see that $\lim_{m\to\infty}E_{T,m}=0$ $\mu$-a.s.: by the uniform bound on total variation assumed in (H3β), there exists deterministic $C$ such that

Combining these observations gives $\lim_{m\to\infty}E_{T,m}=0$ $\mu$-a.s.

To take the limit in $\mu$-expectation, we argue similarly as in part (a): by (35) and (H1) there exists deterministic $C^{\prime}$ such that

for all $\beta\in[\beta_{0},\beta_{1}-\delta]$, $x\to y\in{T}^{1}$, $\sigma\in\mathscr{X}$ and $t\in$, hence

Combining (a)–(c) gives the result of the proposition.

[Proof of Theorem 1.15(a)] Recalling Lemma 2.1,

where the first inequality follows by (the reversed) Fatou’s lemma and the second one by the hypothesis (20). By Proposition 2.4 the right-most expression equals to $\Phi(\beta_{1},h)-\Phi(\beta_{0},h)$, so the theorem is proved.

The justification for interpolation in $B$ is entirely similar:

[Proof of Theorem 1.15(b)] Now $\beta$ is fixed, so we suppress it from the notation. For $h\in\mathcal{H}$ and $T\in{\mathcal{T}_{\bullet}^{+}}$, then

while if $T={T}^{0}$, then $\partial_{B}\Phi_{T}=\sum_{\sigma}\partial_{B}{\bar{\xi}}(\sigma){\bar{\psi}}(\sigma)/\sum_{\sigma}{\bar{\psi}}(\sigma)$. If $h\in\mathcal{H}^{\star}$, then $\widehat{h}^{B}=h^{B}$, so

The result now follows by adapting the proofs of Proposition 2.4 and Theorem 1.15(a).

3 Discussion and first consequences

We now prove Theorem 1.16 by considering an extended notion of local weak convergence. As discussed in MR2354165, a graph $G=(V,E)$ together with a spin configuration $\underline{\sigma}\in\mathscr{X}^{V}$ on the graph can be regarded as a graph with marks in $\mathscr{X}$. Let $\mathcal{G}_{\bullet}^{\mathscr{X}}$ and $\mathcal{G}_{{\bullet}{\bullet}}^{\mathscr{X}}$ denote the spaces of marked isomorphism classes of connected, rooted and bi-rooted graphs, respectively, with marks in $\mathscr{X}$. These spaces are metrizable by the obvious generalizations of the metrics on ${\mathcal{G}_{{\bullet}}},{\mathcal{G}_{{\bullet}{\bullet}}}$ defined in Section 2.1, giving rise to the notion of local weak convergence for pairs $(G_{n},\underline{\sigma}_{n})$ of graphs with spin configurations. Definition 1.2 generalizes naturally to this setting, and we show next that if $\underline{\sigma}_{n}$ is a random configuration on $G_{n}$ with law $\nu_{G_{n},\underline{\psi}}$ [as defined in (1)], then a local weak limit of $(G_{n},\underline{\sigma}_{n})$, if it exists, must be unimodular.

If $G_{n}\to_{\mathit{lwc}}\mu$ and $\underline{\sigma}_{n}\sim\nu_{G_{n},\underline{\psi}}$, then the laws of $(G_{n},\underline{\sigma}_{n})$ have subsequential local weak limits belonging to the space $\mathscr{U}$ of unimodular measures on $\mathcal{G}_{\bullet}^{\mathscr{X}}$.

where $\bar{f}$ is a nonnegative Borel function on ${\mathcal{G}_{{\bullet}{\bullet}}}$. The unimodularity of the underlying measure $\mu$ then gives

and therefore $\mu\otimes\nu\in\mathscr{U}$.

An element $\nu\in\mathscr{G}_{T}$ is called a Markov chain (or splitting Gibbs measure) if for any finite connected sub-graph $U\subseteq T$, the marginal of $\nu$ on $U$ is a Markov random field MR714953; see also MR956646, Chapter 12, and MR0378152. A collection $\Lambda_{T}\equiv(\lambda^{j}_{i})_{(ij)\in E_{T}}$ of probability measures on $\mathscr{X}$ is called an entrance law (or boundary law) for the specification $\underline{\psi}\equiv(\psi,{\bar{\psi}})$ on $T$ if it satisfies the consistency requirement (MR714953, (3.4))

where $\phi_{ij}(\sigma_{i},\sigma_{j})\equiv{\bar{\psi}}(\sigma)^{1/D_{i}}\psi(\sigma,\sigma^{\prime}){\bar{\psi}}(\sigma^{\prime})^{1/D_{j}}$, the pairwise interaction potential corresponding to $\underline{\psi}$. It is shown in MR714953, Theorem 3.2, that there is a one-to-one correspondence between Markov chains $\nu$ and entrance laws $\Lambda_{T}$, given by

[Proof of Theorem 1.16] Suppose uniqueness holds at $(\beta,B)$, that is, $\mathscr{G}_{T}=\{\nu_{T}\}$ $\mu$-a.s. Then $\mathcal{H}^{\star}_{\mu}(\beta,B)$ has size at most one by Remark 2.3. For $\mu$-a.e. $T$, the measure $\nu_{T}$ is extremal, and so specifies a Markov chain on $T$ with entrance law $\Lambda_{T}$; see Remark 2.6. If we define $h_{x\to y}(\sigma)\equiv h_{(T,x\to y)}(\sigma)\cong\lambda^{y}_{x}(\sigma){\bar{\psi}}(\sigma)^{1/D_{x}}$, then $h\in\mathcal{H}^{\star}_{\mu}(\beta,B)$, which proves that $\mathcal{H}^{\star}_{\mu}(\beta,B)$ is a singleton.

Now consider interpolation in $\beta$ or $B$. All the conditions of Theorem 1.15 are satisfied by assumption except (20) and (21). If uniqueness holds at $(\beta,B)$, it follows from the preceding discussion that there is a unique $\mu\otimes\nu\in\mathscr{U}$ corresponding to the specification $(\psi^{\beta},{\bar{\psi}}^{B})$. Any local weak limit of $(G_{n},\underline{\sigma}_{n})$ must be such a measure, so $(G_{n},\underline{\sigma}_{n})\to_{\mathit{lwc}}\mu\otimes\nu$; likewise, any element of $\mathcal{H}^{\star}_{\mu}(\beta,B)$ gives rise to $\mu\otimes\nu$. Therefore,

where the limit in expectation is justified by the boundedness of $\partial_{\beta}\xi$ on compacts and uniform sparsity (as in the proof of Lemma 2.1). This verifies (20), and the verification of (21) is entirely similar. The result therefore follows from Theorem 1.15.

If uniqueness of Gibbs measures does not hold, one may consider extremal decomposition of the subsequential local weak limits $\widehat{\mu}$ of $(G_{n},\underline{\sigma}_{n})$, either in the spaces $\mathscr{G}_{T}$ (possibly losing unimodularity in the decomposition), or in the space $\mathscr{U}$. Extremal decomposition in $\mathscr{U}$ is discussed in MR2354165, Section 4, but it is unclear whether extremal elements would be unimodular Markov chains in the sense described here. A decomposition of $\widehat{\mu}=\mu\otimes\nu$ into unimodular Markov chains $\mu\otimes\nu^{\prime}$ would obviously yield a substantial generalization of Theorem 1.16.

4 Application to independent set

We now prove Theorem 1.12, our result for the independent set model (4), by verifying the conditions of Theorem 1.16 for the interpolation parameter $B\equiv\log\lambda$. In this setting a convenient parametrization for the messages $h\in\mathcal{H}$ is $u\equiv h(0)$, so that the BP mapping (1.6) becomes

A single BP iteration is anti-monotone in the messages $u_{v\to x}$, so a double iteration is monotone. Since the root marginal for an independent set model in ${T}^{2t-1}$ is obtained by an even number of BP iterations starting from level $2t$ (see Remark 1.13), it is monotone in the boundary conditions. Recalling from Section 1.2.3 the definition of $\bar{h}^{t,\ddagger}_{T}\equiv\bar{h}^{t,\ddagger,\lambda}_{T}$ for $\ddagger\in\{0,1\}$ and writing $\bar{u}^{t,\ddagger}_{T}\equiv\bar{h}^{t,\ddagger}_{T}(0)$, the above implies that for $1\leq s\leq t$,

Thus the $t\to\infty$ limits $\bar{h}^{0}_{T},\bar{h}^{1}_{T}$ are well-defined with $\bar{h}^{0}_{T}(1)\geq\bar{h}^{1}_{T}(1)\geq 1/(1+\lambda)$, and using these we define messages $h^{\ddagger}\in\mathcal{H}$, $h^{\ddagger}_{x\to y}=\bar{h}^{\ddagger}_{{T}_{{x\to y}}}$. The next lemma gives the boundary values for the interpolation.

For the independent set model on $G_{n}\to_{\mathit{lwc}}\mu$,

The left limit follows from the trivial bounds $1\leq Z_{n}\leq(1+\lambda)^{n}$. Next, for any $h\in\mathcal{H}$,

For $T\in{\mathcal{T}_{\bullet}}$, as noted above the root occupation probability on ${T}^{s}$ for $s\geq 2t-1$ with any boundary conditions is sandwiched between $\bar{h}^{2t-1,0}_{T}(1)$ and $\bar{h}^{2t-1,1}_{T}(1)$, with the former increasing to $\bar{h}^{0}_{T}(1)$ and the latter decreasing to $\bar{h}^{1}_{T}(1)$. Since the $\bar{h}^{t,\ddagger}_{T}$ are clearly continuous in $\lambda$, it follows that $\bar{h}^{0}_{T}(1)$ and $\bar{h}^{1}_{T}(1)$ are, respectively, lower and upper semi-continuous in $\lambda$, so if they coincide, then their common value $\bar{h}_{T}(1)$ is continuous in $\lambda$. Applying this with $T={T}_{{x\to y}}$ gives the $\mu^{\uparrow}$-a.s. continuity of $h^{\ddagger}_{x\to y}$ on $(0,\lambda_{c})$.

For $T\in{\mathcal{T}_{\bullet}}$, $\bar{h}^{\ddagger}_{T}$ for $\ddagger\in\{0,1\}$ is a function of $(h^{1-\ddagger}_{j\to o})_{j\in\partial o}$, so for $\lambda<\lambda_{c}$ we have that $\bar{h}^{0}_{T}=\bar{h}^{1}_{T}$, $\mu$-a.s. It then follows from the preceding observations and Remark 1.13 that the boundary effect vanishes and $|\mathscr{G}_{T}|=1$ $\mu$-a.s. Thus, we are in the setting of Theorem 1.16(b), and it remains only to complete the verification of (H3B), that is, the boundedness in total variation of the messages $h_{x\to y}$:

No verification is needed since boundedness in total variation is simply assumed.

For $T\in{\mathcal{T}_{\bullet}}$, $\bar{u}^{t,\ddagger}_{T}\equiv\bar{h}^{t,\ddagger}_{T}(0)$ satisfies