Gibbs Measures and Phase Transitions on Sparse Random Graphs

Contents

Introduction

Statistical mechanics is a rich source of fascinating phenomena that can be, at least in principle, fully understood in terms of probability theory. Over the last two decades, probabilists have tackled this challenge with much success. Notable examples include percolation theory , interacting particle systems , and most recently, conformal invariance. Our focus here is on another area of statistical mechanics, the theory of Gibbs measures, which provides a very effective and flexible way to define collections of ‘locally dependent’ random variables.

The general abstract theory of Gibbs measures is fully rigorous from a mathematical point of view . However, when it comes to understanding the properties of specific Gibbs measures, i.e. of specific models, a large gap persists between physicists heuristic methods and the scope of mathematically rigorous techniques.

Recently this area has witnessed significant progress and renewed interest as a consequence of motivations coming from computer science, probabilistic combinatorics and statistical inference. In these disciplines, one is often interested in understanding the properties of (optimal) solutions of a large set of combinatorial constraints. As a typical example, consider a linear system over GF$$,$A\,\underline{x}=\underline{b}$mod$2$, with$A$an$n\times n$binary matrix and$\underline{b}$a binary vector of length$n$. Assume that$A$and$\underline{b}$ are drawn from random matrix/vector ensemble. Typical questions are: What is the probability that such a linear system admits a solution? Assuming a typical realization does not admit a solution, what is the maximum number of equations that can, typically, be satisfied?

While probabilistic combinatorics developed a number of ingenious techniques to deal with these questions, significant progress has been achieved recently by employing novel insights from statistical physics (see ). Specifically, one first defines a Gibbs measure associated to each instance of the problem at hand, then analyzes its properties using statistical physics techniques, such as the cavity method. While non-rigorous, this approach appears to be very systematic and to provide many sharp predictions.

It is clear at the outset that, for ‘natural’ distributions of the binary matrix $A$, the above problem does not have any $d$-dimensional structure. Similarly, in many interesting examples, one can associate to the Gibbs measure a graph that is sparse and random, but of no finite-dimensional structure. Non-rigorous statistical mechanics techniques appear to provide detailed predictions about general Gibbs measures of this type. It would be highly desirable –and in principle possible– to develop a fully mathematical theory of such Gibbs measures. The present paper provides a unified presentation of a few results in this direction.

In the rest of this section, we proceed with a more detailed overview of the topic, proposing certain fundamental questions the answer to which plays an important role within the non-rigorous statistical mechanics analysis. We illustrate these questions on the relatively well-understood Curie-Weiss (toy) model and explore a few additional motivating examples.

Section 2 focuses on a specific example, namely the ferromagnetic Ising model on sequences of locally tree-like graphs. Thanks to its monotonicity properties, detailed information can be gained on this model.

A recurring prediction of statistical mechanics studies is that Bethe-Peierls approximation is asymptotically tight in the large graph limit, for sequences of locally tree-like graphs. Section 3 provides a mathematical formalization of Bethe-Peierls approximation. We also prove there that, under an appropriate correlation decay condition, Bethe-Peierls approximation is indeed essentially correct on graphs with large girth.

In Section 4 we consider a more challenging, and as of now, poorly understood, example: proper colorings of a sparse random graph. A fascinating ‘clustering’ phase transition is predicted to occur as the average degree of the graph crosses a certain threshold. Whereas the detailed description and verification of this phase transition remains an open problem, its relation with the appropriate notion of correlation decay (‘extremality’), is the subject of Section 5.

Finally, it is common wisdom in statistical mechanics that phase transitions should be accompanied by a specific ‘finite-size scaling’ behavior. More precisely, a phase transition corresponds to a sharp change in some property of the model when a control parameter crosses a threshold. In a finite system, the dependence on any control parameter is smooth, and the change and takes place in a window whose width decreases with the system size. Finite-size scaling broadly refers to a description of the system behavior within this window. Section 6 presents a model in which finite-size scaling can be determined in detail.

The Curie-Weiss model is deceivingly simple, but is a good framework to start illustrating some important ideas. For a detailed study of this model we refer to .

At time zero, each of $n$ individuals takes one of two opinions $X_{i}(0)\in\{+1,-1\}$ independently and uniformly at random for $i\in[n]=\{1,\dots,n\}$. At each subsequent time $t$, one individual $i$, chosen uniformly at random, computes the opinion imbalance

and $M^{(i)}\equiv M-X_{i}$. Then, he/she changes his/her opinion with probability

Despite its simplicity, this model raises several interesting questions.

How long does is take for the process $\underline{X}(t)$ to become approximately stationary?

How often do individuals change opinion in the stationary state?

Is the typical opinion pattern strongly polarized (herding)?

If this is the case, how often does the popular opinion change?

We do not address question (a) here, but we will address some version of questions (b)–(d). More precisely, this dynamics (first studied in statistical physics under the name of Glauber or Metropolis dynamics) is an aperiodic irreducible Markov chain whose unique stationary measure is

We are mostly interested in the large-$n$ (population size), behavior of $\mu_{n,\beta}(\cdot)$ and its dependence on $\beta$ (the interaction strength). In this context, we have the following ‘static’ versions of the preceding questions:

What is the distribution of $p_{\mbox{\tiny flip}}(\underline{x})$ when $\underline{x}$ has distribution $\mu_{n,\beta}(\,\cdot\,)$?

What is the distribution of the opinion imbalance $M$? Is it concentrated near $0$ (evenly spread opinions), or far from $0$ (herding)?

In the herding case: how unlikely are balanced ($M\approx 0$) configurations?

1.2 Graphical models

A graph $G=(V,E)$ consists of a set $V$ of vertices and a set $E$ of edges (where an edge is an unordered pair of vertices). We always assume $G$ to be finite with $|V|=n$ and often make the identification $V=[n]$. With ${\cal X}$ a finite set, called the variable domain, we associate to each vertex $i\in V$ a variable $x_{i}\in{\cal X}$, denoting by $\underline{x}\in{\cal X}^{V}$ the complete assignment of these variables and by $\underline{x}_{U}=\{x_{i}:\;i\in U\}$ its restriction to $U\subseteq V$.

A bounded specification $\underline{\psi}\equiv\{\psi_{ij}:\;(i,j)\in E\}$ for a graph $G$ and variable domain ${\cal X}$ is a family of functionals $\psi_{ij}:{\cal X}\times{\cal X}\to[0,\psi_{\max}]$ indexed by the edges of $G$ with $\psi_{\max}$ a given finite, positive constant (where for consistency $\psi_{ij}(x,x^{\prime})=\psi_{ji}(x^{\prime},x)$ for all $x,x^{\prime}\in{\cal X}$ and $(i,j)\in E$). The specification may include in addition functions $\psi_{i}:{\cal X}\to[0,\psi_{\max}]$ indexed by vertices of $G$.

A bounded specification $\underline{\psi}$ for $G$ is permissive if there exists a positive constant $\kappa$ and a ‘permitted state’ $x_{i}^{\rm p}\in{\cal X}$ for each $i\in V$, such that $\min_{i,x^{\prime}}\psi_{i}(x^{\prime})\geq\kappa\psi_{\max}$ and

The graphical model associated with a graph-specification pair $(G,\underline{\psi})$ is the canonical probability measure

and the corresponding canonical stochastic process is the collection $\underline{X}=\{X_{i}:\,i\in V\}$ of ${\cal X}$-valued random variables having joint distribution $\mu_{G,\underline{\psi}}(\cdot)$.

One such example is the distribution (1.3), where ${\cal X}=\{+1,-1\}$, $G$ is the complete graph over $n$ vertices and $\psi_{ij}(x_{i},x_{j})=\exp(\beta x_{i}x_{j}/n)$. Here $\psi_{i}(x)\equiv 1$. It is sometimes convenient to introduce a ‘magnetic field’ (see for instance Eq. (1.9) below). This corresponds to taking $\psi_{i}(x_{i})=\exp(Bx_{i})$.

Rather than studying graphical models at this level of generality, we focus on a few concepts/tools that have been the subject of recent research efforts.

Coexistence. Roughly speaking, we say that a model $(G,\underline{\psi})$ exhibits coexistence if the corresponding measure $\mu_{G,\underline{\psi}}(\cdot)$ decomposes into a convex combination of well-separated lumps. To formalize this notion, we consider sequences of measures $\mu_{n}$ on graphs $G_{n}=([n],E_{n})$, and say that coexistence occurs if, for each $n$, there exists a partition $\Omega_{1,n},\dots,\Omega_{r,n}$ of the configuration space ${\cal X}^{n}$ with $r=r(n)\geq 2$, such that

The measure of elements of the partition is uniformly bounded away from one:

The elements of the partition are separated by ‘bottlenecks’. That is, for some $\epsilon>0$,

as $n\to\infty$, where $\partial_{\epsilon}\Omega$ denotes the $\epsilon$-boundary of $\Omega\subseteq{\cal X}^{n}$,

with respect to the Hamming The Hamming distance $d(\underline{x},\underline{x}^{\prime})$ between configurations $\underline{x}$ and $\underline{x}^{\prime}$ is the number of positions in which the two configurations differ. Given $\Omega\subseteq{\cal X}^{n}$, $d(\underline{x},\Omega)\equiv\min\{d(\underline{x},\underline{x}^{\prime}):\underline{x}^{\prime}\in\Omega\}$. distance. The normalization by $\mu_{n}(\Omega_{s,n})$ removes ‘false bottlenecks’ and is in particular needed since $r(n)$ often grows (exponentially) with $n$.

Depending on the circumstances, one may further specify a required rate of decay in (1.6).

We often consider families of models indexed by one (or more) continuous parameters, such as the inverse temperature $\beta$ in the Curie-Weiss model. A phase transition will generically be a sharp threshold in some property of the measure $\mu(\,\cdot\,)$ as one of these parameters changes. In particular, a phase transition can separate values of the parameter for which coexistence occurs from those values for which it does not.

Mean field models. Intuitively, these are models that lack any (finite-dimensional) geometrical structure. For instance, models of the form (1.4) with $\psi_{ij}$ independent of $(i,j)$ and $G$ the complete graph or a regular random graph are mean field models, whereas models in which $G$ is a finite subset of a finite dimensional lattice are not. To be a bit more precise, the Curie-Weiss model belongs to a particular class of mean field models in which the measure $\mu(\underline{x})$ is exchangeable (that is, invariant under coordinate permutations). A wider class of mean field models may be obtained by considering random distributions A random distribution over ${\cal X}^{n}$ is just a random variable taking values on the $(|{\cal X}|^{n}-1)$-dimensional probability simplex. $\mu(\cdot)$ (for example, when either $G$ or $\underline{\psi}$ are chosen at random in (1.4)). In this context, given a realization of $\mu$, consider $k$ i.i.d. configurations $\underline{X}^{(1)},\dots,\underline{X}^{(k)}$, each having distribution $\mu$. These ‘replicas’ have the unconditional, joint distribution

The random distribution $\mu$ is a candidate to be a mean field model when for each fixed $k$ the measure $\mu^{(k)}$, viewed as a distribution over $({\cal X}^{k})^{n}$, is exchangeable (with respect to permutations of the coordinate indices in $[n]$). Unfortunately, while this property suffices in many ‘natural’ special cases, there are models that intuitively are not mean-field and yet have it. For instance, given a non-random measure $\nu$ and a uniformly random permutation $\pi$, the random distribution $\mu(x_{1},\dots,x_{n})\equiv\nu(x_{\pi(1)},\dots,x_{\pi(n)})$ meets the preceding requirement yet should not be considered a mean field model. While a satisfactory mathematical definition of the notion of mean field models is lacking, by focusing on selective examples we examine in the sequel the rich array of interesting phenomena that such models exhibit.

Mean field equations. Distinct variables may be correlated in the model (1.4) in very subtle ways. Nevertheless, mean field models are often tractable because an effective ‘reduction’ to local marginals In particular, single variable marginals, or joint distributions of two variables connected by an edge. takes place asymptotically for large sizes (i.e. as $n\to\infty$).

Thanks to this reduction it is often possible to write a closed system of equations for the local marginals that hold in the large size limit and determine the local marginals, up to possibly having finitely many solutions. Finding the ‘correct’ mathematical definition of this notion is an open problem, so we shall instead provide specific examples of such equations in a few special cases of interest (starting with the Curie-Weiss model).

1.3 Coexistence in the Curie-Weiss model

The model (1.3) appeared for the first time in the physics literature as a model for ferromagnets A ferromagnet is a material that acquires a macroscopic spontaneous magnetization at low temperature.. In this context, the variables $x_{i}$ are called spins and their value represents the direction in which a localized magnetic moment (think of a tiny compass needle) is pointing. In certain materials the different magnetic moments favor pointing in the same direction, and physicists want to know whether such interaction may lead to a macroscopic magnetization (imbalance), or not.

In studying this and related problems it often helps to slightly generalize the model by introducing a linear term in the exponent (also called a ‘magnetic field’). More precisely, one considers the probability measures

In this context $1/\beta$ is referred to as the ‘temperature’ and we shall always assume that $\beta\geq 0$ and, without loss of generality, also that $B\geq 0$.

The following estimates on the distribution of the magnetization per site are the key to our understanding of the large size behavior of the Curie-Weiss model (1.9).

Let $H(x)=-x\log x-(1-x)\log(1-x)$ denote the binary entropy function and for $\beta\geq 0$, $B\in{\mathds{R}}$ and $m\in[-1,+1]$ set

Then, for $\overline{X}\equiv n^{-1}\sum_{i=1}^{n}X_{i}$, a random configuration $(X_{1},\ldots,X_{n})$ from the Curie-Weiss model and each $m\in S_{n}\equiv\{-1,-1+2/n,\dots,1-2/n,1\}$,

our thesis follows by Stirling’s approximation of the binomial coefficient (for example, see [24, Theorem 12.1.3]). $\Box$

A major role in determining the asymptotic properties of the measures $\mu_{n,\beta,B}$ is played by the free entropy density (the term ‘density’ refers here to the fact that we are dividing by the number of variables),

For all $n$ large enough we have the following bounds on the free entropy density $\phi_{n}(\beta,B)$ of the (generalized) Curie-Weiss model

The upper bound follows upon summing over $m\in S_{n}$ the upper bound in (1.11). Further, from the lower bound in (1.11) we get that

A little calculus shows that maximum of $\varphi_{\beta,B}(\cdot)$ over the finite set $S_{n}$ is not smaller that its maximum over the interval $[-1,+1]$ minus $n^{-1}(\log n)$, for all $n$ large enough. $\Box$

Consider the optimization problem in Eq. (1.13). Since $\varphi_{\beta,B}(\cdot)$ is continuous on $$and differentiable in its interior, with$\varphi^{\prime}_{\beta,B}(m)\to\pm\infty$as$m\to\mp 1$, this maximum is achieved at one of the points$m\in(-1,1)$where$\varphi_{\beta,B}^{\prime}(m)=0$. A direct calculation shows that the latter condition is equivalent to

Analyzing the possible solutions of this equation, one finds out that:

For $\beta\leq 1$, the equation (1.14) admits a unique solution $m_{*}(\beta,B)$ increasing in $B$ with $m_{*}(\beta,B)\downarrow 0$ as $B\downarrow 0$. Obviously, $m_{*}(\beta,B)$ maximizes $\varphi_{\beta,B}(m)$.

For $\beta>1$ there exists $B_{*}(\beta)>0$ continuously increasing in $\beta$ with $\lim_{\beta\downarrow 1}B_{*}(\beta)=0$ such that: $(i)$ for $0\leq B<B_{*}(\beta)$, Eq. (1.14) admits three distinct solutions $m_{-}(\beta,B),m_{0}(\beta,B),m_{+}(\beta,B)\equiv m_{*}(\beta,B)$ with $m_{-}<m_{0}\leq 0\leq m_{+}\equiv m_{*}$; $(ii)$ for $B=B_{*}(\beta)$ the solutions $m_{-}(\beta,B)=m_{0}(\beta,B)$ coincide; $(iii)$ and for $B>B_{*}(\beta)$ only the positive solution $m_{*}(\beta,B)$ survives.

Further, for $B\geq 0$ the global maximum of $\varphi_{\beta,B}(m)$ over $m\in$ is attained at $m=m_{*}(\beta,B)$, while $m_{0}(\beta,B)$ and $m_{-}(\beta,B)$ are (respectively) a local minimum and a local maximum (and a saddle point when they coincide at $B=B_{*}(\beta)$). Since $\varphi_{\beta,0}(\cdot)$ is an even function, in particular $m_{0}(\beta,0)=0$ and $m_{\pm}(\beta,0)=\pm m_{*}(\beta,0)$.

Our next theorem answers question (c’) of Section 1.1.1 for the Curie-Weiss model.

Consider $\overline{X}$ of Lemma 1.2 and the relevant solution $m_{*}(\beta,B)$ of equation (1.14). If either $\beta\leq 1$ or $B>0$, then for any $\varepsilon>0$ there exists $C(\varepsilon)>0$ such that, for all $n$ large enough

In contrast, if $B=0$ and $\beta>1$, then for any $\varepsilon>0$ there exists $C(\varepsilon)>0$ such that, for all $n$ large enough

Suppose first that either $\beta\leq 1$ or $B>0$, in which case $\varphi_{\beta,B}(m)$ has the unique non-degenerate global maximizer $m_{*}=m_{*}(\beta,B)$. Fixing $\varepsilon>0$ and setting $I_{\varepsilon}=[-1,m_{*}-\varepsilon]\cup[m_{*}+\varepsilon,1]$, by Lemma 1.2

The bound of (1.16) is proved analogously, using the fact that $\mu_{n,\beta,0}(\underline{x})=\mu_{n,\beta,0}(-\underline{x})$. $\Box$

We just encountered our first example of coexistence (and of phase transition).

The Curie-Weiss model shows coexistence if and only if $B=0$ and $\beta>1$.

We will limit ourselves to the ‘if’ part of this statement: for $B=0$, $\beta>1$, the Curie-Weiss model shows coexistence. To this end, we simply check that the partition of the configuration space $\{+1,-1\}^{n}$ to $\Omega_{+}\equiv\{\underline{x}:\,\sum_{i}x_{i}\geq 0\}$ and $\Omega_{-}\equiv\{\underline{x}:\,\sum_{i}x_{i}<0\}$ satisfies the conditions in Section 1.1.2. Indeed, it follows immediately from (1.16) that choosing a positive $\epsilon<m_{*}(\beta,0)/2$, we have

for some $C>0$ and all $n$ large enough, which is the thesis. $\Box$

1.4 The Curie-Weiss model: Mean field equations

which, in agreement with our general description of mean field equations, is a closed form relation between the local marginals under the measure $\mu_{n,\beta,B}(\cdot)$.

We next re-derive the equation (1.17) directly out of the concentration in probability of $\overline{X}$. This approach is very useful, for in more complicated models one often has mild bounds on the fluctuations of $\overline{X}$ while lacking fine controls such as in Theorem 1.4. To this end, we start by proving the following ‘cavity’ estimate. Cavity methods of statistical physics aim at understanding thermodynamic limits $n\to\infty$ by first relating certain quantities for systems of size $n\gg 1$ to those in systems of size $n^{\prime}=n+O(1)$.

By direct computation, for any function $F:\{+1,-1\}^{n}\to{\mathds{R}}$,

Therefore, with $\cosh(a)\geq 1$ we get by Cauchy-Schwarz that

where the last inequality is due to the Lipschitz behavior of $x\mapsto\cosh(B+\beta x)$ together with the bound $|\overline{X}|\leq 1$. $\Box$

The following theorem provides a rigorous version of Eq. (1.17) for $\beta\leq 1$ or $B>0$.

There exists a constant $C(\beta,B)$ such that for any $i\in[n]$,

Further notice that (by the Lipschitz property of $\cosh(B+\beta x)$ and $\sinh(B+\beta x)$ together with the bound $|\overline{X}|\leq 1$),

Using the inequality $|a_{1}/b_{1}-a_{2}/b_{2}|\leq|a_{1}-a_{2}|/b_{1}+a_{2}|b_{1}-b_{2}|/b_{1}b_{2}$ we thus have here (with $a_{i}\geq 0$ and $b_{i}\geq\max(1,a_{i})$), that

At this point you get our thesis by applying Lemma 1.6. $\Box$

2 Graphical models: examples

We next list a few examples of graphical models, originating at different domains of science and engineering. Several other examples that fit the same framework are discussed in detail in .

Ferromagnetic Ising model. The ferromagnetic Ising model is arguably the most studied model in statistical physics. It is defined by the Boltzmann distribution

over $\underline{x}=\{x_{i}:\,i\in V\}$, with $x_{i}\in\{+1,-1\}$, parametrized by the ‘magnetic field’ $B\in{\mathds{R}}$ and ‘inverse temperature’ $\beta\geq 0$, where the partition function $Z(\beta,B)$ is fixed by the normalization condition $\sum_{\underline{x}}\mu(\underline{x})=1$. The interaction between vertices $i,j$ connected by an edge pushes the variables $x_{i}$ and $x_{j}$ towards taking the same value. It is expected that this leads to a global alignment of the variables (spins) at low temperature, for a large family of graphs. This transition should be analogue to the one we found for the Curie-Weiss model, but remarkably little is known about Ising models on general graphs. In Section 2 we consider the case of random sparse graphs.

Anti-ferromagnetic Ising model. This model takes the same form (1.20), but with $\beta<0$. In the literature one usually introduces explicitly a minus sign to keep $\beta$ positive. Note that if $B=0$ and the graph is bipartite (i.e. if there exists a partition $V=V_{1}\cup V_{2}$ such that $E\subseteq V_{1}\times V_{2}$), then this model is equivalent to the ferromagnetic one (upon inverting the signs of $\{x_{i},i\in V_{1}\}$). However, on non-bipartite graphs the anti-ferromagnetic model is way more complicated than the ferromagnetic one, and even determining the most likely (lowest energy) configuration is a difficult matter. Indeed, for $B=0$ the latter is equivalent to the celebrated max-cut problem from theoretical computer science.

Spin glasses. An instance of the Ising spin glass is defined by a graph $G$, together with edge weights $J_{ij}\in{\mathds{R}}$, for $(i,j)\in E$. Again variables are binary $x_{i}\in\{+1,-1\}$ and

In a spin glass model the ‘coupling constants’ $J_{ij}$ are random with even distribution (the canonical examples being $J_{ij}\in\{+1,-1\}$ uniformly and $J_{ij}$ centered Gaussian variables). One is interested in determining the asymptotic properties as $n=|V|\to\infty$ of $\mu_{n,\beta,B,{\underline{J}}}(\,\cdot\,)$ for a typical realization of the coupling ${\underline{J}}\equiv\{J_{ij}\}$.

2.2 Random constraint satisfaction problems

A constraint satisfaction problem (CSP) consists of a finite set ${\cal X}$ (called the variable domain), and a class ${\cal C}$ of possible constraints (i.e. indicator functions), each of which involves finitely many ${\cal X}$-valued variables $x_{i}$. An instance of this problem is then specified by a positive integer $n$ (the number of variables), and a set of $m$ constraints involving only the variables $x_{1},\ldots,x_{n}$ (or a subset thereof). A solution of this instance is an assignment in ${\cal X}^{n}$ for the variables $x_{1},\ldots,x_{n}$ which satisfies all $m$ constraints.

In this context, several questions are of interest within computer science:

Decision problem. Does the given instance have a solution?

Optimization problem. Maximize the number of satisfied constraints.

Counting problem. Count the number of solutions.

There are many ways of associating a graphical model to an instance of CSP. If the instance admits a solution, then one option is to consider the uniform measure over all such solutions. Let us see how this works in a few examples.

Coloring. A proper $q$-coloring of a graph $G$ is an assignment of colors in $[q]$ to the vertices of $G$ such that no edge has both endpoints of the same color. The corresponding CSP has variable domain ${\cal X}=[q]$ and the possible constraints in ${\cal C}$ are indexed by pairs of indices $(i,j)\in V\times V$, where the constraint $(i,j)$ is satisfied if and only if $x_{i}\neq x_{j}$.

Assuming that a graph $G$ admits a proper $q$-coloring, the uniform measure over the set of possible solutions is

with $Z_{G}$ counting the number of proper $q$-colorings of $G$.

$k$-SAT. In case of $k$-satisfiability (in short, $k$-SAT), the variables are binary $x_{i}\in{\cal X}=\{0,1\}$ and each constraint is of the form $(x_{i(1)},\dots,x_{i(k)})\neq(x^{*}_{i(1)},\dots,x^{*}_{i(k)})$ for some prescribed $k$-tuple $(i(1),\dots,i(k))$ of indices in $V=[n]$ and their prescribed values $(x^{*}_{i(1)},\dots,x^{*}_{i(k)})$. In this context constraints are often referred to as ‘clauses’ and can be written as the disjunction (logical OR) of $k$ variables or their negations. The uniform measure over solutions of an instance of this problem, if such solutions exist, is then

with $Z$ counting the number of solutions. An instance can be associated to a factor graph, cf. Fig. 1. This is a bipartite graph having two types of nodes: variable nodes in $V=[n]$ denoting the unknowns $x_{1},\ldots,x_{n}$ and function (or factor) nodes in $F=[m]$ denoting the specified constraints. Variable node $i$ and function node $a$ are connected by an edge in the factor graph if and only if variable $x_{i}$ appears in the $a$-th clause, so ${\partial a}=\{i_{a}(1),\dots,i_{a}(k)\}$ and ${\partial i}$ corresponds to the set of clauses in which $i$ appears.

In general, such a construction associates to arbitrary CSP instance a factor graph $G=(V,F,E)$. The uniform measure over solutions of such an instance is then of the form

for a suitable choice of $\underline{\psi}\equiv\{\psi_{a}(\cdot):a\in F\}$. Such measures can also be viewed as the zero temperature limit of certain Boltzmann distributions. We note in passing that the probability measure of Eq. (1.4) corresponds to the special case where all function nodes are of degree two.

2.3 Communications, estimation, detection

We describe next a canonical way of phrasing problems from mathematical engineering in terms of graphical models. Though we do not detail it here, this approach applies to many specific cases of interest.

Let $X_{1},\dots,X_{n}$ be a collection of i.i.d. ‘hidden’ random variables with a common distribution $p_{0}(\,\cdot\,)$ over a finite alphabet ${\cal X}$. We want to estimate these variables from a given collection of observations $Y_{1},\dots,Y_{m}$. The $a$-th observation (for $a\in[m]$) is a random function of the $X_{i}$’s for which $i\in{\partial a}=\{i_{a}(1),\dots,i_{a}(k)\}$. By this we mean that $Y_{a}$ is conditionally independent of all the other variables given $\{X_{i}:\,i\in{\partial a}\}$ and we write

for some probability kernel $Q_{a}(\,\cdot\,|\,\cdot\,)$.

The a posteriori distribution of the hidden variables given the observations is thus

2.4 Graph and graph ensembles

The structure of the underlying graph $G$ is of much relevance for the general measures $\mu_{G,\underline{\psi}}$ of (1.4). The same applies in the specific examples we have outlined in Section 1.2.

As already hinted, we focus here on (random) graphs that lack finite dimensional Euclidean structure. A few well known ensembles of such graphs (c.f. ) are:

3 Detour: The Ising model on the integer lattice

In statistical physics it is most natural to consider models with local interactions on a finite dimensional integer lattice ${\mathds{Z}}^{d}$, where $d=2$ and $d=3$ are often the physically relevant ones. While such models are of course non-mean field type, taking a short detour we next present a classical result about ferromagnetic Ising models on finite subsets of ${\mathds{Z}}^{2}$.

While this theorem and its proof refer to ${\mathds{Z}}^{2}$, the techniques we use are more general.

Low temperature: Peierls argument. The proof of (1.26) is taken from and based on the Peierls contour representation for the two dimensional Ising model. We start off by reviewing this representation. First, given a square grid $G=(V,E)$ of side $\sqrt{n}$ in ${\mathds{Z}}^{2}$, for each $(i,j)\in E$ draw a perpendicular edge of length one, centered at the midpoint of $(i,j)$. Let $E^{*}$ denote the collection of all these perpendicular edges and $V^{*}$ the collection of their end points, viewed as a finite subset of ${\mathds{R}}^{2}$. A contour is a simple path on the ‘dual’ graph $G^{*}=(V^{*},E^{*})$, either closed or with both ends at boundary (i.e. degree one) vertices. A closed contour $C$ divides $V$ to two subsets, the inside of $C$ and the outside of $C$. We further call as ‘inside’ the smaller of the two subsets into which a non-closed contour divides $V$ (an arbitrary convention can be used in case the latter two sets are of equal size). A Peierls contours configuration $(\mathcal{C},s)$ consists of a sign $s\in\{+1,-1\}$ and an edge-disjoint finite collection $\mathcal{C}$ of non-crossing contours (that is, whenever two contours share a vertex, each of them bends there). Starting at an Ising configuration $\underline{x}\in\Omega\equiv\{+1,-1\}^{V}$ note that the set $V_{+}(\underline{x})=\{v\in V:x_{v}=+1\}$ is separated from $V_{-}(\underline{x})=\{v\in V:x_{v}=-1\}$ by an edge-disjoint finite collection $\mathcal{C}=\mathcal{C}(\underline{x})$ of non-crossing contours. Further, it is not hard to check that the non-empty set $U(\underline{x})=\{v\in V:v$ not inside any contour from $\mathcal{C}\}$ is either contained in $V_{+}(\underline{x})$, in which case $s(\underline{x})=+1$ or in $V_{-}(\underline{x})$, in which case $s(\underline{x})=-1$, partitioning $\Omega$ to $\Omega_{+}=\{\underline{x}:s(\underline{x})=+1\}$ and $\Omega_{-}=\{\underline{x}:s(\underline{x})=-1\}$. In the reverse direction, the Ising configuration is read off a Peierls contours configuration $(\mathcal{C},s)$ by setting $x_{v}=s$ when the number of contours $C\in\mathcal{C}$ such that $v\in V$ lies in the inside of $C$ is even while $x_{v}=-s$ when it is odd. The mapping $\underline{x}\mapsto-\underline{x}$ exchanges $\Omega_{+}$ with $\Omega_{-}$ so

If $\underline{x}$ is in $\Omega_{+}$ then $|V_{-}(\underline{x})|$ is bounded by the total number of vertices of $V$ inside contours of $\mathcal{C}$, which by isoperimetric considerations is at most $\sum_{C\in\mathcal{C}}|C|^{2}$ (where $|C|$ denotes the length of contour $C$). Further, our one-to-one correspondence between Ising and Peierls contours configurations maps the Ising measure at $\beta>0$ to uniform $s\in\{+1,-1\}$ independent of $\mathcal{C}$ whose distribution is the Peierls measure

Recall that if a given contour $C$ is in some edge-disjoint finite collection $\mathcal{C}$ of non-crossing contours, then $\mathcal{C}^{\prime}=\mathcal{C}\setminus C$ is another such collection, with $\mathcal{C}\mapsto\mathcal{C}^{\prime}$ injective, from which we easily deduce that $\mu_{*}(C\in\mathcal{C})\leq\exp(-2\beta|C|)$ for any fixed contour $C$. Consequently,

We are thus done, as this lower bound converges to one for $\beta\to\infty$.

High-temperature expansion. The proof of (1.27), taken from , is by the method of high-temperature expansion which serves us again when dealing with the unfrustrated XORSAT model in Section 6.1. As in the low-temperature case, the first step consists of finding an appropriate ‘geometrical’ representation. To this end, given a subset $U\subseteq V$ of vertices, let

and denote by ${\mathcal{G}}(U)$ the set of subgraphs of $G$ having an odd-degree at each vertex in $U$ and an even degree at all other vertices. Then, with $\theta\equiv\tanh(\beta)$ and $F\subseteq E$ denoting both a subgraph of $G$ and its set of edges, we claim that

Indeed, $e^{\beta y}=\cosh(\beta)[1+y\theta]$ for $y\in\{+1,-1\}$, so by definition

By symmetry $\sum_{\underline{x}}x_{R}$ is zero unless each $v\in V$ appears in the set $R$ an even number of times, in which case the sum is $2^{|V|}$. In particular, the latter applies for $x_{R}=x_{U}\prod_{(i,j)\in F}x_{i}x_{j}$ if and only if $F\in{\mathcal{G}}(U)$ from which our stated high-temperature expansion (1.30) follows.

We next use this expansion to get a uniform in $n$ decay of correlations at all $\beta<\beta_{o}\equiv{\rm atanh}(1/3)$, with an exponential rate with respect to the graph distance $d(i,j)$. More precisely, we claim that for any such $\beta$, $n$ and $i,j\in V$

Let $\mathcal{F}(i,j)$ denote the collection of all simple paths from $i$ to $j$ in ${\mathds{Z}}^{2}$ and for each such path $F_{i,j}$, denote by ${\mathcal{G}}(\emptyset,F_{i,j})$ the sub-collection of graphs in ${\mathcal{G}}(\emptyset)$ that have no edge in common with $F_{i,j}$. The sum of vertex degrees in a connected component of a graph $F$ is even, hence any $F\in{\mathcal{G}}(\{i,j\})$ contains some path $F_{i,j}\in\mathcal{F}(i,j)$. Further, $F$ is the edge-disjoint union of $F_{i,j}$ and $F^{\prime}=F\setminus F_{i,j}$ with $F^{\prime}$ having an even degree at each vertex. As $F^{\prime}\in{\mathcal{G}}(\emptyset,F_{i,j})$ we thus deduce that

We are done now, for there are at most $8d$ vertices in ${\mathds{Z}}^{2}$ at distance $d$ from each $i\in{\mathds{Z}}^{2}$. Hence,

which for $\theta<1/3$ decays to zero as $n\to\infty$.

Ising models on locally tree-like graphs

A ferromagnetic Ising model on the finite graph $G$ (with vertex set $V$, and edge set $E$) is defined by the Boltzmann distribution $\mu_{\beta,B}(\underline{x})$ of (1.20) with $\beta\geq 0$. In the following it is understood that, unless specified otherwise, the model is ferromagnetic, and we will call it ‘Ising model on $G$.’

For sequences of graphs $G_{n}=(V_{n},E_{n})$ of diverging size $n$, non-rigorous statistical mechanics techniques, such as the ‘replica’ and ‘cavity methods,’ make a number of predictions on this model when the graph $G$ ‘lacks any finite-dimensional structure.’ The most basic quantity in this context is the asymptotic free entropy density, cf. Eq. (1.12),

The Curie-Weiss model, cf. Section 1.1, corresponds to the complete graph $G_{n}=K_{n}$. Predictions exist for a much wider class of models and graphs, most notably, sparse random graphs with bounded average degree that arise in a number of problems from combinatorics and theoretical computer science (c.f. the examples of Section 1.2.2). An important new feature of sparse graphs is that one can introduce a notion of distance between vertices as the length of shortest path connecting them. Consequently, phase transitions and coexistence can be studied with respect to the correlation decay properties of the underlying measure. It turns out that this approach is particularly fruitful and allows to characterize these phenomena in terms of appropriate features of Gibbs measures on infinite trees. This direction is pursued in in the case of random constraint satisfaction problems.

Statistical mechanics also provides methods for approximating the local marginals of the Boltzmann measure of (1.20). Of particular interest is the algorithm known in artificial intelligence and computer science under the name of belief propagation. Loosely speaking, this procedure consists of solving by iteration certain mean field (cavity) equations. Belief propagation is shown in to converge exponentially fast for an Ising model on any graph (even in a low-temperature regime lacking uniform decorrelation), with resulting asymptotically tight estimates for large locally tree-like graphs (see Section 2.3).

We follow here , where the asymptotic free entropy density (2.1) is determined rigorously for certain sparse graph sequences $\{G_{n}\}$ that converge locally to trees. In order to make this notion more precise, we denote by ${\sf B}_{i}(t)$ the subgraph induced by vertices of $G_{n}$ whose distance from $i$ is at most $t$. Further, given two rooted trees $T_{1}$ and $T_{2}$ of the same size, we write $T_{1}\simeq T_{2}$ if $T_{1}$ and $T_{2}$ are identical upon labeling their vertices in a breadth first fashion following lexicographic order among siblings.

where ${\sf T}(t)$ denotes the subtree of first $t$ generations of ${\sf T}$.

We also say that $\{G_{n}\}$ is uniformly sparse if

where $|{\partial i}|$ denotes the size of the set ${\partial i}$ of neighbors of $i\in V_{n}$ (i.e. the degree of $i$).

The proof that for locally tree-like graphs $\phi_{n}(\beta,B)=\frac{1}{n}\log Z_{n}(\beta,B)$ converges to (an explicit) limit $\phi(\beta,B)$ consists of two steps

Reduce the computation of $\phi_{n}(\beta,B)$ to computing expectations of local (in $G_{n}$) quantities with respect to the Boltzmann measure (1.20). This is achieved by noting that the derivative of $\phi_{n}(\beta,B)$ with respect to $\beta$ is a sum of such expectations.

Show that under the Boltzmann measure (1.20) on $G_{n}$ expectations of local quantities are, for $t$ and $n$ large, well approximated by the same expectations with respect to an Ising model on the associated random tree ${\sf T}(t)$ (a philosophy related to that of ).

The key is of course step (b), and the challenge is to carry it out when the parameter $\beta$ is large and we no longer have uniqueness of the Gibbs measure on the limiting tree ${\sf T}$. Indeed, this is done in for the following collection of trees of conditionally independent (and of bounded average) offspring numbers.

An infinite labeled tree ${\sf T}$ rooted at the vertex ${\o}$ is called conditionally independent if for each integer $k\geq 0$, conditional on the subtree ${\sf T}(k)$ of the first $k$ generations of ${\sf T}$, the number of offspring $\Delta_{j}$ for $j\in\partial{\sf T}(k)$ are independent of each other, where $\partial{\sf T}(k)$ denotes the set of vertices at generation $k$. We further assume that the (conditional on ${\sf T}(k)$) first moments of $\Delta_{j}$ are uniformly bounded by a given non-random finite constant $\Delta$ and say that an unlabeled rooted tree ${\sf T}$ is conditionally independent if ${\sf T}\simeq{\sf T}^{\prime}$ for some conditionally independent labeled rooted tree ${\sf T}^{\prime}$.

As shown in [29, Section 4] (see also Theorem 2.10), on such a tree, local expectations are insensitive to boundary conditions that stochastically dominate the free boundary condition. Our program then follows by monotonicity arguments. An example of the monotonicity properties enjoyed by the Ising model is provided by Lemma 2.12.

We next provide a few examples of well known random graph ensembles that are uniformly sparse and converge locally to conditionally independent trees. To this end, let $P=\{P_{k}:\,k\geq 0\}$ be a probability distribution over the non-negative integers, with finite, positive first moment $\overline{P}$, set $\rho_{k}=(k+1)P_{k+1}/\overline{P}$ and denote its mean as $\overline{\rho}$. We denote by ${\sf T}(\rho,t)$ the rooted Galton-Watson tree of $t\geq 0$ generations, i.e. the random tree such that each node has offspring distribution $\{\rho_{k}\}$, and the offspring numbers at different nodes are independent. Further, ${\sf T}(P,\rho,t)$ denotes the modified ensemble where only the offspring distribution at the root is changed to $P$. In particular, ${\sf T}(P,\rho,\infty)$ is clearly conditionally independent. Other examples of conditionally independent trees include: $(a)$ deterministic trees with bounded degree; $(b)$ percolation clusters on such trees; $(c)$ multi-type branching processes.

The following simple observation transfers results from configuration models to the associated uniform models.

Let $A_{n}$ be a sequence of events, such that, under the configuration model

Further, assume $m=\lfloor\alpha n\rfloor$ with $\alpha$ fixed (for Erdös-Renyi random graphs), or $\{P_{k}\}$ fixed, with bounded first moment (for general degree distribution). Then, almost surely under the uniform model, property $A_{n}$ holds for all $n$ large enough.

The point is that, the graph chosen under the configuration model is distributed uniformly when further conditional on the property $L_{n}$ that it has neither self-loops nor double edges (see ). Consequently,

Our next lemma ensures that we only need to check the local (weak) convergence in expectation with respect to the configuration model.

Given a finite rooted tree $T$ of at most $t$ generations, assume that

which is more than enough for completing the proof. $\Box$

Note that for any random graph $G_{n}$ of degree distribution $P$,

Our assumption that $\overline{P}=\sum_{k}kP_{k}$ is finite implies that $\overline{P}_{l}\to 0$ as $l\to\infty$, so any such sequence of graphs $\{G_{n}\}$ is uniformly sparse.

Since $b$ is independent of $n$ and $a=n|T(t-1)|+O(1)$, it is easy to verify that for $n\to\infty$ and $m/n\to\alpha$ the latter expression converges to

As a special case of Proposition 2.5, almost every sequence of uniformly random $k$-regular graphs of $n$ vertices converges locally to the (non-random) rooted $k$-regular infinite tree $T_{k}(\infty)$.

Note that the $k$-canopy tree is not conditionally independent.

2 Ising models on conditionally independent trees

Following it is convenient to extend the model (1.20) by allowing for vertex-dependent magnetic fields $B_{i}$, i.e. to consider

In this general context, it is possible to prove correlation decay results for Ising models on conditionally independent trees. Beyond their independent interest, such results play a crucial role in our analysis of models on sparse graph sequences.

The proof of this theorem, given in [29, Section 4], relies on monotonicity properties of the Ising measure, and in particular on the following classical inequality.

Given a finite set $V$ and parameters ${\underline{J}}=(J_{R},R\subseteq V)$ with $J_{R}\geq 0$, consider the extended ferromagnetic Ising measure

where $\underline{x}\in\{+1,-1\}^{V}$ and $x_{R}\equiv\prod_{u\in R}\,x_{u}$. Then, for $\underline{X}$ of law $\mu_{{\underline{J}}}$ and any $A,B\subseteq V$,

Proof. See [61, Theorem IV.1.21] (and consult for generalizations of this result).

Note that the measure $\mu(\cdot)$ of (2.9) is a special case of $\mu_{{\underline{J}}}$ (taking $J_{\{i\}}=B_{i}$, $J_{\{i,j\}}=\beta$ for all $(i,j)\in E$ and $J_{R}=0$ for all other subsets of $V$). Thus, Griffiths inequalities allow us to compare certain marginals of the latter measure for a graph $G$ and non-negative $\beta$, $B_{i}$ with those for other choices of $G$, $\beta$ and $B_{i}$. To demonstrate this, we state (and prove) the following well known general comparison results.

Fixing $\beta\geq 0$ and $B_{i}\geq 0$, for any finite graph $G=(V,E)$ and $A\subseteq V$ let $\langle x_{A}\rangle_{G}=\mu(x_{A}=1)-\mu(x_{A}=-1)$ denote the mean of $x_{A}$ under the corresponding Ising measure on $G$. Similarly, for $U\subseteq V$ let $\langle x_{A}\rangle^{0}_{U}$ and $\langle x_{A}\rangle^{+}_{U}$ denote the magnetization induced by the Ising measure subject to free (i.e. $x_{u}=0$) and plus (i.e. $x_{u}=+1$) boundary conditions, respectively, at all $u\notin U$. Then, $\langle x_{A}\rangle^{0}_{U}\leq\langle x_{A}\rangle_{G}\leq\langle x_{A}\rangle^{+}_{U}$ for any $A\subseteq U$. Further, $U\mapsto\langle x_{A}\rangle^{0}_{U}$ is monotone non-decreasing and $U\mapsto\langle x_{A}\rangle^{+}_{U}$ is monotone non-increasing, both with respect to set inclusion (among sets $U$ that contain $A$).

Finally, the stated monotonicity of $U\mapsto\langle x_{A}\rangle^{0}_{U}$ and $U\mapsto\langle x_{A}\rangle^{+}_{U}$ are in view of Griffiths inequalities the direct consequence of the monotonicity (with respect to set inclusions) of $U\mapsto{\underline{J}}^{U}$ and $U\mapsto{\underline{J}}^{\eta,U}$, respectively. $\Box$

3 Algorithmic implications: belief propagation

The ‘belief propagation’ (BP) algorithm consists of solving by iterations a collection of Bethe-Peierls (or cavity) mean field equations. More precisely, for the Ising model (1.20) we associate to each directed edge in the graph $i\to j$, with $(i,j)\in G$, a distribution (or ‘message’) $\nu_{i\to j}(x_{i})$ over $x_{i}\in\{+1,-1\}$, using then the following update rule

starting at a positive initial condition, namely where $\nu_{i\to j}^{(0)}(+1)\geq\nu_{i\to j}^{(0)}(-1)$ at each directed edge.

Applying Theorem 2.10 we establish in [29, Section 5] the uniform exponential convergence of the BP iteration to the same fixed point of (2.16), irrespective of its positive initial condition. As we further show there, for tree-like graphs the limit of the BP iteration accurately approximates local marginals of the Boltzmann measure (1.20).

Assume $\beta\geq 0$, $B>0$ and $G$ is a graph of finite maximal degree $\Delta$. Then, there exists $A=A(\beta,B,\Delta)$ and $c=c(\beta,B,\Delta)$ finite, $\lambda=\lambda(\beta,B,\Delta)>0$ and a fixed point $\{\nu^{*}_{i\to j}\}$ of the BP iteration (2.16) such that for any positive initial condition $\{\nu^{(0)}_{l\to k}\}$ and all $t\geq 0$,

Further, for any $i_{o}\in V$, if ${\sf B}_{i_{o}}(t)$ is a tree then for $U\equiv{\sf B}_{i_{o}}(r)$

where $\mu_{U}(\,\cdot\,)$ is the law of $\underline{x}_{U}\equiv\{x_{i}:\,i\in U\}$ under the Ising model (1.20) and $\nu_{U}$ the probability distribution

with $E_{U}$ the edge set of $U$ whose border is $\partial U$ (i.e. the set of its vertices at distance $r$ from $i_{o}$), and $j(i)$ is any fixed neighbor in $U$ of $i$.

4 Free entropy density, from trees to graphs

Bethe-Peierls approximation (we refer to Section 3.1 for a general introduction), allows us to predict the asymptotic free entropy density for sequences of graphs that converge locally to conditionally independent trees. We start by explaining this prediction in a general setting, then state a rigorous result which verifies it for a specific family of graph sequences.

To be definite, assume that $B>0$. Given a graph sequence $\{G_{n}\}$ that converges to a conditionally independent tree ${\sf T}$ with bounded average offspring number, let $L=\Delta_{\o}$ be the degree of its root. Define the ’cavity fields’ $\{h_{1},\dots,h_{L}\}$ by letting $h_{j}=\lim_{t\to\infty}h_{j}^{(t)}$ with $h_{j}^{(t)}\equiv{\rm atanh}[\langle x_{j}\rangle^{(t)}_{j}]$, where $\langle\,\cdot\,\rangle^{(t)}_{j}$ denotes expectation with respect to the Ising distribution on the sub-tree induced by $j\in\partial{\o}$ and all its descendants in ${\sf T}(t)$ (with free boundary conditions). We note in passing that $t\mapsto h_{j}^{(t)}$ is stochastically monotone (and hence has a limit in law) by Lemma 2.12. Further $\{h_{1},\dots,h_{L}\}$ are conditionally independent given $L$. Finally, define $\theta=\tanh(\beta)$ and

The Bethe-Peierls free energy density is given by

for $\gamma(u)=-\frac{1}{2}\log(1-u^{2})$. We refer to Section 3.3 where this formula is obtained as a special case of the general expression for a Bethe-Peierls free energy. The prediction is extended to $B<0$ by letting $\varphi(\beta,B)=\varphi(\beta,-B)$, and to $B=0$ by letting $\varphi(\beta,0)$ be the limit of $\varphi(\beta,B)$ as $B\to 0$.

As shown in [29, Lemma 2.2], when ${\sf T}={\sf T}(P,\rho,\infty)$ is a Galton-Watson tree, the random variables $\{h_{j}\}$ have a more explicit characterization in terms of the following fixed point distribution.

In case ${\sf T}={\sf T}(P,\rho,\infty)$ consider the random variables $\{h^{(t)}\}$ where $h^{(0)}\equiv 0$ and for $t\geq 0$,

The main result of confirms the statistical physics prediction for the free entropy density.

If $\overline{\rho}$ is finite then for any $B\in{\mathds{R}}$, $\beta\geq 0$ and sequence $\{G_{n}\}_{n\in{\mathds{N}}}$ of uniformly sparse graphs that converges locally to ${\sf T}(P,\rho,\infty)$,

We proceed to sketch the outline of the proof of Theorem 2.15. For uniformly sparse graphs that converge locally to ${\sf T}(P,\rho,\infty)$ the model (1.20) has a line of first order phase transitions for $B=0$ and $\beta>\beta_{\rm c}$ (that is, where the continuous function $B\mapsto\varphi(\beta,B)$ exhibits a discontinuous derivative). Thus, the main idea is to utilize the magnetic field $B$ to explicitly break the $+/-$ symmetry, and to carefully exploit the monotonicity properties of the ferromagnetic Ising model in order to establish the result even at $\beta>\beta_{\rm c}$.

Indeed, since $\phi_{n}(\beta,B)\equiv\frac{1}{n}\log Z_{n}(\beta,B)$ is invariant under $B\to-B$ and is uniformly (in $n$) Lipschitz continuous in $B$ with Lipschitz constant one, for proving the theorem it suffices to fix $B>0$ and show that $\phi_{n}(\beta,B)$ converges as $n\to\infty$ to the predicted expression $\varphi(\beta,B)$ of (2.4). This is obviously true for $\beta=0$ since $\phi_{n}(0,B)=\log(2\cosh B)=\varphi(0,B)$. Next, denoting by $\langle\,\cdot\,\rangle_{n}$ the expectation with respect to the Ising measure on $G_{n}$ (at parameters $\beta$ and $B$), it is easy to see that