Random cluster models on random graphs

We follow [23]. Let $G=(V(G),E(G))$ be a finite graph with vertex set $V(G)$ and edge set $E(G)$. We assume that $|V(G)|=n$. The random cluster measure is denoted by $\phi_{p,q}$, and gives a measure on configurations $\bm{\omega}=(\omega(e))_{e\in E}$, where the edge variables $\omega(e)$ satisfy $\omega(e)\in\{0,1\}$. We think of $e$ for which $\omega(e)=1$ as being present, and $e$ for which $\omega(e)=0$ as being vacant. The random cluster measure $\phi_{p,q}$ is given by

(1.1)

$$\phi_{p,q}(\bm{\omega})=\frac{1}{Z_{n,\rm RC}(p,q)}q^{k(\bm{\omega})}\prod_{e\in E(G)}p^{\omega(e)}(1-p)^{1-\omega(e)},$$

where $q>0$ and $p\in[0,1]$, and $k(\bm{\omega})$ denotes the number of connected components of the subgraph $G_{p}$ with vertex set $V(G)$ and edge set $E_{p}(G)=\{e\in E(G)\colon\omega(e)=1\}$. The partition function, or normalising constant, $Z_{n,\rm RC}(p,q)$ is given by

(1.2)

$$Z_{n,\rm RC}(p,q)=\sum_{\bm{\omega}}q^{k(\bm{\omega})}\prod_{e\in E(G)}p^{\omega(e)}(1-p)^{1-\omega(e)},$$

where the sum is over all bond variables $\omega(e)\in\{0,1\}$.

In the above, $q>0$ is general, as it will often be in this paper. We now specialise to $q\in\{1,2,3\ldots\}$, and relate the above model to the Potts model. For this, we need to specify vertex variables $\bm{\sigma}=(\sigma_{x})_{x\in V(G)}\in[q]^{V(G)}$, where $[q]=\{1,\ldots,q\}$. We first define a joint law $\mu_{p,q}(\bm{\sigma},\bm{\omega})$ given by

(1.3)

$$\mu_{p,q}(\bm{\sigma},\bm{\omega})=\frac{1}{Z_{n}(p,q)}\prod_{\{x,y\}\in E(G)}\Big{[}(1-p){\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\{\omega(\{x,y\})=0\}}+p{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\{\omega(\{x,y\})=1\}}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\{\sigma_{x}=\sigma_{y}\}}\Big{]},$$

where the partition function, or normalising constant, $Z_{n}(p,q)$ is now given by

(1.4)

$$Z_{n}(p,q)=\sum_{\bm{\sigma},\bm{\omega}}\prod_{\{x,y\}\in E(G)}\Big{[}(1-p){\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\{\omega(\{x,y\})=0\}}+p{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\{\omega(\{x,y\})=1\}}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\{\sigma_{x}=\sigma_{y}\}}\Big{]},$$

and the sum is over all bond variables $\omega(e)\in\{0,1\}$ and vertex variables $\sigma_{v}\in[q]$ for all $v\in V(G)$.

The key coupling result is that (cf. [23, Theorem (1.10)]) for $p=1-{\rm e}^{-\beta}$ and $q\in{\mathbb{N}}$, the spin marginal $\bm{\sigma}\mapsto\mu_{p,q}(\bm{\sigma})$ obtained by summing out over the bond variables is the Potts model with parameters $\beta$ and $q$, while the bond marginal $\bm{\omega}\mapsto\mu_{p,q}(\bm{\omega})$ obtained by summing out over the vertex spins is the random cluster measure.

Equations (1.3)–(1.4) define the random cluster and Potts model without an external field, and we now extend it to an external field. For this, we define the Potts model partition function, with inverse temperature $\beta\geq 0$ and external field $B$, as

(1.5)

$$Z_{G}^{\scriptscriptstyle\rm Potts}(q,\beta,B)=\sum_{\bm{\sigma}\in[q]^{V(G)}}{\rm e}^{-H(\bm{\sigma})},$$

where

(1.6)

$$H(\bm{\sigma})=H_{\beta,B}(\bm{\sigma})=-\beta\sum_{\{u,v\}\in E(G)}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\{\sigma_{u}=\sigma_{v}\}}-B\sum_{v\in V(G)}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\{\sigma_{v}=1\}}.$$

Note that $Z_{G}^{\scriptscriptstyle\rm Potts}(q,\beta,0)={\rm e}^{-\beta|E(G)|}Z_{n}(p,q)$ with $p=1-{\rm e}^{-\beta}$, but that will play no role in what follows. In this paper, we investigate this partition function, as well as its random cluster model extension, which we define next.

We next define the main object of study, which is the random cluster model with a weight that we think of as an external field. For Potts and Ising models, this weighted model is exactly the Potts/Ising model with an external field, while the definition extends to non-integer $q$. Let $q>1$ be a positive real number, and $w={\rm e}^{\beta}-1$. Then, we define the random cluster measure with external field $B$, inspired by [7], by

(1.7)

$$\mu_{G}(\bm{\omega})=\frac{W(\bm{\omega})}{Z_{G}(q,w,B)},\qquad\text{and}\qquad W(\bm{\omega})=\prod_{e\in E(G)}w^{\omega_{e}}\prod_{C\in\mathscr{C}(\bm{\omega})}(1+(q-1){\rm e}^{-B|C|}),$$

where the normalisation constant $Z_{G}(q,w,B)$ is given by

(1.8)

$$Z_{G}(q,w,B)=\sum_{\bm{\omega}}\prod_{e\in E(G)}w^{\omega_{e}}\prod_{C\in\mathscr{C}(\bm{\omega})}(1+(q-1){\rm e}^{-B|C|}),$$

where $\mathscr{C}(\bm{\omega})$ is the collection of connected components in $\bm{\omega}$. It is this measure that we will focus on in this paper. The following lemma relates the partition function for the Potts model with external field $B$ to $Z_{G}(q,w,B):$

We next describe the random graph models that we will be working on.

In the above, the finite graph $G=(V(G),E(G))$ is general. Here, we introduce the kind of random graphs that we shall work on. We will consider graph sequences $(G_{n})_{n\geq}$ of growing size, where $G_{n}=(V(G_{n}),E(G_{n}))$, with $V(G_{n})$ and $E(G_{n})$ denoting the vertex and edge sets of $G_{n}$, respectively. We assume that $|V(G_{n})|=n$, and assume that $n$ tends to infinity.

We will strongly rely on local convergence, as introduced by Benjamini and Schramm in [6], and, independently by Aldous and Steele in [2]. We refer to [25, Chapter 2] for an overview of the theory, and [25, Chapters 3-5] for several examples. By [5], (1.9) implies that the graph sequence $(G_{n})_{n\geq}$ is precompact in the local topology, meaning that every subsequence has a further subsequence that converges in the local topology. See also [1] for further discussion. Our main assumption is that the graph sequence $(G_{n})_{n\geq}$ is locally tree-like:

Conditions 1.2 and 1.3 have a long history in considering Ising and Potts models on random graphs. See e.g., [13, 12, 14, 16] for some of the relevant references. Below, and throughout the paper, we call a graph sequence $(G_{n})_{n\geq}$ locally tree-like when Conditions 1.2 and 1.3 both hold.

This section is organised as follows. We start by describing our main results, which are divided into three parts. In Section 1.3, we rewrite the random cluster partition function with general external field $B>0$ in terms of an extended Ising model with specific vertex-dependent external fields. In Section 1.4, we use this representation to give a lower bound on the partition function by the Bethe partition function. In Section 1.5, we use these results to analyse the phase transition of the Potts model on random $d$-regular graphs. In Section 1.6, we describe the results for the extended Ising model, and their consequences on the random cluster model for high external magnetic fields and low temperature. We close in Section 1.7 by discussing our results and stating open problems.

We first give bounds on the partition function of the random cluster model with external field, extending the work of Bencs, Borbényi and Csikváry [4] to non-zero external fields:

The proof of Theorem 1.4 is given in Section 2, and closely follows Bencs, Borbényi and Csikváry [4].

We next use Theorem 1.4 to investigate the pressure per particle of the random cluster model. We can trivially bound

(1.13)

$$\mathcal{L}(G)\leq\frac{|V(G)|}{k}+\sum_{i=2}^{k-1}\mathcal{L}_{i}(G),$$

where

(1.14)

$$\mathcal{L}_{i}(G)=\max\{l\colon G\leavevmode\nobreak\ \text{\rm contains $l$ vertex-disjoint cycles of length $i$}\}.$$

In particular, for graphs $G_{n}=(V(G_{n}),E(G_{n}))$ on $|V(G_{n})|=n$ vertices, having a locally tree-like limit, we can bound

(1.15)

$$\frac{1}{n}\mathcal{L}(G_{n})\leq\frac{1}{k}+\frac{1}{n}\sum_{i=2}^{k-1}\mathcal{L}_{i}(G_{n})\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\frac{1}{k},$$

since $\mathcal{L}_{i}(G_{n})/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}0$ by the fact that the local limit is tree-like (recall Condition 1.3). Since $k$ is arbitrary, it follows that

(1.16)

$$\frac{1}{n}\log Z_{G_{n}}(q,w,B)=\frac{1}{n}\log Z_{G_{n}}^{\scriptscriptstyle(2)}(q,w,B)+o(1).$$

Thus, the pressure per particle for the random cluster model is the same as that for the rank-2 approximation, as will be a guiding principle for this paper:

We continue by investigating the rank-2 approximation $Z^{\scriptscriptstyle(2)}_{G_{n}}(q,w,B)$ in more detail.

We next write the expressions in (1.12) in terms of two-spin models, which will turn out to be general Ising models with vertex-dependent external fields. Define

(1.18)

$$Z_{G}(\psi,\overline{\psi})=\sum_{\bm{\sigma}\in\{+,-\}^{V(G)}}\prod_{v\in V(G)}\overline{\psi}(\sigma_{v})\prod_{\{u,v\}\in E(G)}\psi(\sigma_{u},\sigma_{v}),$$

where we use a slight abuse of notation and write $+$ instead of $+1$ and $-$ instead of $-1$. Sly and Sun [29] show that any two-spin model on regular graphs can be mapped to an Ising model, which can be ferro- or antiferromagnetic. Our second main result rewrites the partition function of the rank-2 approximation of the random cluster model with inverse temperature $\beta$ and external field $B$ in terms of the partition function of a ferromagnetic two-spin model:

With Theorem 1.6 in hand, we now set to reformulating this result in terms of ferromagnetic Ising models.

We next turn to Sly and Sun [29], who investigate general two-spin models, and relate them to Ising models. Note that

(1.22)

$$Z_{G}(\psi,\overline{\psi})=(\overline{\psi}(+)\overline{\psi}(-))^{n/2}\sum_{\bm{\sigma}\in\{-1,1\}^{V(G)}}\prod_{v\in V(G)}{\rm e}^{h\sigma_{v}}\prod_{\{u,v\}\in E(G)}\psi(\sigma_{u},\sigma_{v}),$$

where

(1.23)

$${\rm e}^{2h}=\frac{\overline{\psi}(+)}{\overline{\psi}(-)},$$

so that

(1.24)

$$h=\frac{1}{2}\log(\overline{\psi}(+)/\overline{\psi}(-))=\frac{1}{2}\log({\rm e}^{B}/(q-1)).$$

Then, since $\psi>0$, we can rewrite (see [29, page 2393])

(1.25)

$$\psi(\sigma,\sigma^{\prime})={\rm e}^{B_{0}}{\rm e}^{\beta^{*}\sigma\sigma^{\prime}}{\rm e}^{k(\sigma+\sigma^{\prime})},$$

where the parameters $B_{0}$, $k$ and $\beta^{*}$ are determined by

(1.26)		$\displaystyle\frac{\psi(+,+)}{\psi(-,-)}$	$\displaystyle={\rm e}^{4k},$
(1.27)		$\displaystyle\frac{\psi(+,+)\psi(-,-)}{\psi(+,-)^{2}}$	$\displaystyle={\rm e}^{4\beta^{*}},$
(1.28)		$\displaystyle\psi(+,+)\psi(+,-)^{2}\psi(-,-)$	$\displaystyle={\rm e}^{4B_{0}}.$

Thus,

(1.29)

$$k=\frac{1}{4}\log\left(\frac{1+w}{1+w/(q-1)}\right),$$

and, by (1.20) and (1.27),

(1.30)

$$(1+w/(q-1))(1+w)={\rm e}^{4\beta^{*}},$$

so that

(1.31)

$$\beta^{*}=\frac{1}{4}\log((1+w)(1+w/(q-1))),$$

while, by (1.20) and (1.28),

(1.32)

$$(1+w/(q-1))(1+w)={\rm e}^{4B_{0}},$$

so that

(1.33)

$$B_{0}=\frac{1}{4}\log((1+w)(1+w/(q-1)))=\beta^{*}.$$

We conclude that

(1.34)

$$Z_{G}(\psi,\overline{\psi})=({\rm e}^{-B}(q-1))^{n/2}{\rm e}^{\beta^{*}|E(G)|}Z_{G}^{\scriptscriptstyle\rm eIsing}(\beta^{*},k,h),$$

where we define the partition function of the extended Ising model as

(1.35)

$$Z_{G}^{\scriptscriptstyle\rm eIsing}(\beta^{*},k,h):=\sum_{\bm{\sigma}\in\{-1,1\}^{V(G)}}\exp\left(\beta^{*}\sum_{\{u,v\}\in E(G)}\sigma_{u}\sigma_{v}+\sum_{v\in V(G)}(kd_{v}+h)\sigma_{v}\right),$$

and $d_{v}=d_{v}(G)$ is the degree of vertex $v\in V(G)$. This Ising model is unusual, due to the vertex-dependent external fields, which are governed by the degrees of the vertices in the graph. We defer a discussion of the parameters to below Corollary 1.7.

The above computations lead to the following two corollaries:

Let us make some observations at this point:

Let $G_{n}$ be locally tree-like $d$-regular graph having $|V(G_{n})|=n$ vertices. Let us denote $\varphi^{\rm\scriptscriptstyle Ising}(\beta,B)$ as the pressure per particle of the Ising model with inverse temperature $\beta\geq 0$ and external field $B\in\mathbb{R}$, i.e.,

(1.47)

$$\frac{1}{n}\log Z_{G_{n}}^{\scriptscriptstyle\rm Ising}(\beta,B)\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\varphi^{\rm\scriptscriptstyle Ising}(\beta,B).$$

This limit exists by [13], see also [12, 14, 16, 17] for related results. Our first result shows that the pressure per particle exists for all $\beta,B$:

Due to the link to the Ising model (where now the external fields are constant) in Corollary 1.8, this result follows directly from the literature, in particular [13]. We refer to [12, 14, 16, 17] for related results, and [26] for an overview of the Ising model on locally tree-like random graphs. The whole point is that these references prove that the pressure per particle for Ising models exists for all locally tree-like random graphs, and fixed external fields.

We next analyse the phase transition in terms of $\beta$. For $q>2$, the phase transition when $B=0$ follows from the analysis by Bencs, Borbényi and Csikváry in [4]. We will show that the first-order phase transition persists for certain positive external fields $B>0$.

For $q\geq 2$ and $d\geq 3$, define

(1.51)

$$\ell_{q,d}(x)=\frac{x^{2/d}-1}{1-\tfrac{1}{q-1}x^{2/d}},$$

and

(1.52)

$$w_{c}(B):=\ell_{q,d}((q-1){\rm e}^{-B})$$

Then the critical curve is defined by

(1.53)

$$\mathscr{C}=\{(w,B):w=w_{c}(B),\,0\leq B<B_{+}\},$$

where $B_{+}>0$ is the unique positive solution of

(1.54)

$$(1+w_{c}(B))(1+w_{c}(B)/(q-1))=\left(\frac{d}{d-2}\right)^{2}.$$

The following theorem describes the first-order phase transition of random cluster model:

We close this section by explaining the relation to the work of Basak, Dembo and Sly in [3] that studies the $q$-states Potts model on locally tree-like regular graphs with an external field. In this paper, [3, Assumption 1.4] makes an assumption about the form of the pressure per particle in this setting that roughly states that the quenched and annealed pressure per particle agree. More precisely, [3, Assumption 1.4] states that the quenched pressure per particle is the same as the Bethe functional. Our results allow us to prove this assumption. We first show that the quenched and annealed pressure per particle are the same for random $d$-regular graphs, which will be an essential ingredient in the proof:

Theorem 1.14 has the following direct consequence, showing that the pressure per particle equals the Bethe functional: