THE RANDOM-CLUSTER MODEL

Geoffrey Grimmett

Abstract. The class of random-cluster models is a unification of a variety of stochastic processes of significance for probability and statistical physics, including percolation, Ising, and Potts models; in addition, their study has impact on the theory of certain random combinatorial structures, and of electrical networks. Much (but not all) of the physical theory of Ising/Potts models is best implemented in the context of the random-cluster representation. This systematic summary of random-cluster models includes accounts of the fundamental methods and inequalities, the uniqueness and specification of infinite-volume measures, the existence and nature of the phase transition, and the structure of the subcritical and supercritical phases. The theory for two-dimensional lattices is better developed than for three and more dimensions. There is a rich collection of open problems, including some of substantial significance for the general area of disordered systems, and these are highlighted when encountered. Amongst the major open questions, there is the problem of ascertaining the exact nature of the phase transition for general values of the cluster-weighting factor q, and the problem of proving that the critical random-cluster model in two dimensions, with 1 ≤ q ≤ 4, converges when re-scaled to a stochastic Löwner evolution (SLE). Overall the emphasis is upon the random-cluster model for its own sake, rather than upon its applications to Ising and Potts systems.

List of contents

1. Introduction

2. Potts and random-cluster measures 2.1 Random-cluster measures 2.2 Ising and Potts models 2.3 Random-cluster and Ising/Potts coupled 2.4 The limit as q ↓ 0 2.5 Rank-generating functions

3. Infinite-volume random-cluster measures 3.1 Stochastic ordering 3.2 A differential formula 3.3 Conditional probabilities 3.4 Infinite-volume weak limits 3.5 Random-cluster measures on infinite graphs 3.6 The case q < 1

4. Phase transition, the big picture 4.1 Infinite open clusters

Mathematics Subject Classification (2000). 60K35, 82B20, 82B43. Key words and phrases. Random-cluster model, FK model, percolation, Ising model, Potts

model, phase transition.

4.2 First- and second-order phase transition 5. General results in d (≥ 2) dimensions

5.1 The subcritical phase, p < p_{c}(q) 5.2 The supercritical phase, p > p_{c}(q) 5.3 Near the critical point, p ≃ p_{c}(q)

6. In two dimensions 6.1 Graphical duality 6.2 Value of the critical point 6.3 First-order phase transition 6.4 SLE limit when q ≤ 4

7. On complete graphs and trees 7.1 On complete graphs 7.2 On trees and non-amenable graphs

8. Time-evolutions of random-cluster models 8.1 Reversible dynamics 8.2 Coupling from the past 8.3 Swendsen–Wang dynamics

1. Introduction

During a classical period, probabilists studied the behaviour of independent random variables. The emergent theory is rich, and is linked through theory and application to areas of pure/applied mathematics and to other sciences. It is however unable to answer important questions from a variety of sources concerning large families of dependent random variables. Dependence comes in many forms, and one of the targets of modern probability theory has been to derive robust techniques for studying it. The voice of statistical physics has been especially loud in the call for rigour in this general area. In a typical scenario, we are provided with an infinity of random variables, indexed by the vertices of some graph such as the cubic lattice, and which have some dependence structure governed by the geometry of the graph. Thus mathematicians and physicists have had further cause to relate probability and geometry. One major outcome of the synthesis of ideas from physics and probability is the theory of Gibbs states, [59], which is now established as a significant branch of probability theory.

A classic example of a Gibbs state is the (Lenz–)Ising model [88] for a ferromagnet. When formulated on the bounded region B of the square lattice 𝕃^{2}, a random variable σ_{x} taking values −1 and +1 is assigned to each vertex x of B, and the probability of the configuration σ is proportional to exp(−βH(σ)), where β > 0 and the ‘energy’ H(σ) is the negative of the sum of σ_{x}σ_{y} over all neighbouring pairs x, y of B. This ‘starter model’ has proved extraordinarily successful in generating beautiful and relevant mathematics, and has been useful and provocative in the mathematical theory of phase transitions and cooperative phenomena (see, for example, [51]).

There are many possible generalisations of the Ising model in which the σ_{x} may take a general number q of values, rather than q = 2 only. One such generalisation, the so-called Potts model [125], has attracted especial interest amongst physicists, and has displayed a complex and varied structure; for example, when q is large, it enjoys a discontinuous phase transition, in contrast to the continuous transition believed to take place for small q. Ising/Potts models are the first of three principal ingredients in the story of random-cluster models. Note that they are ‘vertex models’ in the sense that they involve random variables σ_{x} indexed by the vertices x of the underlying graph.

The ‘(bond) percolation model’ was inspired by problems of physical type, and emerged from the mathematics literature of the 1950s [30, 148]. In this model for a porous medium, each edge of a graph is declared ‘open’ (to the passage of fluid) with probability p, and ‘closed’ otherwise, different edges having independent states. The problem is to determine the typical large-scale properties of connected components of open edges, as the parameter p varies. Percolation theory is now a mature part of probability, at the core of the study of random media and interacting systems, and it is the second ingredient in the story of random-cluster models. Note that bond percolation is an ‘edge model’, in that the random variables are indexed by the set of edges of the underlying graph. [There is a variant termed ‘site percolation’ in which the vertices are open/closed at random rather than the edges.]

The third and final ingredient preceded the first two, and is the theory of electrical networks. Dating back at least to the 1847 paper [101] of Kirchhoff, this sets down a method for calculating macroscopic properties of an electrical network in terms of its local structure. In particular, it explains the relevance of counts of certain types of spanning trees of the graph. In the modern vernacular, an electrical network on a graph G may be studied via the properties of a ‘uniformly random spanning tree’ on G (see [17]).

These three ingredients seemed fairly distinct until Fortuin and Kasteleyn discovered, around 1970, [53, 54, 55, 93], that each features in a certain way within a family of probability measures of ‘edge models’, parameterised by two quantities, p ∈ [0, 1] and q ∈ (0, ∞). [In actuality, electrical networks arise as a weak limit of such measures.] These models they termed ‘random-cluster models’, and they developed the basic theory — correlation inequalities and the like — in a series of papers published thereafter. The true power of random-cluster models as a mechanism for studying Ising/Potts models has emerged only gradually over the intervening thirty years.

We note in passing that the genesis of the random-cluster model lay in Kasteleyn’s observation that each of the three ingredients above satisfies certain series/parallel laws: any two edges in series (or parallel) may be replaced by a single edge in such a way that, if the interaction function is adapted accordingly, then the distributions of large-scale properties remain unchanged.

The family of random-cluster measures (that is, probability measures which govern random-cluster models) is not an extension of the Potts measures. The relationship is more sophisticated, and is such that correlations for Potts models correspond to connections in random-cluster models. Thus the correlation structure of a Potts model may be studied via the stochastic geometry of a corresponding random-cluster model. The intuition behind this geometrical study comes often from percolation, of which the random-cluster model is indeed an extension.

It turns out that, in many situations involving ferromagnetic Ising/Potts models, the best way forward is via the random-cluster model. As examples of this we mention the existence of discontinuous phase transitions [104], exact computations in two dimensions [15], the verification of the Wulff construction for Ising droplets [36], and the Dobrushin theory of interfaces and non-translation-invariant measures [62]. As a major exception to the mantra ‘everything worth doing for Ising/Potts is done best via random-cluster’, we remind the reader of the so-called randomcurrent expansion for the Ising model, wielded with effect in [1, 2, 5] and elsewhere. The random-current method appears to be Ising-specific, and has enabled a deep analysis of the Ising model unparalleled in more general Potts systems. (See Section 5.3.)

The primary target of this review is to summarise and promote the theory of random-cluster models for its own sake. In doing so, we encounter many results having direct impact on Ising/Potts systems, but we shall not stress such connections. Some of the theory has been discovered several times by apparently independent teams; whilst making a serious attempt to list key references, we apologise for unwitting omissions of which there will certainly be a few. The large number of references to work of the author is attributable in part to the fact that he is acquainted with these contributions.

It is a lesson in humility to return to the original Fortuin–Kasteleyn papers [53, 55], and especially [54], where so much of the basic theory was first presented. These authors may not have followed the slickest of routes, but they understood rather well the object of their study. Amongst the many papers of general significance since, we highlight: [4], which brought the topic back to the fore; [47], where the coupling between Potts and random-cluster models was so beautifully managed; [69], where the random-cluster model was studied systematically on infinite grids; [80], which links the theory to several other problems of interest in statistical mechanics; and [61], where random-cluster models are placed in the perspective of stochastic geometry as a tool for studying phase transitions.

This review is restricted mostly to core material for random-cluster models on the nearest-neighbour cubic lattice in a general number d of dimensions. Only in passing do we mention such subjects as extensions to long-range systems [4], meanfield behaviour in high dimensions [98], and mixing properties [7]. Neither do we stress the impact that graphical methods of the random-cluster type have had on a variety of other disordered systems, such as the Ashkin–Teller model [13, 80, 121, 131, 146], the Widom–Rowlinson model [39, 40, 60, 80, 144], or on methods for simulating disordered physical systems [41, 42, 140, 147].

Random-cluster methods may be adapted to systems with random interactions [3, 72, 80], and even to non-ferromagnetic systems of Edwards–Anderson spin-glass type [46, 116, 117] where, for example, they have been used to prove that, for a given set {J_{e}} of positive or negative interactions, uniqueness of the infinite-volume Gibbs measure for the ferromagnetic system having interactions {|J_{e}|} implies uniqueness for the original system.

Amongst earlier papers on random-cluster models, the following include a degree of review material: [4, 24, 61, 66, 80, 112].

Notwithstanding the fairly mature theory which has evolved, there remain many open problems including some of substantial significance for the general area. Many of these are marked in the text with the acronym OP.

2. Potts and random-cluster processes

We write μ(f) for the expectation of a random variable f under a probability measure μ.

2.1 Random-cluster measures

Let G = (V, E) be a finite graph. An edge e having endvertices x and y is written as e = ⟨x, y⟩. A random-cluster measure on G is a member of a certain class of probability measures on the set of subsets of the edge set E. We take as state space the set Ω = {0, 1}^{E}, members of which are vectors ω = (ω(e) : e ∈ E). We speak of the edge e as being open (in ω) if ω(e) = 1, and as being closed if ω(e) = 0. For ω ∈ Ω, let η(ω) = {e ∈ E : ω(e) = 1} denote the set of open edges, and let k(ω) be the number of connected components (or ‘open clusters’) of the graph (V, η(ω)). Note that k(ω) includes a count of isolated vertices, that is, of vertices incident to no open edge. We assign to Ω the σ-field F of all its subsets.

A random-cluster measure on G has two parameters satisfying 0 ≤ p ≤ 1 and q > 0, and is the measure ϕ_{p,q} on the measurable pair (Ω, F) given by

ϕ_{p,q}(ω) = \frac{1}{Z} \{ ∏_{e∈E} p^{ω(e)}(1 − p)^{1−ω(e)}\}q^{k(ω)}, ω ∈ Ω,

where the ‘partition function’, or ‘normalising constant’, Z is given by

Z = ∑_{ω∈Ω}{ ∏_{e∈E} p^{ω(e)}(1 − p)^{1−ω(e)}}q^{k(ω)}.

This measure differs from product measure only through the inclusion of the term q^{k(ω)}. Note the difference between the cases q ≤ 1 and q ≥ 1: the former favours fewer clusters, whereas the latter favours many clusters. When q = 1, edges are open/closed independently of one another. This very special case has been studied in detail under the titles percolation and random graphs; see [26, 71, 89]. Perhaps the most important values of q are the integers, since the random-cluster model with q ∈ {2, 3, … } corresponds, in a way sketched in the next two sections, to the Potts model with q local states. The bulk of this review is devoted to the theory of random-cluster measures when q ≥ 1. The case q < 1 seems to be harder mathematically and less important physically. There is some interest in the limit as q ↓ 0; see Sections 2.4 and 3.6.

We shall sometimes write ϕ_{G,p,q} for ϕ_{p,q}, when the choice of graph G is to be stressed. Samples from random-cluster measures on ℤ^{2} are presented in Figure 2.1.

2.2 Ising and Potts models

In a famous experiment, a piece of iron is exposed to a magnetic field. The field is increased from zero to a maximum, and then diminishes to zero. If the temperature is sufficiently low, the iron retains some ‘residual magnetisation’, otherwise it does not. There is a critical temperature for this phenomenon, often called the Curie point. The famous (Lenz–)Ising model for such ferromagnetism, [88], may be summarised as follows. One supposes that particles are positioned at the points of

p = 0.30  p = 0.45  p = 0.49 p = 0.51  p = 0.55  p = 0.70

Figure 2.1. Samples from the random-cluster measure with q = 1 on the box [0, 40]^{2} of the square lattice. We have set q = 1 for ease of programming, the measure being of product form in this case. The critical value is p_{c}(1) = \frac{1}{2} . Samples with more general values of q may be obtained by the method of ‘coupling from the past’, as described in Section 8.2.

some lattice in Euclidean space. Each particle may be in either of two states, representing the physical states of ‘spin up’ and ‘spin down’. Spin-values are chosen at random according to a certain probability measure, known as a Gibbs state, which is governed by interactions between neighbouring particles. This measure may be described as follows.

Let G = (V, E) be a finite graph. We think of each vertex v ∈ V as being occupied by a particle having a random spin. Since spins are assumed to come in two basic types, we take as sample space the set Σ = {−1, +1}^{V}. The appropriate probability mass function λ_{β,J,h} on Σ has three parameters satisfying 0 ≤ β, J < ∞ and h ∈ ℝ, and is given by

λ_{β,J,h}(σ) = \frac{1}{Z_{I}} e^{−βH(σ)}, σ ∈ Σ,

where the partition function Z_{I} and the ‘Hamiltonian’ H : Σ → ℝ are given by

Z_{I} = ∑_{σ∈Σ} e^{−βH(σ)}, H(σ) = − ∑_{e=⟨x,y⟩∈E} Jσ_{x}σ_{y} − h ∑_{x∈V} σ_{x}.

The physical interpretation of β is as the reciprocal 1/T of temperature, of J as the strength of interaction between neighbours, and of h as the external field. For reasons of simplicity, we shall consider only the case of zero external field, and we assume henceforth that h = 0. Each edge has equal interaction strength J in the above formulation. Since β and J occur only as a product βJ, the measure λ_{β,J,0} has effectively only a single parameter. In a more complicated measure not studied here, different edges e are permitted to have different interaction strengths J_{e}.

As pointed out by Baxter, [15], the Ising model permits an infinity of generalisations. Of these, the extension to so-called ‘Potts models’ has proved especially fruitful. Whereas the Ising model permits only two possible spin-values at each vertex, the Potts model [125] permits a general number q ∈ {2, 3, … }, and is given as follows.

Let q be an integer satisfying q ≥ 2, and take as sample space Σ = {1, 2, …, q}^{V}. Thus each vertex of G may be in any of q states. The relevant probability measure is now given by

π_{β,J,q}(σ) = \frac{1}{Z_{P}} e^{−βH′(σ)}, σ ∈ Σ,

where Z_{P} is the appropriate normalising constant,

H′(σ) = − ∑_{e=⟨x,y⟩} Jδ_{σ_{x},σ_{y}},

and δ_{u,v} is the Kronecker delta. When q = 2, we have that δ_{σ_{x},σ_{y}} = \frac{1}{2}(1 + σ_{x}σ_{y}). It is now easy to see in this case that the ensuing Potts model is simply the Ising model with an adjusted value of J.

2.3 Random-cluster and Ising–Potts coupled

It was Fortuin and Kasteleyn [53, 54, 55, 93] who discovered that Potts models may be recast as random-cluster models, and furthermore that the relationship between the two systems facilitates an extended study of phase transitions in Potts models. Their methods were essentially combinatorial. In the more modern game, we construct the two systems on a common probability space, and then observe their relationship through their realisations. There may in principle be many ways to do this, but the standard coupling reported in [47] is of special value.

Let q ∈ {2, 3, … }, 0 ≤ p ≤ 1, and let G = (V, E) be a finite graph, as before. We consider the product sample space Σ×Ω where Σ = {1, 2, …, q}^{V} and Ω = {0, 1}^{E} as above. We now define a probability mass function μ on Σ × Ω by

μ(σ, ω) ∝ ∏_{e∈E}{(1 − p)δ_{ω(e),0} + pδ_{ω(e),1}δ_{e}(σ)}, (σ, ω) ∈ Σ × Ω,

where δ_{e}(σ) = δ_{σ_{x},σ_{y}} for e = ⟨x, y⟩ ∈ E. Elementary calculations reveal the following facts.

(a) Marginal on Σ. The marginal measure μ_{1}(σ) = ∑_{ω∈Ω} μ(σ, ω) is given by

μ_{1}(σ) ∝ exp{β ∑_{e} Jδ_{e}(σ)}

where p = 1 − e^{−βJ}. This is the Potts measure.

(b) Marginal on Ω. The second marginal of μ is

μ_{2}(ω) = ∑_{σ∈Σ} μ(σ, ω) ∝ {∏_{e} p^{ω(e)}(1 − p)^{1−ω(e)}}q^{k(ω)}.

This is the random-cluster measure.

(c) The conditional measures. Given ω, the conditional measure on Σ is obtained by putting (uniformly) random spins on entire clusters of ω (of which there are k(ω)). These spins are constant on given clusters, and are independent between clusters. Given σ, the conditional measure on Ω is obtained by setting ω(e) = 0 if δ_{e}(σ) = 0, and otherwise ω(e) = 1 with probability p (independently of other edges).

In conclusion, the measure μ is a coupling of a Potts measure π_{β,J,q} on V, together with the random-cluster measure ϕ_{p,q} on Ω. The parameters of these measures are related by the equation p = 1−e^{−βJ}. Since 0 ≤ p ≤ 1, this is possible only if βJ ≥ 0.

This special coupling may be used in a particularly simple way to show that correlations in Potts models correspond to open connections in random-cluster models. When extended to infinite graphs, this implies as discussed in Section 4 that the phase transition of a Potts model corresponds to the creation of an infinite open cluster in the random-cluster model. Thus arguments of stochastic geometry, and particularly those developed for the percolation model, may be harnessed directly in order to understand the correlation structure of the Potts system. The basic step is as follows.

We write {x ↔ y} for the set of all ω ∈ Ω for which there exists an open path joining vertex x to vertex y. The complement of the event {x ↔ y} is denoted {x ↮ y}.

The ‘two-point correlation function’ of the Potts measure π_{β,J,q} on the finite graph G = (V, E) is defined to be the function τ_{β,J,q} given by

τ_{β,J,q}(x, y) = π_{β,J,q}(σ_{x} = σ_{y}) − \frac{1}{q}, x, y ∈ V.

The term q^{−1} is the probability that two independent and uniformly distributed spins are equal. The ‘two-point connectivity function’ of the random-cluster measure ϕ_{p,q} is defined as the function ϕ_{p,q}(x ↔ y) for x, y ∈ V, that is, the probability that x and y are joined by a path of open edges. It turns out that these ‘two-point functions’ are (except for a constant factor) the same.

Theorem 2.1 (Correlation/connection) [93]. If q ∈ {2, 3, … } and p = 1 − e^{−βJ} satisfies 0 ≤ p ≤ 1, then

τ_{β,J,q}(x, y) = (1 − q^{−1})ϕ_{p,q}(x ↔ y), x, y ∈ V.

Proof. The indicator function of an event A is denoted 1_{A}. We have that

τ_{β,J,q}(x, y) = ∑_{σ,ω}{1_{{σ_{x}=σ_{y}}}(σ) − q^{−1}}μ(σ, ω)

= ∑_{ω} ϕ_{p,q}(ω) ∑_{σ} μ(σ | ω){1_{{σ_{x}=σ_{y}}}(σ) − q^{−1}}

= ∑_{ω} ϕ_{p,q}(ω){(1 − q^{−1})1_{{x↔y}}(ω) + 0 · 1_{{x↮y}}(ω)}

= (1 − q^{−1})ϕ_{p,q}(x ↔ y),

where μ is the above coupling of the Potts and random-cluster measures. □

The theorem may be generalised as follows. Suppose we are studying the Potts model, and are interested in some ‘observable’ f : Σ → ℝ. The mean value of f(σ) satisfies

π_{β,J,q}(f) = ∑_{σ} f(σ)π_{β,J,q}(σ) = ∑_{σ,ω} f(σ)μ(σ, ω)

= ∑_{ω} F (ω)ϕ_{p,q}(ω) = ϕ_{p,q}(F)

where F : Ω → ℝ is given by

F (ω) = μ(f | ω) = ∑_{σ} f(σ)μ(σ | ω).

The above theorem is obtained in the case f(σ) = δ_{σ_{x},σ_{y}} − q^{−1}, where x, y ∈ V.

The Potts models considered above have zero external field. Some complications arise when an external field is added; see the discussions in [8, 24].

2.4 The limit as q ↓ 0

Let G = (V, E) be a finite connected graph, and let ϕ_{p,q} be the random-cluster measure on the associated sample space Ω = {0, 1}^{E}. We consider first the weak limit of ϕ_{p,q} as q ↓ 0 for fixed p ∈ (0, 1). This limit may be ascertained by observing that the dominant terms in the partition function

Z(p, q) = ∑_{ω∈Ω} p^{|η(ω)|}(1 − p)^{|E\η(ω)|}q^{k(ω)}

are those for which k(ω) is a minimum, that is, those with k(ω) = 1. It follows that lim_{q↓0} ϕ_{p,q} is precisely the product measure ϕ_{p,1} (that is, percolation with intensity p) conditioned on the resulting graph (V, η(ω)) being connected. A more interesting limit arises if we allow p to converge to 0 with q, as follows.

The random-cluster model originated in a systematic study by Fortuin and Kasteleyn of systems of a certain type which satisfy certain parallel and series laws. Electrical networks are the best known such systems — two parallel (respectively, series) connections of resistances r_{1} and r_{2} may be replaced by a single connection with resistance (r_{1}^{−1} + r_{2}^{−1})^{−1} (respectively, r_{1} + r_{2}). Fortuin and Kasteleyn [55] realised that the electrical-network theory of a graph G is related to the limit as q ↓ 0 of the random-cluster model on G. Their argument may be expanded as follows.

Suppose p = p_{q} is related to q in such a way that p → 0 and q/p → 0 as q → 0. We may write Z(p, q) as

Z(p, q) = (1 − p)^{|E|} ∑_{ω∈Ω} (\frac{p}{1 − p})^{|η(ω)|+k(ω)} (\frac{q(1 − p)}{p})^{k(ω)} .

Note that p/(1 − p) → 0 and q(1 − p)/p → 0 as q → 0. Now k(ω) ≥ 1 and |η(ω)| + k(ω) ≥ |V | for all ω ∈ Ω; these two inequalities are satisfied simultaneously with equality if and only if η(ω) is a spanning tree of G. It follows that, in the limit as q → 0, the ‘mass’ is concentrated on such configurations, and it is easily seen that the limit mass is uniformly distributed. That is, lim_{q↓0} ϕ_{p,q} is a probability measure which selects, uniformly at random, a spanning tree of G; in other words, the limit measure is ϕ_{\frac{1}{2} ,1} conditioned on the resulting graph being a spanning tree.

The link to the theory of electrical networks is now provided by Kirchhoff’s theorem [101], which expresses effective resistances in terms of counts of spanning trees. See also [78].

The theory of random spanning trees is beautiful in its own right (see [17]), and is linked in an important way to the emerging field of stochastic growth processes of ‘stochastic Löwner evolution’ (SLE) type (see [110, 129]), to which we return in Section 6.4. Another limit emerges if p = q and q ↓ 0, namely uniform measure on the set of forests of G. More generally, take p = αq where α ∈ (0, ∞) is constant, and take the limit as q ↓ 0. The limit measure is the percolation measure ϕ_{β,1} conditioned on the non-existence of open circuits, where β = α/(1 + α). If p/q → 0 as p, q → 0, the limit measure is concentrated on the empty set of edges.

2.5 Rank-generating functions The partition functions of Potts and random-cluster measures are particular evaluations of rank-generating functions, defined as follows. The rank-generating function of the simple graph G = (V, E) is the function

W_{G}(u, v) = ∑_{E′⊆E} u^{r(G′)}v^{c(G′)}, u, v ∈ ℝ,

where r(G′) = |V | − k(G′) is the rank of the graph G′ = (V, E′), and c(G′) = |E′| − |V | + k(G′) is its co-rank; here, k(G′) denotes the number of components of the graph G′. The rank-generating function has various useful properties, and occurs in several contexts in graph theory; see [21, 141]. It crops up in other forms also. For example, the function

T_{G}(u, v) = (u − 1)^{|V |−1}W_{G}((u − 1)^{−1}, v − 1)

is known as the dichromatic (or Tutte) polynomial, [141]. The partition function Z = Z_{G} of the random-cluster measure on G with parameters p, q is easily seen to satisfy

Z_{G} = q^{|V |}(1 − p)^{|E|}W_{G} (\frac{p}{q(1 − p)}, \frac{p}{1 − p}) ,

a relationship which provides a link with other classical quantities associated with a graph. See [21, 22, 53, 143] also.

3. Infinite-volume random-cluster measures

It is in the infinite-volume limit that random-cluster measures exhibit phase transitions. There are two ways of constructing random-cluster measures on infinite graphs, namely by taking weak limits as a finite domain approaches the infinite system, and by studying measures on the infinite graph having the ‘correct’ conditional versions. Such matters are discussed in this section, which begins with a summary of certain valuable properties of random-cluster measures on finite graphs.

3.1 Stochastic ordering

The stochastic ordering of measures provides a technique fundamental to the study of random-cluster measures. Let G = (V, E) be a finite or countably infinite graph as above; let Ω = {0, 1}^{E}, and let F be the σ-field of Ω generated by the finitedimensional cylinders. Note first that Ω is a partially ordered set with partial order ω_{1} ≤ ω_{2} if ω_{1}(e) ≤ ω_{2}(e) for all e. A random variable f : Ω → ℝ is called increasing if f(ω_{1}) ≤ f(ω_{2}) whenever ω_{1} ≤ ω_{2}. An event A ∈ F is called increasing if its indicator function 1_{A} is increasing. The word ‘decreasing’ should be interpreted in the natural way. Given two probability measures μ_{1}, μ_{2} on Ω, we write μ_{1} ≤_{st} μ_{2}, and say that μ_{1} is stochastically smaller than μ_{2}, if μ_{1}(f) ≤ μ_{2}(f) for all bounded increasing random variables f on Ω.

We return now to the case when G is a finite graph. Let μ_{1}, μ_{2} be probability measures on Ω, and assume for the moment that the μ_{i} are strictly positive in the sense that μ_{i}(ω) > 0 for all ω ∈ Ω. An important sufficient condition for the inequality μ_{1} ≤_{st} μ_{2} was found by Holley [87], namely that

μ_{1}(ω_{1} ∨ ω_{2})μ_{2}(ω_{1} ∧ ω_{2}) ≥ μ_{1}(ω_{1})μ_{2}(ω_{2}) for all ω_{1}, ω_{2} ∈ Ω,

where ω_{1} ∨ ω_{2} and ω_{1} ∧ ω_{2} are the maximum and minimum configurations given respectively as max{ω_{1}(e), ω_{2}(e)} and min{ω_{1}(e), ω_{2}(e)}, for e ∈ E. A probability measure μ on Ω is said to have the FKG lattice property if

μ(ω_{1} ∨ ω_{2})μ(ω_{1} ∧ ω_{2}) ≥ μ(ω_{1})μ(ω_{2}) for all ω_{1}, ω_{2} ∈ Ω,

amd it is a consequence of Holley’s argument that any strictly positive measure with the FKG lattice property satisfies the so-called FKG inequality. This amounts to the following for random-cluster measures.

Theorem 3.1 (FKG inequality) [54, 56]. Suppose that 0 ≤ p ≤ 1 and q ≥ 1. If f and g are increasing functions on Ω, then ϕ_{p,q}(fg) ≥ ϕ_{p,q}(f)ϕ_{p,q}(g).

Specialising to indicator functions, we obtain that

ϕ_{p,q}(A ∩ B) ≥ ϕ_{p,q}(A)ϕ_{p,q}(B) for increasing events A, B,

whenever q ≥ 1. It is not difficult to see that the FKG inequality does not generally hold when 0 < q < 1.

Holley’s theorem leads easily to the following comparison inequalities, which were first proved by Fortuin.

Theorem 3.2 (Comparison inequalities) [54]. It is the case that

ϕ_{p′,q′} ≤ ϕ_{p,q}  if q′ ≥ q, q′ ≥ 1, and p′ ≤ p,
ϕ_{p′,q′} ≥ ϕ_{p,q}  if q′ ≥ q, q′ ≥ 1, and \frac{p′}{q′(1 − p′)} ≥ \frac{p}{q(1 − p)}.

3.2 A differential formula

One way of estimating the probability of an event A is via an estimate of its derivative dϕ_{p,q}(A)/dp. When q = 1, there is a formula for this derivative which has proved very useful, and which is commonly attributed to Russo, see [14, 71, 130]. This formula may be generalised to random-cluster measures as follows. The proof is an exercise in the differentiation of summations.

Theorem 3.3 [20]. Let 0 < p < 1, q > 0, and let ϕ_{p,q} be the corresponding random-cluster measure on a finite graph G = (V, E). Then

\frac{d}{dp}ϕ_{p,q}(A) = \frac{1}{p(1 − p)}\{ϕ_{p,q}(|η|1_{A}) − ϕ_{p,q}(|η|)ϕ_{p,q}(A)\}

for any event A, where |η| = |η(ω)| = ∑_{e∈E} ω(e) is the number of open edges of the configuration ω.

3.3 Conditional probabilities

Whether or not an edge e is open depends on the configuration on E \ {e}, and a further important property of random-cluster measures summarises the nature of this dependence.

For e ∈ E, we denote by G \ e (respectively, G.e) the graph obtained from G by deleting (respectively, contracting) e. We write Ω_{e} = {0, 1}^{E\{e}}; for ω ∈ Ω we define ω_{e} ∈ Ω_{e} by ω_{e}(f) = ω(f) for f ≠ e. For e = ⟨x, y⟩, we write K_{e} for the event that x and y are joined by an open path not using e.

Theorem 3.4 [54]. Let e ∈ E. We have that

ϕ_{G,p,q}(ω | ω(e) = j) = \{ \begin{matrix}ϕ_{G\e,p,q}(ω_{e}) & if j = 0, \\ ϕ_{G.e,p,q}(ω_{e}) & if j = 1, \end{matrix}

and

ϕ_{G,p,q}(ω(e) = 1 | ω_{e}) = \{ \begin{matrix}p & if ω_{e} ∈ K_{e}, \\ \frac{p}{p + (1 − p)q} & if ω_{e} ∉ K_{e}. \end{matrix}

That is to say, the effect of conditioning on the absence or presence of an edge e is to replace the measure ϕ_{G,p,q} by the random-cluster measure on the respective graph G \ e or G.e. Secondly, the conditional probability that e is open, given the configuration elsewhere, depends only on whether or not K_{e} occurs, and is then given by the stated formula. The proof is elementary. The final equation of the theorem leads to properties of random-cluster measures referred to elsewhere as ‘insertion tolerance’ and the ‘finite-energy property’.

3.4 Infinite-volume weak limits

In studying random-cluster measures on infinite graphs, we restrict ourselves to the case of the hypercubic lattice in d dimensions, where d ≥ 2; similar observations are valid in greater generality. Let d ≥ 2, and let ℤ^{d} be the set of all d-vectors of integers; for x ∈ ℤ^{d}, we normally write x = (x_{1}, x_{2}, …, x_{d}). For x, y ∈ ℤ^{d}, let

∥x − y∥ = ∑_{i=1}^{d} |x_{i} − y_{i}|.

We place an edge ⟨x, y⟩ between x and y if and only if ∥x − y∥ = 1; the set of such edges is denoted by 𝔼^{d}, and we write 𝕃^{d} = (ℤ^{d}, 𝔼^{d}) for the ensuing lattice. For any subset S of ℤ^{d}, we write ∂S for its boundary, that is,

∂S = {s ∈ S : ⟨s, t⟩ ∈ 𝔼^{d} for some t ∉ S}.

Let Ω = {0, 1}^{𝔼^{d}}, and let F be the σ-field of subsets of Ω generated by the finitedimensional cylinders. The letter Λ is used to denote a finite box of ℤ^{d}, which is to say that Λ = ∏_{i=1}^{d}[x_{i}, y_{i}] for some x, y ∈ ℤ^{d}; we interpret [x_{i}, y_{i}] as the set {x_{i}, x_{i} + 1, x_{i} + 2, …, y_{i}}. The set Λ generates a subgraph of 𝕃^{d} having vertex set Λ and edge set 𝔼_{Λ} containing all ⟨x, y⟩ with x, y ∈ Λ.

We are interested in the ‘thermodynamic limit’ (as Λ ↑ ℤ^{d}) of the random-cluster measure on the finite box Λ. In order to describe such weak limits, we shall need to introduce the notion of a ‘boundary condition’.

For ξ ∈ Ω, we write Ω_{Λ}^{ξ} for the (finite) subset of Ω containing all configurations ω satisfying ω(e) = ξ(e) for e ∈ 𝔼^{d} \ 𝔼_{Λ}; these are the configurations which ‘agree with ξ off Λ’. For ξ ∈ Ω and values of p, q satisfying 0 ≤ p ≤ 1, q > 0, we define ϕ_{Λ,p,q}^{ξ} to be the random-cluster measure on the finite graph (Λ, 𝔼_{Λ}) ‘with boundary condition ξ’; this is the equivalent of a ‘specification’ for Gibbs states. More precisely, let ϕ_{Λ,p,q}^{ξ} be the probability measure on the pair (Ω, F) given by

ϕ_{Λ,p,q}^{ξ}(ω) = \{ \begin{matrix}\frac{1}{Z_{Λ,p,q}^{ξ}} \{ ∏_{e∈𝔼_{Λ}} p^{ω(e)}(1 − p)^{1−ω(e)}\}q^{k(ω,Λ)} & if ω ∈ Ω_{Λ}^{ξ}, \\ 0 & otherwise, \end{matrix}

where k(ω, Λ) is the number of components of the graph (ℤ^{d}, η(ω)) which intersect Λ, and where Z_{Λ,p,q}^{ξ} is the appropriate normalising constant

Z_{Λ,p,q}^{ξ} = ∑_{ω∈Ω_{Λ}^{ξ}} { ∏_{e∈𝔼_{Λ}} p^{ω(e)}(1 − p)^{1−ω(e)}}q^{k(ω,Λ)}.

Note that ϕ_{Λ,p,q}^{ξ}(Ω_{Λ}^{ξ}) = 1.

Definition 3.5. Let 0 ≤ p ≤ 1 and q > 0. A probability measure ϕ on (Ω, F) is called a limit random-cluster measure with parameters p and q if, for some ξ ∈ Ω, ϕ is a limit point of the family {ϕ_{Λ,p,q}^{ξ} : Λ ⊆ ℤ^{d}}, in the sense of the weak convergence of measures. The set of all such measures ϕ is denoted by W_{p,q}, and the closed convex hull of W_{p,q} is denoted \overline{co W_{p,q}}.

It might seem reasonable to define a limit random-cluster measure to be any limit point of the family of ϕ_{Λ,p,q}^{ξ} as Λ ranges over finite boxes and as ξ ranges over Ω. It may however be shown that this adds no extra generality to the class as defined above, [69]. Note that, for ϕ ∈ W_{p,q}, there exists ξ ∈ Ω and a sequence of boxes (Λ_{n} : n ≥ 1) such that ϕ_{Λ_{n},p,q}^{ξ} ⇒ ϕ as n → ∞. The dependence of the limit measure ϕ on the choice of sequence (Λ_{n}) can be subtle, especially when q < 1 (OP).

It is standard that W_{p,q} ≠ ∅ for all 0 ≤ p ≤ 1, q > 0, and one way of seeing this is as follows. The sample space Ω is the product of discrete spaces, and is therefore compact. It follows that any class of probability measures on Ω is tight, and hence relatively compact (see the account of Prohorov’s theorem in [23]), which is to say that any infinite sequence of probability measures contains a weakly convergent subsequence.

When does the limit lim_{n→∞} ϕ_{Λ_{n},p,q}^{ξ} exist, and when does it depend on the choice of boundary condition ξ? The FKG inequality provides a route to a partial answer to this important question. Suppose for the moment that q ≥ 1. Two extremal boundary conditions of special importance are provided by the configurations 0 and 1, comprising ‘all edges closed’ and ‘all edges open’ respectively. One speaks of configurations in Ω_{Λ}^{0} as having ‘free’ boundary conditions, and configurations in Ω_{Λ}^{1} as having ‘wired’ boundary conditions.

Theorem 3.6 (Thermodynamic limit) [4, 28, 54, 66, 69]. Suppose 0 ≤ p ≤ 1 and q ≥ 1.

(a) Let Λ = (Λ_{n} : n ≥ 1) be a sequence of boxes satisfying Λ_{n} → ℤ^{d} as n → ∞. The weak limits

ϕ_{p,q}^{b} = lim_{n→∞} ϕ_{Λ_{n},p,q}^{b}, for b = 0, 1,

exist and are independent of the choice of Λ.

(b) We have that each ϕ_{p,q}^{b} is translation-invariant, and

ϕ_{p,q}^{0} ≤_{st} ϕ ≤_{st} ϕ_{p,q}^{1} for all ϕ ∈ W_{p,q}.

(c) For b = 0, 1, the measure ϕ_{p,q}^{b} is ergodic, in that any translation-invariant random variable is ϕ_{p,q}^{b}-a.s. constant.

In writing Λ_{n} → ℤ^{d} we mean that, for all m, Λ_{n} ⊇ [−m, m]^{d} for all large n. The FKG inequality underlies all parts of Theorem 3.6. The claim (c) of ergodicity has until recently been considered slightly subtle (see the discussion after the forthcoming Theorem 3.9) but an easy proof may be found in [112].

It follows from the inequality of part (b) that |W_{p,q}| = 1 if and only if ϕ_{p,q}^{0} = ϕ_{p,q}^{1}. It is an important open problem to determine for which p, q this holds, and we shall return to this question in Section 5 (OP). For the moment, we note one sufficient condition for uniqueness, proved using a certain convexity property of the logarithm of a partition function Z.

Theorem 3.7 [67, 69]. Let q ≥ 1. There exists a subset D_{q} of [0, 1], at most countably infinite in size, such that ϕ_{p,q}^{0} = ϕ_{p,q}^{1}, and hence |W_{p,q}| = 1, if p ∉ D_{q}.

It is believed but not proved (OP) that: for any given q ≥ 1, D_{q} either is empty or consists of a singleton (the critical point, to be defined in Section 4), the former occurring if and only if q is sufficiently small.

3.5 Random-cluster measures on infinite graphs

One may define a class of measures on the infinite lattice without having recourse to weak limits. The following definition of a random-cluster measure is based upon the Dobrushin–Lanford–Ruelle (DLR) definition of a Gibbs state, [44, 59, 105]. It was introduced in [66, 67], and discussed further in [28, 69]. For any box Λ, we write T_{Λ} for the σ-field generated by the set {ω(e) : e ∈ 𝔼^{d} \ 𝔼_{Λ}} of states of edges having at least one endvertex outside Λ.

Definition 3.8. Let 0 ≤ p ≤ 1 and q > 0. A probability measure ϕ on (Ω, F) is called a random-cluster measure with parameters p and q if

ϕ(A | T_{Λ})(ξ) = ϕ_{Λ,p,q}^{ξ}(A) for ϕ-a.e. ξ, for all A ∈ F and finite boxes Λ.

The set of such measures is denoted R_{p,q}.

The condition of this definition amounts to the following. Suppose we are given that the configuration off the finite box Λ is that of ξ. Then, for almost every ξ ∈ Ω, the (conditional) measure on Λ is simply the random-cluster measure with boundary condition ξ. No further generality is gained by replacing the finite box Λ by a general finite subset of ℤ^{d}.

Some information about the structure of R_{p,q}, and its relationship to W_{p,q}, is provided in [69]. For example, for all p, q, R_{p,q} is non-empty and convex. We have no proof that W_{p,q} ⊆ R_{p,q}, but we state one theorem in this direction. For ω ∈ Ω, let I(ω) be the number of infinite open clusters of ω. We say that a probability measure ϕ on (Ω, F) has the 0/1-infinite-cluster property if ϕ(I ∈ {0, 1}) = 1.

Theorem 3.9 [69, 70, 73]. Let 0 ≤ p ≤ 1 and q > 0. If ϕ ∈ \overline{co W_{p,q}} and ϕ has the 0/1-infinite-cluster property, then ϕ ∈ R_{p,q}.

Since, [31], any translation-invariant probability measure satisfying a finiteenergy property (see the discussion after Theorem 3.4) necessarily has the 0/1infinite-cluster property, we have that all translation-invariant members of \overline{co W_{p,q}} lie in R_{p,q}. Suppose for the moment that q ≥ 1. By Theorem 3.6(b), the weak limits ϕ_{p,q}^{b}, b = 0, 1, are translation-invariant, and therefore they belong to R_{p,q}. It is not difficult to see, by the FKG inequality, that

(∗)  ϕ_{p,q}^{0} ≤_{st} ϕ ≤_{st} ϕ_{p,q}^{1}  for all ϕ ∈ R_{p,q},

and it follows that |R_{p,q}| = 1 if and only if ϕ_{p,q}^{0} = ϕ_{p,q}^{1}. The claim of ergodicity in Theorem 3.6(c) is one consequence of the extremality (∗) of the ϕ_{p,q}^{b} within the class R_{p,q} (see also [112, page 1113]).

It may be seen by an averaging argument, [69], that \overline{co W_{p,q}} necessarily contains at least one translation-invariant measure, for all p ∈ [0, 1] and q ∈ (0, ∞). Therefore, R_{p,q} is non-empty for all p and q.

We note that Theorem 3.9, and particularly the 0/1-infinite-cluster property, is linked to the property of so-called ‘almost sure quasilocality’, a matter discussed in [120].

3.6 The case q < 1

The FKG inequality, a keystone of many arguments when q ≥ 1, is not valid when q < 1. Consequently, many fundamental questions are unanswered to date, and the theory of random-cluster models on a finite graph G = (V, E) remains obscure when q < 1. The intuition is that certain positive correlations should be replaced by negative correlations; however, the theory of negative correlation is more problematic than that of positive correlation (see [119]). We return to this point later in this subsection.

As referred to above, there is an existence proof of infinite-volume weak limits and random-cluster measures for all q > 0. On the other hand, no constructive proof is known of the existence of such measures when q < 1 (OP). More specifically, the existence of the weak limits lim_{Λ↑ℤ^{d}} ϕ_{Λ,p,q}^{b}, b = 0, 1, is not known when q < 1. The best that can be shown currently is that the two limits exist and are equal when p is either sufficiently small or sufficiently large, [73]. This may be achieved by comparison with percolation models having different values of p, very much as in [69] (the claim for small p may also be shown by the arguments of [49, 50]).

The theory of percolation gives a clue to a possible way forward. When q = 1, the FKG inequality is complemented by the so-called ‘disjoint-occurrence’ (or ‘BK’) inequality. This latter inequality is said to be valid for a measure μ if μ(A ∘ B) ≤ μ(A)μ(B) for all increasing events A, B, where A ∘ B is the event that A and B occur disjointly (see [19, 71] for a discussion of this and the more general ‘Reimer inequality’ [128]). The disjoint-occurrence inequality has been established for classes of measures which are only slightly more general than product measures, and it is an interesting open question whether it is valid for a wider class of measures of importance (OP). It has been asked whether the disjoint-occurrence inequality could be valid for random-cluster measures with q < 1 (OP). A positive answer would aid progress substantially towards an understanding of limit random-cluster measures.

We illustrate this discussion about disjoint-occurrence with the following test question (OP): is it generally the case that the random-cluster measure ϕ_{p,q} on G satisfies

(∗)  ϕ_{p,q}(edges e and f are open) ≤ ϕ_{p,q}(e is open)ϕ_{p,q}(f is open)

for e ≠ f and q < 1? (See [119].) This equation would be a very special instance of the disjoint-occurrence inequality. A further restriction arises if we take the limit as q ↓ 0; recall the discussion of Section 2.4. This leads to certain open questions of a purely graph-theoretic type, which combinatorial theorists might elevate to the status of conjectures. The first such question is the following. Let K(e_{1}, e_{2}, …) be the number of subsets F of the edge set E, containing e_{1}, e_{2}, …, such that the graph (V, F) is connected. Is it the case that (OP)

(∗∗)  K(e, f)K(∅) ≤ K(e)K(f) if e ≠ f?

(See [92].) In the second such question, we ask if the same inequality is valid with K(e_{1}, e_{2}, …) redefined as the number of subsets F containing e_{1}, e_{2}, … such that (V, F) is a forest (OP). These two questions are dual to one another in the sense that the first holds for a planar graph G if and only if the second holds for its planar dual.

In the ‘intermediate regime’, with K(e_{1}, e_{2}, …) redefined as the number of spanning trees (that is, connected forests) of G containing e_{1}, e_{2}, …, the corresponding inequality is indeed valid. An extra ingredient in this case is the link to electrical networks, and particularly the variational principle known as the Thomson or Dirichlet principle (see [45]). Further results and references are provided in [17]. Substantially more is known for spanning trees, namely a general result concerning the ‘negative association’ of the uniform measure on the set of spanning trees of G, [48].

We note a more general version of conjecture (∗∗), namely

K_{α}(e, f)K_{α}(∅) ≤ K_{α}(e)K_{α}(f) for e ≠ f, 0 < α < ∞,

where

K_{α}(e_{1}, e_{2}, …) = ∑_{F ⊆E F ⊇{e_{1},e_{2},... } (V,F) connected} α^{|F |}.

This is equivalent to (∗) in the limit as q ↓ 0, where α = p/(1 − p).

By other means one may establish a certain non-trivial monotonicity when q < 1, but by a more complicated reasoning than before involving a property of convexity of the logarithm of the partition function. Namely, the mean number of open edges is non-decreasing in p, for 0 < q < ∞, [69].

4. Phase transition, the big picture

Phase transition in a Potts model corresponds to the creation of an infinite open cluster in the corresponding random-cluster model. There are rich predictions concerning the nature of such a phase transition, but these have been proved only in part. This section is a summary of the expected properties of the phase diagram for different dimensions d and cluster-weighting factors q. The corresponding rigorous theory is described in Sections 5 and 6.

4.1 Infinite open clusters

We assume henceforth that q ≥ 1, and we concentrate here on the extremal randomcluster measures ϕ_{p,q}^{0} and ϕ_{p,q}^{1}. The phase transition of a random-cluster measure is marked by the onset of an infinite open cluster. We write {0 ↔ ∞} for the event that the origin is the endvertex of some infinite open path, and we define the ϕ_{p,q}^{b} percolation probability by

θ^{b}(p, q) = ϕ_{p,q}^{b}(0 ↔ ∞), b = 0, 1.

It is almost immediate by a stochastic-ordering argument that θ^{b}(p, q) is nondecreasing in p, and therefore

θ^{b}(p, q)\{ \begin{matrix}= 0 & if p < p_{c}^{b}(q), \\ > 0 & if p > p_{c}^{b}(q), \end{matrix} b = 0, 1,

for critical points p_{c}^{b}(q) given by

p_{c}^{b}(q) = sup{p : θ^{b}(p, q) = 0}, b = 0, 1.

It is an easy exercise to show that the number I of infinite open clusters satisfies:

ϕ_{p,q}^{b}(I ≥ 1) = \{ \begin{matrix}0 & if θ^{b}(p, q) = 0, \\ 1 & if θ^{b}(p, q) > 0. \end{matrix}

We shall see in Section 5.2 that any infinite open cluster is ϕ_{p,q}^{b}-a.s. unique whenever it exists.

We have by Theorem 3.7 that ϕ_{p,q}^{0} = ϕ_{p,q}^{1} for almost every p, whence θ^{0}(p, q) = θ^{1}(p, q) for almost every p, and therefore p_{c}^{0}(q) = p_{c}^{1}(q). Henceforth we use the abbreviated notation p_{c}(q) = p_{c}^{0}(q) = p_{c}^{1}(q), and we refer to p_{c}(q) as the critical point of the corresponding random-cluster measures. The non-triviality of p_{c}(q) may be proved by comparisons of random-cluster measures with product measures via Theorem 3.2. Recall the fact, [71, Chapter 1], that 0 < p_{c}(1) < 1 if d ≥ 2.

Theorem 4.1 [4]. We have for q ≥ 1 that

p_{c}(1) ≤ p_{c}(q) ≤ \frac{qp_{c}(1)}{1 + (q − 1)p_{c}(1)}.

When q is an integer satisfying q ≥ 2, the phase transition of the random-cluster model corresponds in a special way to that of the Potts model with the same value of q. An indicator of phase transition in the Potts model is the ‘magnetisation’, defined as follows. Consider a Potts measure π_{Λ}^{1} on Λ having parameters β, J, q, and with ‘1’ boundary conditions, which is to say that all vertices on the boundary ∂Λ are constrained to have spin value 1. Let τ_{Λ} = π_{Λ}^{1}(σ_{0} = 1) − q^{−1}, a quantity which represents the net effect of this boundary condition on the spin at the origin. The corresponding random-cluster measure ϕ_{Λ}^{1} has parameters p = 1 − e^{−βJ} and q, and has wired boundary condition. We apply Theorem 2.1 to the graph obtained from Λ by identifying all vertices in ∂Λ, and we find that

τ_{Λ} = (1 − q^{−1})ϕ_{Λ}^{1}(0 ↔ ∂Λ).

The limit function τ = lim_{Λ↑ℤ^{d}} τ_{Λ} is called the magnetisation, it is a non-decreasing function of βJ and satisfies

τ \{ \begin{matrix}= 0 & if βJ is small, \\ > 0 & otherwise. \end{matrix}

It is not hard to show, [4], that ϕ_{Λ}^{1}(0 ↔ ∂Λ) → ϕ^{1}(0 ↔ ∞) as Λ ↑ ℤ^{d}, whence τ = (1−q^{−1})θ^{1}(p, q) where p = 1−e^{−βJ}. Therefore there is long-range order in the Potts model (that is, τ > 0) if and only if the origin lies in an infinite open cluster with strictly positive ϕ_{p,q}^{1}-probability. In particular, p_{c}(q) = 1 − e^{−β_{c}J} where β_{c} is the critical value of β for the Potts model in question.

4.2 First- and second-order phase transition

There is a rich physical theory of phase transitions in percolation, Ising, and Potts models, some of which has been made rigorous in the context of the random-cluster model. There follows a broad sketch of the big picture, a full rigorous verification of which is far from complete. Rigorous mathematical progress is described in Section 5.

I. The subcritical phase, p < p_{c}(q). It is standard, [4], that

ϕ_{p,q}^{0} = ϕ_{p,q}^{1} if θ^{1}(p, q) = 0,

implying that there exists a unique random-cluster measure whenever θ^{1}(p, q) = 0. In particular, |W_{p,q}| = |R_{p,q}| = 1 when 0 ≤ p < p_{c}(q). Assume for the moment that p < p_{c}(q), and denote the unique random-cluster measure by ϕ_{p,q}. By the definition of the critical point, all open clusters are ϕ_{p,q}-a.s. finite. It is believed that they have a tail which decays exponentially, in that there exist γ = γ(p, q) > 0 and η = η(p, q) > 0 such that

ϕ_{p,q}(|C| = n) = e^{−γn(1+o(1))}, ϕ_{p,q}(rad(C) = n) = e^{−ηn(1+o(1))}, as n → ∞,

where C denotes the open cluster containing the origin, and its radius rad(C) is defined as sup{∥x∥ : x ∈ C}. Such exponential decay would be the starting point for a complete exploration of the subcritical phase. More detailed asymptotics should then emerge, including the Ornstein–Zernike decay of the connectivity functions:

ϕ_{p,q}(0 ↔ e_{n}) ∼ \frac{c(p, q)}{n^{(d−1)/2}} e^{−n/ξ(p,q)} as n → ∞,

where e_{n} = (n, 0, 0, …, 0) and ξ(p, q) is termed the ‘correlation length’.

II. The supercritical phase, p > p_{c}(q). This phase is characterised by the existence of one or more infinite open clusters (exactly one, in fact, for translation-invariant measures at least, see Section 5.2). It is believed that, as in the subcritical phase, we have that ϕ_{p,q}^{0} = ϕ_{p,q}^{1} when p > p_{c}(q); this remains unproven in general. Thus the first main problem is to prove that there is a unique random-cluster measure when p > p_{c}(q).

The theory of percolation, [71], suggests a route towards understanding the geometry of the supercritical phase, namely by developing a rigorous block renormalisation argument. This should permit the use of theory developed when p is close to 1 in order to understand the model when p is close to p_{c}(q). In particular, one expects an exponential estimate for the decay of the probabilities of long-range connections within finite open clusters, and a Wulff construction for the shape of such clusters.

III. Near the critical point, p ≃ p_{c}(q). The main open problem is to understand the way in which the nature of the phase transition depends on the value of q. It is believed that the transition is continuous and governed by critical exponents and scaling theory when q is small, and is discontinuous when q is large. Presumably there exists a threshold for q which separates the so-called ‘second-order’ (or continuous) transition from the so-called ‘first-order’ (or discontinuous) transition. More specifically, it is believed that there exists Q = Q(d) satisfying

Q(d) = \{ \begin{matrix}4 & if d = 2, \\ 2 & if d ≥ 6, \end{matrix}

such that the following hold.

(i) Assume that q < Q.

– For any p, there exists a unique random-cluster measure, denoted ϕ_{p,q}. In particular ϕ_{p_{c}(q),q}^{0} = ϕ_{p_{c}(q),q}^{1}.

– θ(p, q) = ϕ_{p,q}(0 ↔ ∞) is a continuous function of p. There is no percolation at the critical point, in the sense that θ(p_{c}(q), q) = 0.

– The edge-density h(p, q) = ϕ_{p,q}(e is open), viewed as a function of p, is continuous at the critical point p = p_{c}(q). [The letter e denotes a typical edge of the lattice.]

– These functions and others have power-law singularities at p_{c}(q), and the associated critical exponents satisfy the scaling relations (see [71, Chapter 9]).

– When d is large (how large depends on the value of q), these critical exponents take on their ‘mean-field’ values, and depend no further on the value of d.

– There is no ‘mass gap’, in the sense that the correlation length ξ(p, q) satisfies lim_{p↑p_{c}(q)} ξ(p, q) = ∞.

– Universality reigns, in that the critical exponents depend on the number d of dimensions but not on the choice of lattice. For example, the exponents associated with the square lattice are expected to be the same as those for the triangular lattice.

– Assume d = 2 and 1 ≤ q < 4. The process with p = p_{c}(q) converges as the lattice spacing shrinks to zero, the limit process when suitably defined being a stochastic Löwner evolution SLE_{κ} having parameter κ satisfying cos(4π/κ) = −\frac{1}{2} \sqrt{q}, κ ∈ (4, 8) (see Section 6.4 and [129]).

(ii) Assume that q > Q.

– There exists a unique random-cluster measure if and only if p ≠ p_{c}(q). When d = 2 and p = p_{c}(q), there are exactly two extremal members of R_{p,q}, namely the free and the wired measures ϕ_{p,q}^{b}, b = 0, 1. When d ≥ 3 and p = p_{c}(q) there exist other extremal members of R_{p,q} including a variety of non-translation-invariant measures.

– We have that θ^{0}(p_{c}(q), q) = 0 but θ^{1}(p_{c}(q), q) > 0.

– The edge-density h(p, q) is a discontinuous function of p at the critical point p_{c}(q).

– There is a ‘mass gap’ in the sense that the correlation length ξ(p, q) satisfies lim_{p↑p_{c}(q)} ξ(p, q) < ∞.

5. General results in d (≥ 2) dimensions

The properties of the random-cluster model depend pivotally on whether the process is subcritical (p < p_{c}(q)), supercritical (p > p_{c}(q)), or critical (p ≃ p_{c}(q)). We consider these situations in turn, in each case identifying major results and open problems. There is a bulk of information available for certain values of q, namely when q = 1, 2 and q is sufficiently large. In addition, the case d = 2 is special, and we shall return to this in Section 6. We assume throughout this section that q ≥ 1.

Little is known in general about the numerical values of p_{c}(q). For example, it is known that p_{c}(q) is Lipschitz-continuous and strictly increasing when d ≥ 2, [68], and there is a striking conjecture (OP) that p_{c}(q) = \sqrt{q}/(1 + \sqrt{q}) when d = 2 (see Section 6.2). Some concrete inequalities involving the p_{c}(q) are implied by the comparison inequalities of Theorem 3.2.

5.1 The subcritical phase, p < p_{c}(q)

As remarked in Section 4.2, there is a unique random-cluster measure when p < p_{c}(q), and we shall denote this by ϕ_{p,q}.

The key theorem for understanding the subcritical phase of percolation states that long-range connections have exponentially decaying probabilities. Such a result is believed to hold for all random-cluster models with q ≥ 1, but no proof has been found (OP) which is valid for all q ≥ 1 and all p < p_{c}(q). The full result is known only when q = 1, q = 2, or q is sufficiently large, and the three sets of arguments for these cases are somewhat different from one another. As for results valid for all q (≥ 1), the best that is currently known is that the connectivity function decays exponentially for sufficiently small p (this follows by Theorem 3.2 and the corresponding q = 1 result), and that it decays exponentially whenever it decays at a sufficient polynomial rate. We describe the last result next.

As a preliminary we introduce another definition of a critical point. Let B(n) be the cube [−n, n]^{d}. We write

Y (p, q) = lim sup_{n→∞}{n^{d−1}ϕ_{p,q}(0 ↔ ∂B(n))}

and p_{g}(q) = sup{p : Y (p, q) < ∞}. Evidently 0 < p_{g}(q) ≤ p_{c}(q), and it is believed that p_{g}(q) = p_{c}(q) for all q ≥ 1 (OP).

Theorem 5.1 [76]. Let q ≥ 1, d ≥ 2, and 0 ≤ p < p_{g}(q). There exists γ = γ(p, q) satisfying γ > 0 such that

ϕ_{p,q}(0 ↔ ∂B(n)) ≤ e^{−γn} for all large n.

The spirit of the theorem is close to that of Hammersley [83] and Simon–Lieb [111, 135] who proved exponential estimates when q = 1, 2 subject to a hypothesis of finite susceptibility (that is, under the hypothesis that ∑_{x} ϕ_{p,q}(0 ↔ x) < ∞). The latter assumption is slightly stronger than the assumption of the above theorem when d = 2.

Connectivity functions are expected to decay exponentially with a correction term of power order. More specifically, it is expected as reported in Section 4.2 that

ϕ_{p,q}(0 ↔ x) ∼ \frac{c}{|x|^{(d−1)/2}} exp(−|x|/ξ) as |x| → ∞,

for constants c(p, q) and ξ(p, q), and for some suitable norm | · | on ℤ^{d}. Such ‘Ornstein–Zernike’ decay is a characteristic of many systems in their disordered phases. No proof is known (OP), except in the special cases when q = 1 and q = 2, [32, 33]. In [9] may be found a weaker result which bounds the fluctuations by a power-law when d = 2, under the assumption that the function does indeed decay exponentially.

5.2 The supercritical phase, p > p_{c}(q)

We assume as usual that q ≥ 1, and we begin with a discussion concerning the number of infinite open clusters.

Suppose ϕ_{p,q} is a translation-invariant member of R_{p,q}. A well known theorem of Burton and Keane [31] implies that there exists ϕ_{p,q}-a.s. a unique infinite open cluster. It is rather harder to prove so-called ‘simultaneous uniqueness’. One needs first a suitable coupling of random-cluster measures. It was shown in [69] that there exists a Markov process ζ = (ζ_{t} : t ≥ 0) on the state space [0, 1]^{𝔼^{d}} with the following properties. For 0 ≤ p ≤ 1 and σ ∈ [0, 1]^{𝔼^{d}}, we define

σ^{p,−}(e) = 1_{{ζ_{t}(e)>1−p}}, σ^{p,+}(e) = 1_{{ζ_{t}(e)≥1−p}}, e ∈ 𝔼^{d},

where 1_{A} denotes the indicator function of an event A. Then ζ_{t}^{p,−} and ζ_{t}^{p,+} are Markov processes which are reversible with respect to the infinite-volume free and wired random-cluster measures, ϕ_{p,q}^{0} and ϕ_{p,q}^{1}, respectively. The process ζ_{t} has a unique invariant measure μ, and the question of simultaneous uniqueness amounts in this context to asking whether or not

μ(for all p > p_{c}(q), σ^{p,−} and σ^{p,+} have unique infinite open clusters) = 1,

where σ is to be regarded as an element chosen according to μ. The main theorem of [6] may be applied in this context to deduce that this is indeed true. A little extra work is necessary to verify the finite-energy condition of [6], and this has been done by [12, 73].

In two dimensions, the supercritical process is best studied via the subcritical process which arises as its graphical dual (see Section 6). There are two general approaches to the supercritical phase in a general number d (≥ 3) of dimensions. The less powerful is to derive results for large p by comparison with percolation, the theory of which is relatively complete. Without an extra ingredient, such an approach will not reveal the structure of the supercritical phase all the way down to the critical value p_{c}(q). As an example, we present one theorem concerning the uniqueness of random-cluster measures.

Theorem 5.2 [69]. If d ≥ 2 and q ≥ 1, there exists p′ = p′(d, q) < 1 such that ϕ_{p,q}^{0} = ϕ_{p,q}^{1} whenever p > p′.

It is an important open problem to prove that ϕ_{p,q}^{0} = ϕ_{p,q}^{1} for all p > p_{c}(q), or equivalently that there exists a unique random-cluster measure throughout the phase (OP).

A more powerful approach, sometimes used in conjunction with the comparison argument summarised above, is the ‘block argument’ laid out in [36, 124]. One may think of block arguments as a form of rigorous renormalisation. One divides space into blocks, constructs events of an appropriate nature on such blocks, having large probabilities, and then allows these events to combine across space. There have been substantial successes using this technique, of which the most striking is the resolution, subject to certain side conditions, of the so-called Wulff construction for the asymptotic shape of large Ising droplets.

Rather than discussing the physical background of the Wulff construction, we mention instead its impact on random-cluster models. Let B(n) = [−n, n]^{d}, and consider the wired random-cluster measure ϕ_{B(n),p,q}^{1} with p > p_{c}(q). The larger is an open cluster, the more likely it is to be joined to the boundary ∂B(n). Suppose that we condition on the event that there exists in B(n) an open cluster C which does not touch ∂B(n) and which has volume of the order of the volume n^{d} of the box. What can be said about the shape of C? Since p > p_{c}(q), there is little cost in having large volume, and the price is spent around its boundary. Indeed, the price may be expressed as a surface integral of an appropriate function termed ‘surface tension’. This ‘surface tension’ may be specified as the exponential rate of decay of a certain probability. The Wulff prediction for the shape of C is that, when re-scaled in the limit of large n, its shape converges to the solution of a certain variational problem, that is, the limit shape is obtained by minimising a certain surface integral subject to a condition on its volume.

No proof of this general picture for random-cluster models has appeared in the literature, although it is believed that the methods of [36, 37, 124] enable such a proof. The authors of [36] have instead concentrated on using random-cluster technology to solve the corresponding question for the asymptotic shape of large droplets in the Ising model. The outcome is an important ‘large deviation’ theorem which utilises block arguments and yields a full solution to the Ising problem whenever the corresponding random-cluster model (which has q = 2) has parameter p satisfying p > p̂_{c}(2) and ϕ_{p,2}^{0} = ϕ_{p,2}^{1}. Here, p̂_{c}(2) is the limit of a certain decreasing sequence of critical points defined on slabs in ℤ^{d}, and is conjectured (OP) to be equal to the critical point p_{c}(2). [Closely related results have been obtained in [25]. Fluctuations in droplet shape for two-dimensional random-cluster models have been studied in [10, 11].]

The ‘slab critical point’ p̂_{c}(q) may be defined for any random-cluster model as follows. Fix q ≥ 1, and let d ≥ 3. Let S(n, L) = [−n, n]^{d−1} × [−L, L]. Let ψ_{p,q}^{n,L} be the random-cluster measure on S(n, L) with parameters p, q (and with free boundary conditions). We denote by Π(p, L) the property that:

there exists α > 0 such that, for all x ∈ S(n, L) and all n, ψ_{p,q}^{n,L}(0 ↔ x) > α.

It is not hard to see that Π(p, L) ⇒ Π(p′, L′) if p ≤ p′ and L ≤ L′. It is thus natural to define the quantities

p̂_{c}(q, L) = inf{p : Π(p, L) occurs},  p̂_{c}(q) = lim_{L→∞} p̂_{c}(q, L),

and it is clear that p̂_{c}(q) ≥ p_{c}(q).

Conjecture 5.3 [124]. Let q ≥ 1 and d ≥ 3. We have that p̂_{c}(q) = p_{c}(q).

Subject to a verification of this conjecture, and of a positive answer to the question of the uniqueness of random-cluster measures when p > p_{c}(q), the block arguments of [36, 124] may be expected to result in a fairly complete picture of the supercritical phase of random-cluster models with q ≥ 1; see [37] also.

The case q = 1 is special, percolation enjoys a spatial independence not shared with general random-cluster models. This additional property has been used in the formulation of a type of ‘dynamic renormalisation’, which has in turn yielded a proof that p̂_{c}(1) = p_{c}(1) for percolation in three or more dimensions, [71, Chapter 7, 74]. Such arguments do not to date have a random-cluster counterpart.

As a further application of a block argument we note the following bound, [124], for the tail of the size of the open cluster C at the origin,

ϕ_{p,q}^{b}(|C| = n) ≤ exp(−αn^{(d−1)/d}) for all n,

for some α = α(p, q) > 0, and valid for d ≥ 3, b = 0, 1, and p sufficiently close to 1. The complementary inequality

ϕ_{p,q}^{b}(|C| = n) ≥ exp(−α′n^{(d−1)/d}) for all n,

may be obtained for large p as done in the case of percolation, [71, Section 8.6].

5.3 Near the critical point, p ≃ p_{c}(q)

Surprisingly little is known about random-cluster measures near the critical point, except in the cases q = 1, 2 and q large. In each such case, there are special arguments which are apparently not suitable for generalisation. We summarise such results as follows.

I. Percolation, q = 1. There is a full theory of the subcritical and supercritical phases of percolation, [71]. The behaviour when p ≃ p_{c}(1) has been the subject of deep study, and many beautiful results are known. Nevertheless, the picture is incomplete. For example, it is believed but not proved that θ(p_{c}(1), 1) = 0 for all d ≥ 2, but this is known only when d = 2 (because of special properties of two dimensions explored for 𝕃^{2} in Section 6) and when d is large (d ≥ 19 suffices) using a method termed the ‘lace expansion’. The lace expansion explains also the values of some critical exponents when d is large; see, for example, [84, 85].

Great progress has been made in recent years towards understanding the phase transition when d = 2. The idea is to work at the critical point p = p_{c}(1), and to observe the process over an increasing sequence of regions of ℤ^{2}. It is believed that the process, re-scaled as the regions become larger, converges in a certain manner to a stochastic process generated in a prescribed way by a differential equation, known as a Löwner equation, which is driven in a certain way by a Brownian motion. Stochastic processes which arise in this way have been termed stochastic Löwner evolutions by Schramm, [134], and denoted SLE_{κ}, where κ is the variance parameter of the Brownian motion. It is believed that the space of stochastic Löwner evolutions is a canonical family of processes which arise as scaling limits of discrete processes such as critical percolation, critical random-cluster models with q ≤ 4, self-avoiding walks, loop-erased random walk, and uniform spanning trees. Full proofs are not yet known (OP). We expand on this very important development in Section 6.4

II. Ising model, q = 2. Integer values of q are special, and the value q = 2 particularly so because of certain transformations which permit the passage to a model which might be termed a ‘Poisson graph’. Let G = (V, E) be a finite graph and let 0 < λ < ∞. Suppose that π = {π(e) : e ∈ E} is a family of independent random variables each having the Poisson distribution with parameter λ. We now construct a random graph G_{π} = (V, E_{π}) having vertex set V and, for each e ∈ E, having exactly π(e) edges in parallel joining the endvertices of the edge e [the original edge e is itself removed]. We call G_{π} a Poisson graph with intensity λ, and write ℙ_{λ} and 𝔼_{λ} for the appropriate probability measure and expectation operator.

Let q ∈ {2, 3, … } and let G′ = (V′, E′) be a finite graph. A mod-q flow f on G′ is a function f : E′ → {0, 1, 2, …, q − 1} such that

∑_{e′∋x} f(e′) = 0 mod q, for all x ∈ V′,

where the summation extends over all edges e′ incident to x. The mod-q flow f is called non-zero if f(e′) ≠ 0 for every e′ ∈ E′. We write F_{q}(G′) for the number of non-zero mod-q flows on G′.

We return now to the Poisson graph G_{π}. For x, y ∈ V, x ≠ y, we denote by G_{π}^{x,y} the graph obtained from G_{π} by adding an edge with endvertices x, y. [If x and y are already adjacent in G_{π}, we add exactly one further edge between them.] Connection probabilities and flows are related by the following theorem, which may be proved using properties of Tutte polynomials (see [141] and Section 2.5).

Let G = (V, E) be a finite graph, and write ϕ_{G,p,q} for the random-cluster measure on G with parameters p, q.

Theorem 5.4 [63]. Let 0 ≤ p < 1 and q ∈ {2, 3, … }. With p = 1 − e^{−λq}, we have that

(q − 1)ϕ_{G,p,q}(x ↔ y) = \frac{𝔼_{λ}(F_{q}(G_{π}^{x,y}))}{𝔼_{λ}(F_{q}(G_{π}))} for all x, y ∈ V, x ≠ y.

This formula takes on an especially simple form when q = 2, since non-zero mod-2 flows necessarily take only the value 1. It follows that, for any graph G′, 𝔼_{λ}(F_{2}(G′)) equals the ℙ_{λ}-probability that the degree of every vertex of G′ is even, [1]. Observations of this sort have led when q = 2 to the so-called ‘random-current’ expansion for Ising models, thereby after some work [1, 2, 5] leading to proofs amongst other things of the following, expressed here in the language of randomcluster measures.

(i) When q = 2 and p < p_{c}(q), we have exponential decay of the radius distribu-

tion,

ϕ_{p,2}(rad(C) = n) ≤ e^{−ηn} for all n,

where η = η(p) > 0; exponential decay of the two-point connectivity function follows.

(ii) When q = 2 and d ≠ 3, there is a unique random-cluster measure ϕ_{p,2} for all

p, in that |R_{p,q}| = 1. (iii) The phase transition is continuous when q = 2 and d ≠ 3. In particular,

θ^{0}(p_{c}(2), 2) = θ^{1}(p_{c}(2), 2) = 0, and the edge-density h(p, 2) = ϕ_{p,2}(e is open) is a continuous function of p at the critical point p_{c}(2).

(iv) When d ≥ 4, some (at least) critical exponents take their mean-field values,

and depend no further on the value of d. Note that the nature of the phase transition in three dimensions remains curi-

ously undecided (OP).

III. The case of large q. It is not known whether the phase transition is continuous for all small q (OP). The situation for large q is much better understood owing to a method known as Pirogov–Sinai theory [122, 123] which may be adapted in a convenient manner to random-cluster measures. The required computation, which may be found in [104], has its roots in an earlier paper [102] dealing with Potts models. A feature of such arguments is that they are valid ‘all the way to the critical point’ (rather than for ‘small p’ or ‘large p’ only), so long as q is sufficiently large. One obtains thereby a variety of conclusions including the following.

(i) The edge-densities h^{b}(p, q) = ϕ_{p,q}^{b}(e is open), b = 0, 1, are discontinuous functions of p at the critical point.

(ii) The percolation probabilities satisfy θ^{0}(p_{c}(q), q) = 0, θ^{1}(p_{c}(q), q) > 0. (iii) There is a multiplicity of random-cluster measures when p = p_{c}(q), in that

ϕ_{p_{c}(q),q}^{0} ≠ ϕ_{p_{c}(q),q}^{1}.

(iv) If p < p_{c}(q), there is exponential decay and a mass gap, in that the unique random-cluster measure satisfies

ϕ_{p,q}(0 ↔ e_{n}) = e^{−(1+o(1))n/ξ} as n → ∞,

where e_{n} = (n, 0, 0, …, 0) and the correlation length ξ = ξ(p, q) is such that lim_{p↑p_{c}(q)} ξ(p, q) = ψ(q) < ∞.

(v) If d = 3 and p = p_{c}(q), there exists a non-translation-invariant random-cluster measure, [38, 115].

It is not especially fruitful to seek numerical estimates on the required size Q(d) of q for the above conclusions to be valid. Such estimates may be computed, but turn out to be fairly distant from those anticipated, namely Q(2) = 4, Q(d) = 2 for d ≥ 6.

The proofs of the above facts are rather complicated and will not be explained here. Proofs are much easier and not entirely dissimilar when d = 2, and a very short sketch of such a proof is provided in Section 6.3.

6. In two dimensions

The duality theory of planar graphs provides a technique for studying randomcluster models in two dimensions. We shall see in Section 6.1 that, for a dual pair (G, G^{d}) of planar graphs, the measures ϕ_{G,p,q} and ϕ_{G^{d},p^{d},q} are dual measures in a certain geometrical sense, where p, p^{d} are related by p^{d}/(1 − p^{d}) = q(1 − p)/p. Such a duality permits an analysis by which many results for 𝕃^{2} may be derived. Of particular interest is the value of p for which p = p^{d}. This ‘self-dual point’ is easily found to be p = p_{sd}(q) where

p_{sd}(q) = \frac{\sqrt{q}}{1 + \sqrt{q}} ,

and it is conjectured that p_{c}(q) = p_{sd}(q) for q ≥ 1.

6.1 Graphical duality

Let G = (V, E) be a simple planar graph imbedded in ℝ^{2}. We obtain its dual graph G^{d} = (V^{d}, E^{d}) as follows (the roman letter ‘d’ denotes ‘dual’ rather than number of dimensions). We place a dual vertex within each face of G, including the infinite face of G if G is finite. For each e ∈ E we place a dual edge e^{d} = ⟨x^{d}, y^{d}⟩ joining the two dual vertices lying in the two faces of G abutting e; if these two faces are the same, then x^{d} = y^{d} and e^{d} is a loop. Thus E^{d} is in one–one correspondence to E. It is easy to see that the dual of 𝕃^{2} is isomorphic to 𝕃^{2}. What is the relevance of graphical duality to random-cluster measures on G?

Suppose that G is finite. Any configuration ω ∈ Ω (= {0, 1}^{E}) gives rise to a dual configuration ω^{d} lying in the space Ω^{d} = {0, 1}^{E^{d}} defined by ω^{d}(e^{d}) = 1 − ω(e). As before, to each configuration ω^{d} corresponds the set η(ω^{d}) = {e^{d} ∈ E^{d} : ω^{d}(e^{d}) = 1} of its ‘open edges’. Let f(ω) be the number of faces of the graph (V, η(ω)), including the infinite face By drawing a picture, one may easily be convinced (see Figure 6.1) that the faces of (V, η(ω)) are in one–one correspondence with the components of (V^{d}, η(ω^{d})), and therefore f(ω) = k(ω^{d}), in the obvious notation. We shall make use of Euler’s formula (see [145]),

k(ω) = |V | − |η(ω)| + f(ω) − 1, ω ∈ Ω.

Figure 6.1. A primal configuration ω (with solid lines and vertices) and its dual configuration ω^{d} (with dashed lines and hollow vertices). The arrows join the given vertices of the dual to a dual vertex in the infinite face. Note that each face of the primal graph (including the ‘infinite face’) corresponds to a unique component of the dual graph.

The random-cluster measure on G is given by

ϕ_{G,p,q}(ω) ∝ (\frac{p}{1 − p})^{|η(ω)|} q^{k(ω)}, ω ∈ Ω.

Using Euler’s formula and the equality f(ω) = k(ω^{d}), we find that

ϕ_{G,p,q}(ω) = ϕ_{G^{d},p^{d},q}(ω^{d}) for ω ∈ Ω,

where the dual parameter p^{d} is given according to

\frac{p^{d}}{1 − p^{d}} = \frac{q(1 − p)}{p}.

The unique fixed point of the mapping p ↦ p^{d} is given by p = p_{sd}(q) where p_{sd}(q) = \sqrt{q}/(1 + \sqrt{q}). We note at this point that

ϕ_{G,p_{sd}(q),q}(ω) ∝ q^{\frac{1}{2} |η(ω)|+k(ω)} ∝ q^{\frac{1}{2} (k(ω^{d})+k(ω))},

by Euler’s formula. This representation of the random-cluster measure at the ‘selfdual point’ p_{sd}(q) highlights the duality of measures.

Turning to the square lattice, let Λ_{n} = [0, n]^{2}, whose dual graph Λ_{n}^{d} may be obtained from [−1, n]^{2} + (\frac{1}{2}, \frac{1}{2}) by identifying all boundary vertices. By the above,

ϕ_{Λ_{n},p,q}^{0}(ω) = ϕ_{Λ_{n}^{d},p^{d},q}^{1}(ω^{d})

for configurations ω on Λ_{n} (and with a small ‘fix’ on the boundary of Λ_{n}^{d}). Letting n → ∞, we obtain that ϕ_{p,q}^{0}(A) = ϕ_{p^{d},q}^{1}(A^{d}) for all cylinder events A, where A^{d} = {ω^{d} : ω ∈ A}.

6.2 Value of the critical point

Consider the random-cluster process on the two-dimensional lattice 𝕃^{2} = (ℤ^{2}, 𝔼^{2}), with parameters p and q satisfying q ≥ 1. The following remarkable conjecture is widely believed (OP).

Conjecture 6.1. Let q ≥ 1. The critical value p_{c}(q) of 𝕃^{2} is given by

p_{c}(q) = \frac{\sqrt{q}}{1 + \sqrt{q}} for q ≥ 1.

This conjecture is known to hold when q = 1, q = 2, and for q ≥ 25.72. The q = 1 case was answered by Kesten [96] in his famous proof that the critical probability of bond percolation on 𝕃^{2} is \frac{1}{2}. For q = 2, the value of p_{c}(2) given above agrees with the celebrated calculation by Onsager [118] of the critical temperature of the Ising model on ℤ^{2}, and is implied by probabilistic results in the modern vernacular of [2]. The formula for p_{c}(q) has been established rigorously in [103, 104] for sufficiently large (real) values of q, specifically q ≥ 25.72 (see also [70]).

Conjecture 6.1 arises in a natural manner from the observation that 𝕃^{2} is a selfdual graph, and p = p_{sd}(q) = \sqrt{q}/(1+\sqrt{q}) is the self-dual point of a random-cluster measure on 𝕃^{2} with parameters p, q.

Several other remarkable conjectures about the phase transition in 𝕃^{2} may be found in the physics literature (see [15]), as consequences of ‘exact’ but non-rigorous arguments involving ice-type models. These include exact formulae for the asymptotic behaviour of the partition function lim_{Λ↑ℤ^{2}}{Z_{Λ,p,q}}^{1/|Λ|}, and also for the edge-densities h^{b}(p_{sd}(q), q) = ϕ_{p_{sd}(q),q}^{b}(e is open), b = 0, 1, at the self-dual point p_{sd}(q).

Progress towards a rigorous verification of the conjecture may be summarised briefly as follows. Using an argument, [150], taken from percolation using the uniqueness of infinite open clusters, we obtain by duality that θ^{0}(p_{sd}(q), q) = 0 (see [69, 142]), whence the critical value of the square lattice satisfies p_{c}(q) ≥ p_{sd}(q) for q ≥ 1. The complementary inequality p_{c}(q) ≤ p_{sd}(q) has eluded mathematicians despite progress by physicists, [86].

Suppose on the contrary that p_{c}(q) > p_{sd}(q), so that p_{c}(q)^{d} < p_{sd}(q). For p ∈ (p_{c}(q)^{d}, p_{c}(q)) we have also that p^{d} ∈ (p_{c}(q)^{d}, p_{c}(q)). Therefore, for p ∈ (p_{c}(q)^{d}, p_{c}(q)), both primal and dual processes comprise, almost surely, the union of finite open clusters. This contradicts the intuitive picture, supported for p ≠ p_{c}(q) by our knowledge of percolation, of finite clusters of one process floating in an infinite ocean of the other process.

Exact values for the critical points of the triangular and hexagonal lattices may be conjectured similarly, using graphical duality together with the star–triangle transformation, [15, 100].

Rigorous numerical upper bounds of impressive accuracy have been achieved for the square lattice and other two-dimensional lattices via an extension of the basic model to a larger class termed in [8] the ‘asymmetric random-cluster model’. The bound in question for 𝕃^{2} is

p_{c}(q) ≤ \frac{\sqrt{q}}{\sqrt{1 − q^{−1}} + \sqrt{q}} , q ≥ 1.

For example, when q = 10, we have that 0.760 ≤ p_{c}(10) ≤ 0.769, to be compared with the conjecture that p_{c}(10) = \sqrt{10}/(1 + \sqrt{10}) ≃ 0.760. A valuable consequence of the comparison methods developed in [8] is the exponential decay of connectivity functions when q > 2 and p is such that

p < p_{sd}(q − 1) = \frac{\sqrt{q − 1}}{1 + \sqrt{q − 1}}.

6.3 First-order phase transition

There is a special argument discovered first for Potts models, [103], which may be used to show first-order phase transition when q is sufficiently large.

Let a_{n} be the number of self-avoiding walks on 𝕃^{2} beginning at the origin. It is standard, [113], that a_{n}^{1/n} → μ as n → ∞, for some constant μ called the connective constant of the lattice. Let Q = \{\frac{1}{2}(μ + \sqrt{μ^{2} − 4})\}^{4}. We have that 2.620 < μ < 2.696 (see [136]), whence 21.61 < Q < 25.72. We set

ψ(q) = \frac{1}{24} log \{\frac{(1 + \sqrt{q})^{4}}{qμ^{4}} \} ,

noting that ψ(q) > 0 if and only if q > Q. We write B(n) = [−n, n]^{2}.

Theorem 6.2 [70, 103]. If d = 2 and q > Q then the following hold.

(a) The critical point is given by p_{c}(q) = \sqrt{q}/(1 + \sqrt{q}).

(b) We have that θ^{1}(p_{c}(q), q) > 0.

(c) For any ψ < ψ(q) and all large n, ϕ_{p_{c}(q),q}^{0}(0 ↔ ∂B(n)) ≤ e^{−nψ}. Hence, in particular, θ^{0}(p_{c}(q), q) = 0.

The idea of the proof is as follows. There is a partial order on circuits of 𝕃^{2} given by Γ ≤ Γ′ if the bounded component of ℝ^{2} \ Γ is a subset of the bounded component of ℝ^{2} \ Γ′. We work at the self-dual point p = p_{sd}(q), and with the box B(n) with wired boundary conditions. An ‘outer contour’ is defined to be a circuit Γ of the dual graph B(n)^{d} all of whose edges are open in the dual (that is, they traverse closed edges in the primal graph B(n)), and which is maximal with this property. Using self-duality, one may show that

ϕ_{B(n),p_{sd}(q),q}^{1}(Γ is an outer circuit) ≤ \frac{1}{q} (\frac{q}{(1 + \sqrt{q})^{4}} )^{|Γ|/4} ,

for any given circuit Γ of B(n)^{d}. Combined with a circuit-counting argument of Peierls-type involving the connective constant, this estimate implies after a little work the claims of Theorem 6.2. The idea of the proof appeared in [103] in the context of Potts models, and the random-cluster formulation may be found in [70].

We stress that corresponding conclusions may be obtained for general d (≥ 2) when q is sufficiently large (q > Q(d) for suitable Q(d)), as shown in [104] using so-called Pirogov–Sinai theory. Whereas, in the case d = 2, the above duality provides an especially simple proof, the proof for general d utilises nested sequences of surfaces of ℝ^{d} and requires a control of the effective boundary conditions within the surfaces.

6.4 SLE limit when q ≤ 4

Many exact calculations are ‘known’ for critical processes in two dimensions, but the physical arguments involved have sometimes appeared in varying degrees magical or revelationary to mathematicians. The new technology of stochastic Löwner evolutions (SLE), discovered by Schramm [134] and mentioned in Section 5.3, threatens to provide a rigorous underpinning of many such arguments in a manner most consonant with modern probability theory. Roughly speaking, the theory of SLE informs us of the correct weak limit of a critical process in the limit of large spatial scales, and in addition provides a mechanism for performing calculations for the limit process.

Let ℍ = (−∞, ∞) × (0, ∞) be the upper half-plane of ℝ^{2}, with closure \overline{ℍ}. We view ℍ and \overline{ℍ} as subsets of the complex plane. Consider the ordinary differential equation

\frac{d}{dt}g_{t}(z) = \frac{2}{g_{t}(z) − B_{κt}} , z ∈ \overline{ℍ} \ \{0\},

subject to the boundary condition g_{0}(z) = z, where t ∈ [0, ∞), κ is a positive constant, and (B_{t} : t ≥ 0) is a standard Brownian motion. The solution exists when g_{t}(z) is bounded away from B_{κt}. More specifically, for z ∈ \overline{ℍ}, let τ_{z} be the infimum of all times τ such that 0 is a limit point of g_{s}(z) − B_{κs} in the limit as s ↑ τ. We let

H_{t} = \{z ∈ ℍ : τ_{z} > t\}, K_{t} = \{z ∈ \overline{ℍ} : τ_{z} ≤ t\},

so that H_{t} is open, and K_{t} is compact. It may now be seen that g_{t} is a conformal homeomorphism from H_{t} to ℍ.

We call (g_{t} : t ≥ 0) a stochastic Löwner evolution (SLE) with parameter κ, written SLE_{κ}, and we call the K_{t} the hulls of the process. There is good reason to believe that the family K = (K_{t} : t ≥ 0) provides the correct scaling limit of a variety of random spatial processes, the value of κ being chosen according to the process in question. General properties of SLE_{κ}, viewed as a function of κ have been studied in [129], and a beautiful theory has emerged. For example, the hulls K form almost surely a simple path if and only if κ ≤ 4. If κ > 8, then SLE_{κ} generates almost surely a space-filling curve.

Schramm [134] has identified the relevant value of κ for several different processes, and has indicated that percolation has scaling limit SLE_{6}, but full rigorous proofs are incomplete. In the case of percolation, Smirnov [137, 138] has proved the very remarkable result that, for site percolation on the triangular lattice, the scaling limit exists and is SLE_{6} (this last statement is illustrated and partly explained in Figure 6.2), but the existence of the limit is open for other lattices and for bond percolation.

It is possible to perform calculations on stochastic Löwner evolutions, and in particular to confirm, [109, 139], the values of many critical exponents associated with percolation (or, at least, site percolation on the triangular lattice). The consequences are in agreement with predictions of mathematical physicists previously considered near-miraculous (see [71], Chapter 9). In addition, SLE_{6} satisfies the appropriate version of Cardy’s formula, [34, 106].

Figure 6.2. Site percolation on the triangular lattice with p equal to the critical point \frac{1}{2} , and with a mixed boundary condition along the lower side. The interface traces the boundary between the white and the black clusters touching the boundary, and is termed the ‘exploration process’. In the limit of small lattice-spacing, the interface converges in a certain manner to the graph of a function which satisfies the Löwner differential equation driven by a Brownian motion with variance parameter κ = 6.

The technology of SLE is a major piece of contemporary mathematics which promises to explain phase transitions in an important class of two-dimensional disordered systems, and to help bridge the gap between probability theory and conformal field theory. It has already provided complete explanations of conjectures, by mathematicians and physicists, associated with two-dimensional Brownian motions and specifically their intersection exponents and fractionality of frontier, [107, 108].

Extra work is needed in order to prove the validity of the limiting operation for other percolation models and random processes. In another remarkable recent paper [110], Lawler, Schramm, and Werner have verified the existence of the scaling limit for loop-erased random walk and for the uniform spanning tree Peano curve, and have shown them to be SLE_{2} and SLE_{8} respectively. It is believed that selfavoiding walk on 𝕃^{2}, [113], has scaling limit SLE_{8/3}.

We turn now to the random-cluster model on 𝕃^{2} with parameters p and q. For 1 ≤ q < 4, it is believed that the percolation probability θ(p, q), viewed as a function of p, is continuous at the critical point p_{c}(q) (OP), and furthermore that p_{c}(q) = \sqrt{q}/(1 + \sqrt{q}). It seems likely that, when re-scaled in the manner similar to that of percolation (illustrated in Figure 6.2), the exploration process of the model converges to a limit process of SLE type. It then remains only to specify the parameter κ of the limit in terms of q. It has been conjectured in [129] that κ satisfies cos(4π/κ) = −\frac{1}{2} \sqrt{q}, κ ∈ (4, 8). This value is consistent with Smirnov’s theorem [138], and also with the finding of [110] that the scaling limit of the uniform spanning tree Peano curve is SLE_{8}, on recalling that the uniform spanning tree measure is obtainable as a limit of the random-cluster measure as p, q ↓ 0 (recall Section 2.4).

There are uncertainties over how this programme will develop. For a start, the theory of random-cluster models is not as complete as that of percolation and of the uniform spanning tree. Secondly, the existence of spatial limits is currently known only in certain special cases. The programme is however ambitious and full of promise, and should ultimately yield a full picture of the critical behaviour — including values of exponents — of random-cluster models, and hence of Ising/Potts models, with q ≤ 4.

7. On complete graphs and trees

While considerations of ‘real space–time’ support the study of such models on lattices such as 𝕃^{d}, it has proved rewarding also to analyse the random-cluster model on certain other graphs including complete graphs and trees. It is the presence of circuits in the underlying graph which is the root cause of dependence between the states of edges, and for this reason it is the complete graph which provides an appropriate setting for what is termed ‘mean-field theory’, in which vertices ‘interact’ with all other vertices rather than with a selected subset of ‘neighbours’. Trees, on the other hand, contain no circuits, and their random-cluster theory is therefore sterile unless one introduces boundary conditions. [A different approach to mean-field theory has been studied in [98], namely on 𝕃^{d} for large d.]

7.1 On complete graphs

The mean-field Potts model may be formulated as a Potts model on the complete graph K_{n}, being the graph with n labelled vertices every pair of which is joined by an edge. The study of such a process dates back at least to 1954, [99], and has been continued over the last fifty years [27, 98, 149]. The model is exactly soluble in the sense that quantities of interest may be calculated exactly and rigorously. It is therefore not surprising that the corresponding random-cluster models (for real q) have ‘exact solutions’ also, [27].

Consider the random-cluster measure ψ_{n,λ,q} = ϕ_{K_{n},λ/n,q} on the complete graph K_{n}, having parameters p = λ/n and q; this is the appropriate scaling to allow an interesting limit as n → ∞. In the case q = 1, this measure is product measure, and therefore the ensuing graph is an Erdős–Rényi random graph [26, 89]. The overall picture for general values of q is rather richer than for the case q = 1, and many exact calculations may be performed rigorously. It turns out that the phase transition is of first-order if and only if q > 2, and the behaviour of the system depends on how λ compares with a ‘critical value’ λ_{c}(q) taking the value

λ_{c}(q) = \{ \begin{matrix}q & if 0 < q ≤ 2, \\ 2 (\frac{q − 1}{q − 2}) log(q − 1) & if q > 2. \end{matrix}

θ(λ, q) λ_{c}(q)  λ θ(λ, q) λ_{c}(q)  λ θ(λ, q) λ_{c}(q)  λ q < 2  q = 2  q > 2

Figure 7.1. The function θ(λ, q) for the three cases q < 2, q = 2, q > 2.

From the detailed picture described in [27] the following information may be extracted. The given properties occur with ψ_{n,λ,q}-probability tending to 1 as n → ∞.

I. Subcritical case, when λ < λ_{c}(q). The largest component of the graph is of order log n.

II. Supercritical case, when λ > λ_{c}(q). There is a ‘giant component’ having order θ(λ, q)n where θ is defined to be the largest root of the equation

e^{λθ} = \frac{1 + (q − 1)θ}{1 − θ} .

III. Critical case, when λ = λ_{c}(q), 0 < q ≤ 2. The largest component has order n^{2/3}.

IV. Critical case, when λ = λ_{c}(q), q > 2. The largest component is either of order log n or of order θ(λ, q)n, where θ is given as in case II above.

The dichotomy between first- and second-order phase transition is seen by studying the function θ(λ, q), sketched in Figure 7.1. When 0 < q ≤ 2, the function θ(λ, q) descends continuously to 0 as λ ↓ λ_{c}(q). On the other hand, this limit is strictly positive when q > 2.

The above results are obtained via a relationship between the model for general q and the model for the special case q = 1. The latter system has been analysed extensively, [26, 89]. We illustrate the argument in the case q ≥ 1; a similar approach is valid when q < 1. Consider the open clusters C_{1}, C_{2}, …, C_{m} of a sample from the random-cluster measure ϕ_{K_{n},p,q}. We colour each such cluster red with probability ρ, and white otherwise, different clusters receiving independent colours. We delete all vertices in white clusters, and let H denote the remaining graph, comprising a certain random number N of vertices (from the red clusters) together with certain open edges joining pairs of them. It may be seen that, conditional on the value of N, the measure governing H is the random-cluster measure with parameters p and qρ. We choose ρ = 1/q to obtain an Erdős–Rényi random graph on a random set of vertices. This is the observation which permits the full analysis to proceed.

One consequence of this study is an explicit identification of the exponential asymptotics of the partition function Z_{K_{n},λ/n,q}, namely of the limit function

f(λ, q) = lim_{n→∞} \{\frac{1}{n} log Z_{K_{n},λ/n,q}\} .

This provides information via the Gärtner–Ellis theorem, [43], concerning the largedeviation theory of the number of clusters in such systems.

7.2 On trees and non-amenable graphs Whereas physical considerations support the study of interacting systems on finitedimensional lattices, mathematicians have been drawn also to the study of general graphs, thus enabling a clearer elucidation of the mathematical structure of such systems (see the discussion in [133]). A subject of special focus has been the class of graphs for which the ratio of surface to volume of finite boxes does not approach zero in the limit as the size of the box tends to infinity. A prime example of such a graph is an infinite regular tree with vertex degree at least three. We make the distinction more concrete as follows. Let G = (V, E) be an infinite connected graph with finite vertex degrees. For W ⊆ V, we define its boundary ∂W to be the set of all w ∈ W having some neighbour v not belonging to W. The countably infinite graph G is called amenable if its ‘Cheeger constant’

κ(G) = inf \{\frac{|∂W |}{|W |} : W ⊆ V, 0 < |W | < ∞\}

satisfies κ(G) = 0; G is called non-amenable if κ(G) > 0. It is easily seen that 𝕃^{d} is amenable, whereas an infinite regular tree with degree at least three is nonamenable.

The role of amenability in probability theory has been evident since the work of Kesten [94, 95] concerning random walks on a general graph G. More relevant to this review are [18, 75], which consider the number of infinite clusters in the bond percolation model on G. Suppose G is a quasi-transitive graph (that is, its vertex set has only finitely many orbits under its automorphism group). Suppose in addition that G is amenable. Consider bond percolation on G with density p. It may be proved as in [31, 58] that the number I of infinite open clusters satisfies

either P_{p}(I = 0) = 1 or P_{p}(I = 1) = 1.

That is, if an infinite open cluster exists, then it is almost surely unique. Under similar assumptions on a non-amenable graph G, it is believed but not yet proved in full generality that there exists an interval of values of p for which P_{p}(I = ∞) = 1; see, for example, the discussion in [112]. A corresponding question for random-cluster models is to ascertain for which graphs G and values of q there is non-uniqueness of random-cluster measures for an interval of values of p. [Recall Theorem 3.7, easily extended to more general amenable graphs, which states that, for q ≥ 1, there is a unique random-cluster measure on 𝕃^{d} for all except at most countably many values of p.] See [81, 91] and especially [133, Section 6.1] for recent accounts of this and associated questions, and [79] for an analysis of random-cluster measures on regular trees.

8. Time-evolutions of random-cluster models

Let μ be a probability measure on a space (Ω, F). We may study stochastic processes taking values in Ω which converge weakly to μ in the limit of large times. There are a multiplicity of reasons for and benefits in studying time-evolutions. First, physical systems generally have dynamics as well as equilibria. Secondly, new questions of interest arise, such as that of the estimation of a relaxation time. Thirdly, the dynamics thus introduced can yield a new technique for studying the limit measure μ.

When studying a physical system, it is often acceptable to restrict oneself to dynamics which are reversible in time. In Section 8.1, we describe a natural reversible dynamic for a random-cluster model, akin to the Glauber dynamics of the Ising model. This dynamic permits an extension which couples together the randomcluster measures on a given graph as p and q range over their possible values.

The problem commonly arises in statistics, computer science, and statistical physics of how to obtain a sample from a system governed by a probability measure with complex structure. In Section 8.2 we summarise the Propp–Wilson ‘coupling from the past’ approach, [127], to this problem in the context of the random-cluster measure.

Since Potts models may be obtained from random-cluster models, there is an interplay between the dynamics for these two systems. A famous instance of this relationship is the so-called Swendsen–Wang dynamic [140], which is described in Section 8.3.

We assume throughout this section that G = (V, E) is a finite connected graph, and that ϕ_{p,q} is the random-cluster measure on Ω = {0, 1}^{E} with 0 < p < 1 and q > 0.

8.1 Reversible dynamics

We shall consider transitions from a configuration ω to configurations which differ from ω on one edge only. Thus we introduce the following notation. For ω ∈ Ω and e ∈ E, let ω^{e} and ω_{e} be the configurations obtained by ‘switching e on’ and ‘switching e off’, respectively, that is

ω^{e}(f) = \{ \begin{matrix}1 & if f = e, \\ ω(f) & if f ≠ e, \end{matrix} ω_{e}(f) = \{ \begin{matrix}0 & if f = e, \\ ω(f) & if f ≠ e. \end{matrix}

Let (X_{t} : t ≥ 0) be a Markov chain, [77], on the state space Ω with generator Q = {q_{ω,ω′} : ω, ω′ ∈ Ω} satisfying

q_{ω_{e},ω^{e}} = p, q_{ω^{e},ω_{e}} = (1 − p)q^{D(e,ω_{e})}, for ω ∈ Ω, e ∈ E,

where D(e, ξ) is the indicator function of the event that the endpoints of e are joined by no open path of ξ. This specifies the rate at which single edges are acquired or lost. We set q_{ω,ξ} = 0 if ω and ξ differ on two or more edges, and we choose the diagonal elements q_{ω,ω} in such a way that Q, when viewed as a matrix, has row sums zero, that is,

q_{ω,ω} = − ∑_{ξ:ξ≠ω} q_{ω,ξ}.

It is elementary that the ‘detailed balance equations’

ϕ_{p,q}(ω)q_{ω,ω′} = ϕ_{p,q}(ω′)q_{ω′,ω}, ω, ω′ ∈ Ω,

hold, whence X is reversible with respect to ϕ_{p,q}. It follows by the irreducibility of the chain that X_{t} ⇒ ϕ_{p,q} as t → ∞ (where ‘⇒’ denotes weak convergence). There are of course many Markov chains with generators satisfying the above detailed balance equations, the important quantity is the ratio q_{ω,ω′}/q_{ω′,ω}.

Two extensions of this dynamical structure which have proved useful are as follows. The evolution may be specified in terms of a ‘graphical representation’ constructed via a family of independent Poisson processes. This allows a natural coupling of the measures ϕ_{p,q} for different p and q. Such couplings are monotone in p when q ≥ 1. One may similarly couple the unconditional measure ϕ_{p,q}(·) and the conditioned measure ϕ_{p,q}(· | A). Such couplings permit probabilistic interpretations of differences of the form ϕ_{p′,q}(B | A) − ϕ_{p,q}(B) when q ≥ 1, p ≤ p′, and A and B are increasing, and this can be useful in particular calculations (see [20, 68, 69]).

We turn now to the thermodynamic limit, and the question of the structure of a Markovian random-cluster process on an infinite connected graph. In the case q ≥ 1, the above couplings are monotone in the choice of the underlying graph G. Therefore there exist ‘limit dynamics’ as G passes through an increasing sequence of finite graphs. Boundary conditions may be introduced, and one may obtain thereby a certain Markov process ζ = (ζ_{t} : t ≥ 0) on the state space [0, 1]^{𝔼}, where 𝔼 is the limiting (infinite) edge set. This process, which does not generally have the Feller property, generates a pair of ‘level-set processes’ taking values in {0, 1}^{𝔼}, defined for 0 ≤ p ≤ 1 by

ζ_{t}^{p,−}(e) = 1_{{ζ_{t}(e)>1−p}}, ζ_{t}^{p,+}(e) = 1_{{ζ_{t}(e)≥1−p}}, e ∈ 𝔼,

where, as before, 1_{A} denotes the indicator function of an event A. These two processes are Markovian and are reversible with respect to the infinite-volume free and wired random-cluster measures, respectively. See [69].

Note that the generator of the Markov chain given above depends on the random variable D(e, ω_{e}), and that this random variable is a ‘non-local’ function of the configuration ω in the sense that there is no absolute bound on the distance from e of edges whose states may be relevant to its value. It is this feature of non-locality which leads to interesting complications linked in part to the 0/1-infinite-cluster property introduced before Theorem 3.9. Further discussion may be found in [69, 120].

8.2 Coupling from the past

In running Monte Carlo experiments, one requires the ability to sample from the probability measure ϕ_{p,q}. The Markov chain X_{t} of Section 8.1 certainly converges weakly to ϕ_{p,q} as t → ∞, but this is not as good as having in the hand a sample with the exact distribution. Random-cluster measures are well suited to the Propp– Wilson approach to sampling termed ‘coupling from the past’, [127], and we sketch this here. Some illustrations may be found in [90].

First we provide ourselves with a discrete-time reversible Markov chain (Z_{n} : n ≥ 0) on the state space Ω having invariant measure ϕ_{p,q}. The so-called heat-bath algorithm provides a suitable example of such a chain, and proceeds as follows. At each stage, we pick a random edge e, chosen uniformly from E and independently of all earlier choices, and we make e open with the correct conditional probability, given the configuration on the other edges. The corresponding transition matrix is given by Π = {π_{ω,ω′} : ω, ω′ ∈ Ω} where

π_{ω_{e},ω^{e}} = \frac{1}{|E|} · \frac{ϕ_{p,q}(ω^{e})}{ϕ_{p,q}(ω^{e}) + ϕ_{p,q}(ω_{e})},
π_{ω^{e},ω_{e}} = \frac{1}{|E|} · \frac{ϕ_{p,q}(ω_{e})}{ϕ_{p,q}(ω^{e}) + ϕ_{p,q}(ω_{e})}.

A neat way to do this is as follows. Suppose that Z_{n} = ω. Let e_{n} be a random edge of E, and let U_{n} be uniformly distributed on the interval [0, 1], these variables being chosen independently of all earlier choices. We obtain Z_{n+1} from ω by retaining the states of all edges except possibly that of e_{n}. We set

Z_{n+1}(e_{n}) = 0 if and only if U_{n} ≤ \frac{ϕ_{p,q}(ω_{e})}{ϕ_{p,q}(ω^{e}) + ϕ_{p,q}(ω_{e})}.

Thus the evolution of the chain is determined by the sequences e_{n}, U_{n}, and the initial state Z_{0}. One may make this construction explicit by writing Z_{n+1} = ψ(Z_{n}, e_{n}, U_{n}) (= ψ(ω, e_{n}, U_{n})) for some function ψ : Ω × E × [0, 1] → Ω. It is easily seen by the Holley condition of Section 3.1 that, if q ≥ 1, and for every e and u, the function ψ(·, e, u) is non-decreasing in its first argument. It follows that the coupling is ‘monotone’ in the sense that, if ω ≤ ω′, then the chain starting at ω lies at all times beneath the chain starting at ω′ (using the partial order on Ω).

We let W = (W (ω) : ω ∈ Ω) be a vector of random variables such that W (ω) has the distribution of Z_{1} conditional on Z_{0} = ω. Following the scheme described above, we may take W (ω) = ψ(ω, e, U) where e and U are chosen at random. Let W_{−m}, m ≥ 1, be independent random vectors distributed as W, that is, W_{−m}(·) = ψ(·, e_{m}, U_{m}) where the set {(e_{m}, U_{m}) : m ≥ 1} comprises independent pairs of independent random variables, each e_{i} being uniform on E, and each U_{i} being uniform on [0, 1]. We now construct a sequence Y_{−n}, n ≥ 1, of random maps from Ω to Ω by the following inductive procedure. First, for ω ∈ Ω, we set Y_{−1}(ω) = W_{−1}(ω). Having found Y_{−1}, Y_{−2}, …, Y_{−m}, we define Y_{−m−1}(ω) = Y_{−m}(W_{−m−1}(ω)). That is, Y_{−m−1}(ω) is obtained from ω by passing in one step to W_{−m−1}(ω), and then applying Y_{−m} to this new state. The exact dependence structure of this scheme is an important ingredient of what follows.

We stop this process at the earliest time m at which ‘coalescence has occurred’, that is, at the moment M given by M = min{m : Y_{−m}(·) is the constant function}. It is a theorem, [127], that M is ϕ_{p,q}-a.s. finite and, for any ω, the random output Y_{−M}(ω) is governed exactly by the probability measure ϕ_{p,q}.

This procedure looks unwieldy, since Ω is typically rather large, but the reality is simpler when q ≥ 1. By the monotonicity of the above coupling when q ≥ 1, it suffices to follow the trajectories of the ‘smallest’ and ‘largest’ configurations, namely those beginning, respectively, with every edge closed and with every edge open. The processes starting at intermediate configurations remain sandwiched between the extremal processes, for all times t. Thus one may define M by M = min{m : Y_{−m}(0) = Y_{−m}(1)}, where 0 and 1 denote the vectors of zeros and ones as before.

8.3 Swendsen–Wang dynamics

It is a major target of statistical physics to understand the time-evolution of disordered systems, and a prime example lies in the study of the Ising model. A multiplicity of types of dynamics have been proposed. The majority of these share a quality of ‘locality’ in the sense that the evolution involves changes to the states of vertices in close proximity to one another, perhaps single spin-flips, or spinexchanges. The state space is generally large, of size 2^{N} where N is the number of vertices, and the Hamiltonian has complicated structure. When subjected to ‘local dynamics’, the process may approach equilibrium very slowly (see [114, 132] for accounts of recent work of relevance). ‘Non-local dynamics’, on the other hand, have the potential to approach equilibrium faster, since they permit large jumps around the state space, relatively unconstrained by neighbourly relations. The random-cluster model has played a role in the development of a simple but attractive such system, namely that proposed by Swendsen and Wang [140] and described as follows for the Potts model with q states.

As usual, G = (V, E) is a finite graph, typically a large box in ℤ^{d}, and Σ = {1, 2, …, q}^{V} is the state space of a Potts model on G. We write Ω = {0, 1}^{E}. Suppose that, at some time n, we have obtained a configuration σ_{n} (∈ Σ). We construct σ_{n+1} as follows. Let p = 1 − e^{−βJ} where 0 < βJ < ∞.

I. We let ω_{n} ∈ Ω be given as follows. For e = ⟨x, y⟩ ∈ E,

if σ_{n}(x) ≠ σ_{n}(y), let ω_{n}(e) = 0,
if σ_{n}(x) = σ_{n}(y), let ω_{n}(e) = \{ \begin{matrix}1 & with probability p, \\ 0 & otherwise, \end{matrix}

different edges receiving independent states. The edge configuration ω_{n} is carried forward to the next stage.

II. To each cluster C of the graph (V, η(ω_{n})) we assign an integer chosen uniformly at random from the set {1, 2, …, q}, different clusters receiving independent labels. We let σ_{n+1}(x) be the value thus assigned to the cluster containing the vertex x.

It may be checked that the Markov chain (σ_{n} : n ≥ 0) has as unique invariant measure the Potts measure on Σ with parameters β and J. (Recall paragraph (c) of Section 2.3.)

The Swendsen–Wang algorithm leads to samples which generally converge to equilibrium faster than those defined via local dynamics. This is especially evident in the ‘high β’ (or ‘low temperature’) phase, for the following reason. Consider for example the simulation of an Ising model on a finite box with free boundary conditions, and suppose that the initial state is +1 at all vertices. If β is large, then local dynamics result in samples which remain close to the ‘+ phase’ for a very long time. Only after a long wait will the process achieve an average magnetisation close to 0. Swendsen–Wang dynamics, on the other hand, can achieve large jumps in average magnetisation even in a single step, since the spin allocated to a given large cluster of the corresponding random-cluster model is equally likely to be either of the two possibilities. A rigorous analysis of rates of convergence is however incomplete. It turns out that, at the critical point, Swendsen–Wang dynamics approach equilibrium only slowly, [29]. A further discussion is available in [61].

Algorithms of Swendsen–Wang type have been described for other statistical mechanical models having graphical representations of random-cluster-type; see [41, 42]. Related work may be found in [147].

Acknowledgements. GRG recalls John Hammersley passing to him in 1971 a copy of Fortuin’s thesis [52] in which much of the basic theory is developed. Piet Kasteleyn kindly filled out the origins of random-cluster models in two letters addressed to GRG in November 1992. The author acknowledges the opportunity given by the Landau Center of the Hebrew University, Jerusalem, to deliver a course of lectures on the random-cluster model during July 2001. Harry Kesten kindly criticised a draft of the work. Thanks are due to Malwina Łuczak for her contributions to discussions on certain topics in this paper, and to Ágoston Pisztora for reading and commenting on parts of it. The further suggestions of Christian Borgs, Olle Häggström, Russell Lyons, Roberto Schonmann, and Oded Schramm have been appreciated.

References

1. Aizenman, M., Geometric analysis of ϕ^{4} fields and Ising models, Communications in Mathematical Physics 86 (1982), 1–48.

2. Aizenman, M., Barsky, D. J., Fernández, R., The phase transition in a general class of Ising-type models is sharp, Communications in Mathematical Physics 47 (1987), 343–374.

3. Aizenman, M., Chayes, J. T., Chayes, L., Newman, C. M., The phase boundary in dilute and random Ising and Potts ferromagnets, Journal of Physics A: Mathematical and General 20 (1987), L313–L318.

4. Aizenman, M., Chayes, J. T., Chayes, L., Newman, C. M., Discontinuity of the magnetization in one-dimensional 1/|x − y|^{2} Ising and Potts models, Journal of Statistical Physics 50 (1988), 1–40.

5. Aizenman, M., Fernández, R., On the critical behavior of the magnetization in high-dimen-sional Ising models, Journal of Statistical Physics 44 (1986), 393–454.

6. Alexander, K., Simultaneous uniqueness of infinite clusters in stationary random labeled graphs, Communications in Mathematical Physics 168 (1995), 39–55.

7. Alexander, K., Weak mixing in lattice models, Probability Theory and Related Fields 110 (1998), 441–471.

8. Alexander, K., The asymmetric random cluster model and comparison of Ising and Potts models, Probability Theory and Related Fields 120 (2001), 395–444.

9. Alexander, K., Power-law corrections to exponential decay of connectivities and correlations in lattice models, Annals of Probability 29 (2001), 92–122.

10. Alexander, K., Cube-root boundary fluctuations for droplets in random cluster models, Communications in Mathematical Physics 224 (2001), 733–781.

11. Alexander, K., The single-droplet theorem for random-cluster models, In and Out of Equilibrium (Sidoravicius, V., ed.), Birkhäuser, Boston, 2002, pp. 47–73.

12. Alexander, K., Unpublished (2002).

13. Ashkin, J., Teller, E., Statistics of two-dimensional lattices with four components, The Physical Review 64 (1943), 178–184.

14. Barlow, R. N., Proschan, F., Mathematical Theory of Reliability, Wiley, New York, 1965.

15. Baxter, R. J., Exactly Solved Models in Statistical Mechanics, Academic Press, London, 1982.

16. Beijeren, H. van, Interface sharpness in the Ising system, Communications in Mathematical Physics 40 (1975), 1–6.

17. Benjamini, I., Lyons, R., Peres, Y., Schramm, O., Uniform spanning forests, Annals of Probability 29 (2001), 1–65.

18. Benjamini, I., Schramm, O., Percolation beyond ℤ^{d}, many questions and a few answers, Electronic Communications in Probability 1 (1996), 71–82.

19. Berg, J. van den, Kesten, H., Inequalities with applications to percolation and reliability, Journal of Applied Probability 22 (1985), 556–569.

20. Bezuidenhout, C. E., Grimmett, G. R., Kesten, H., Strict inequality for critical values of Potts models and random-cluster processes, Communications in Mathematical Physics 158 (1993), 1–16.

21. Biggs, N. L., Algebraic Graph Theory, Cambridge University Press, Cambridge, 1984.

22. Biggs, N. L., Interaction Models, LMS Lecture Note Series no. 30, Cambridge University Press, Cambridge, 1977.

23. Billingsley, P., Convergence of Probability Measures, Wiley, New York, 1968.

24. Biskup, M., Borgs, C., Chayes, J. T., Kotecký, R., Gibbs states of graphical representations of the Potts model with external fields. Probabilistic techniques in equilibrium and nonequilibrium statistical physics, Journal of Mathematical Physics 41 (2000), 1170–1210.

25. Bodineau, T., The Wulff construction in three and more dimensions, Communications in Mathematical Physics 207 (1999), 197–229.

26. Bollobás, B., Random Graphs, Academic Press, London, 1985.

27. Bollobás, B., Grimmett, G. R., Janson, S., The random-cluster process on the complete graph, Probability Theory and Related Fields 104 (1996), 283–317.

28. Borgs, C., Chayes, J. T., The covariance matrix of the Potts model: A random-cluster analysis, Journal of Statistical Physics 82 (1996), 1235–1297.

29. Borgs, C., Chayes, J. T., Frieze, A. M., Kim, J. H., Tetali, E., Vigoda, E., Vu, V. V., Torpid mixing of some MCMC algorithms in statistical physics, Proceedings of the 40th IEEE Symposium on the Foundations of Computer Science (1999), 218–229.

30. Broadbent, S. R. and Hammersley, J. M., Percolation processes I. Crystals and mazes, Proceedings of the Cambridge Philosophical Society 53 (1957), 629–641.

31. Burton, R. M., Keane, M., Density and uniqueness in percolation, Communications in Mathematical Physics 121 (1989), 501–505.

32. Campanino, M., Chayes, J. T., Chayes, L., Gaussian fluctuations of connectivities in the subcritical regime of percolation, Probability Theory and Related Fields 88 (1991), 269–341.

33. Campanino, M., Ioffe, D., Velenik, Y., Ornstein–Zernike theory for the finite range Ising models above T_{c}, Probability Theory and Related Fields (2002) (to appear).

34. Cardy, J., Critical percolation in finite geometries, Journal of Physics A: Mathematical and General 25 (1992), L201.

35. Cerf, R., Kenyon, R., The low-temperature expansion of the Wulff crystal in the 3D Ising model, Communications in Mathematical Physics 222 (2001), 147–179.

36. Cerf, R., Pisztora, Á., On the Wulff crystal in the Ising model, Annals of Probability 28 (2000), 947–1017.

37. Cerf, R., Pisztora, Á., Phase coexistence in Ising, Potts and percolation models, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 37 (2001), 643–724.

38. Černý, J., Kotecký, R., Interfaces for random cluster models (2001) (to appear).

39. Chayes, J. T., Chayes, L., Kotecký, R., The analysis of the Widom–Rowlinson model by stochastic geometric methods, Communications in Mathematical Physics 172 (1995), 551– 569.

40. Chayes, L., Kotecký, R., Intermediate phase for a classical continuum model, Physical Review B 54 (1996), 9221–9224.

41. Chayes, L., Machta, J., Graphical representations and cluster algorithms, Part I: discrete spin systems, Physica A 239 (1997), 542–601.

42. Chayes, L., Machta, J., Graphical representations and cluster algorithms, II, Physica A 254 (1998), 477–516.

43. Dembo, A., Zeitouni, O., Large deviations techniques and applications, 2nd edition, Springer, New York, 1998.

44. Dobrushin, R. L., Gibbsian random fields for lattice systems and pairwise interactions, Functional Analysis and its Applications (in translation) 2 (1968), 292–301.

45. Doyle, P. G., Snell, J. L., Random Walks and Electric Networks, Carus Mathematical Monographs 22, Mathematical Association of America, Washington, DC, 1984.

46. Edwards, S. F., Anderson, P. W., Theory of spin glasses, Journal of Physics F: Metal Physics 5 (1975), 965–974.

47. Edwards, R. G., Sokal, A. D., Generalization of the Fortuin–Kasteleyn–Swendsen–Wang representation and Monte Carlo algorithm, The Physical Review D 38 (1988), 2009–2012.

48. Feder, T., Mihail, M., Balanced matroids, Proceedings of the 24th ACM Symposium on the Theory of Computing (1992), 26–38.

49. Fernández, R., Ferrari, P. A., Garcia, N. L., Loss network representation for Peierls contours, Annals of Probability 29 (2001), 902–937.

50. Fernández, R., Ferrari, P. A., Garcia, N. L., Perfect simulation for interacting point processes, loss networks and Ising models (2000) (to appear).

51. Fernández, R., Fröhlich, J., Sokal, A. D., Random Walks, Critical Phenomena, and Triviality in Quantum Field Theory, Springer, Berlin, 1992.

52. Fortuin, C. M., On the random-cluster model, Doctoral thesis, University of Leiden, 1971.

53. Fortuin, C. M., On the random-cluster model. II. The percolation model, Physica 58 (1972), 393–418.

54. Fortuin, C. M., On the random-cluster model. III. The simple random-cluster process, Physica 59 (1972), 545–570.

55. Fortuin, C. M., Kasteleyn, P. W., On the random-cluster model. I. Introduction and relation to other models, Physica 57 (1972), 536–564.

56. Fortuin, C. M., Kasteleyn, P. W., Ginibre, J., Correlation inequalities on some partially ordered sets, Communications in Mathematical Physics 22 (1971), 89–103.

57. Gallavotti, G., Miracle-Solé, S., Equilibrium states of the Ising model in the two-phase region, Physical Review B 5 (1972), 2555–2559.

58. Gandolfi, A., Keane, M., Newman, C. M., Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses, Probability Theory and Related Fields 92 (1992), 511–527.

59. Georgii, H.-O., Gibbs measures and phase transitions, Walter de Gruyter, Berlin, 1988.

60. Georgii, H.-O., Häggström, O., Phase transition in continuum Potts models, Communications in Mathematical Physics 181 (1996), 507–528.

61. Georgii, H.-O., Häggström, O., Maes, C., The random geometry of equilibrium phases, Phase Transitions and Critical Phenomena (Domb, C., Lebowitz, J. L., eds.), vol. 18, Academic Press, London, 2000, pp. 1–142,.

62. Gielis, G., Grimmett, G. R., Rigidity of the interface in percolation and random-cluster models, Journal of Statistical Physics 109 (2002), 1–37.

63. Grimmett, G. R., Unpublished (1991).

64. Grimmett, G. R., Differential inequalities for Potts and random-cluster processes, Cellular Automata and Cooperative Systems (N. Boccara et al., eds.), Kluwer, Dordrecht, 1993, pp. 227–236.

65. Grimmett, G. R., Potts models and random-cluster processes with many-body interactions, Journal of Statistical Physics 75 (1994), 67–121.

66. Grimmett, G. R., The random-cluster model, Probability, Statistics and Optimisation (F. P. Kelly, ed.), Wiley, Chichester, 1994, pp. 49–63.

67. Grimmett, G. R., Percolative problems, Probability and Phase Transition (G. R. Grimmett, ed.), Kluwer, Dordrecht, 1994, pp. 69–86.

68. Grimmett, G. R., Comparison and disjoint-occurrence inequalities for random-cluster models, Journal of Statistical Physics 78 (1995), 1311–1324.

69. Grimmett, G. R., The stochastic random-cluster process and the uniqueness of randomcluster measures, Annals of Probability 23 (1995), 1461–1510.

70. Grimmett, G. R., Percolation and disordered systems, Ecole d’Eté de Probabilités de Saint Flour XXVI–1996 (P. Bernard, ed.), Lecture Notes in Mathematics no. 1665, Springer, Berlin, 1997, pp. 153–300.

71. Grimmett, G. R., Percolation, 2nd edition, Springer, Berlin, 1999.

72. Grimmett, G. R., Inequalities and entanglements for percolation and random-cluster models, Perplexing Problems in Probability; Festschrift in Honor of Harry Kesten (M. Bramson, R. Durrett, eds.), Birkhäuser, Boston, 1999, pp. 91–105.

73. Grimmett, G. R., Unpublished (2002).

74. Grimmett, G. R., Marstrand, J. M., The supercritical phase of percolation is well behaved, Proceedings of the Royal Society (London), Series A 430 (1990), 439–457.

75. Grimmett, G. R., Newman, C. M., Percolation in ∞ + 1 dimensions, Disorder in Physical Systems (G. R. Grimmett, D. J. A. Welsh, eds.), Oxford University Press, Oxford, 1990, pp. 219–240.

76. Grimmett, G. R., Piza, M. S. T., Decay of correlations in subcritical Potts and randomcluster models, Communications in Mathematical Physics 189 (1997), 465–480.

77. Grimmett, G. R., Stirzaker, D. R., Probability and Random Processes, 3rd edition, Oxford University Press, Oxford, 2001.

78. Häggström, O., Random-cluster measures and uniform spanning trees, Stochastic Processes and their Applications 59 (1995), 267–275.

79. Häggström, O., The random-cluster model on a homogeneous tree, Probability Theory and Related Fields 104 (1996), 231–253.

80. Häggström, O., Random-cluster representations in the study of phase transitions, Markov Processes and Related Fields 4 (1998), 275–321.

81. Häggström, O., Jonasson, J., Lyons, R., Explicit isoperimetric constants and phase transitions in the random-cluster model, Annals of Probability 30 (2002), 443–473.

82. Häggström, O., Jonasson, J., Lyons, R., Coupling and Bernoullicity in random-cluster and Potts models, Bernoulli 8 (2002), 275–294.

83. Hammersley, J. M., Percolation processes. Lower bounds for the critical probability, Annals of Mathematical Statistics 28 (1957), 790–795.

84. Hara, T., Slade, G., Mean-field critical behaviour for percolation in high dimensions, Communications in Mathematical Physics 128 (1990), 333–391.

85. Hara, T., Slade, G., The scaling limit of the incipient infinite cluster in high-dimensional percolation. II. Integrated super-Brownian excursion, Journal of Mathematical Physics 41 (2000), 1244–1293.

86. Hintermann, D., Kunz, H., Wu, F. Y., Exact results for the Potts model in two dimensions, Journal of Statistical Physics 19 (1978), 623–632.

87. Holley, R., Remarks on the FKG inequalities, Communications in Mathematical Physics 36 (1974), 227–231.

88. Ising, E., Beitrag zur Theorie des Ferromagnetismus, Zeitschrift für Physik 31 (1925), 253– 258.

89. Janson, S., Łuczak, T., Ruciński, A., Random Graphs, Wiley, New York, 2000.

90. Jerrum, M., Mathematical foundations of the Markov chain Monte Carlo method, Probabilistic Methods for Algorithmic Discrete Mathematics (Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B., eds.), Springer, Berlin, 1998.

91. Jonasson, J., The random cluster model on a general graph and a phase transition characterization of nonamenability, Stochastic Processes and their Applications 79 (1999), 335–354.

92. Kahn, J., A normal law for matchings, Combinatorica 20 (2000), 339–391.

93. Kasteleyn, P. W., Fortuin, C. M., Phase transitions in lattice systems with random local properties, Journal of the Physical Society of Japan 26, (1969), 11–14, Supplement.

94. Kesten, H., Symmetric random walks on groups, Transactions of the American Mathematical Society 92 (1959), 336–354.

95. Kesten, H., Full Banach mean values on countable groups, Mathematica Scandinavica 7 (1959), 146–156.

96. Kesten, H., The critical probability of bond percolation on the square lattice equals \frac{1}{2} , Communications in Mathematical Physics 74 (1980), 41–59.

97. Kesten, H., Percolation Theory for Mathematicians, Birkhäuser, Boston, 1982.

98. Kesten, H., Schonmann, R. H., Behavior in large dimensions of the Potts and Heisenberg models, Reviews in Mathematical Physics 1 (1990), 147–182.

99. Kihara, T., Midzuno, Y., Shizume, J., Statistics of two-dimensional lattices with many components, Journal of the Physical Society of Japan 9 (1954), 681–687.

100. Kim, D., Joseph, R. I., Exact transition temperatures for the Potts model with q states per site for the triangular and honeycomb lattices, Journal of Physics C: Solid State Physics 7 (1974), L167–L169.

101. Kirchhoff, G., Uber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Strome gefuhrt wird, Annalen der Physik und Chemie 72 (1847), 497–508.

102. Kotecký, R., Shlosman, S., First order phase transitions in large entropy lattice systems, Communications in Mathematical Physics 83 (1982), 493–515.

103. Laanait, L., Messager, A., Ruiz, J., Phase coexistence and surface tensions for the Potts model, Communications in Mathematical Physics 105 (1986), 527–545.

104. Laanait, L., Messager, A., Miracle-Solé, S., Ruiz, J., Shlosman, S., Interfaces in the Potts model I: Pirogov–Sinai theory of the Fortuin–Kasteleyn representation, Communications in Mathematical Physics 140 (1991), 81–91.

105. Lanford, O. E., Ruelle, D., Observables at infinity and states with short range correlations in statistical mechanics, Communications in Mathematical Physics 13 (1969), 194–215.

106. Langlands, R., Pouliot, P., Saint-Aubin, Y., Conformal invariance in two-dimensional percolation, Bulletin of the American Mathematical Society 30 (1994), 1–61.

107. Lawler, G. F., Schramm, O., Werner, W., The dimension of the planar Brownian frontier is 4/3, Mathematics Research Letters 8 (2001), 401–411.

108. Lawler, G. F., Schramm, O., Werner, W., Values of Brownian intersection exponents III: Two-sided exponents, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 38 (2002), 109–123.

109. Lawler, G. F., Schramm, O., Werner, W., One-arm exponent for critical 2D percolation, Electronic Journal of Probability 7 (2002), 1–13.

110. Lawler, G. F., Schramm, O., Werner, W., Conformal invariance of planar loop-erased random walks and uniform spanning trees (2001) (to appear).

111. Lieb, E. H., A refinement of Simon’s correlation inequality, Communications in Mathematical Physics 77 (1980), 127–135.

112. Lyons, R., Phase transitions on nonamenable graphs, Journal of Mathematical Physics 41 (2001), 1099–1126.

113. Madras, N., Slade, G., The Self-Avoiding Walk, Birkhäuser, Boston, 1993.

114. Martinelli, F., Lectures on Glauber dynamics for discrete spin models, Ecole d’Eté de Probabilités de Saint Flour XXVII–1997 (P. Bernard, ed.), Lecture Notes in Mathematics no. 1717, Springer, Berlin, 1999, pp. 93–191.

115. Messager, A., Miracle-Solé, S., Ruiz, J., Shlosman, S., Interfaces in the Potts model. II. Antonov’s rule and rigidity of the order disorder interface, Communications in Mathematical Physics 140 (1991), 275–290.

116. Newman, C. M., Disordered Ising systems and random cluster representations, Probability and Phase Transition (G. R. Grimmett, ed.), Kluwer, Dordrecht, 1994, pp. 247–260.

117. Newman, C. M., Topics in Disordered Systems, Birkhäuser, Boston, 1997.

118. Onsager, L., Crystal statistics, I. A two-dimensional model with an order-disorder transition, The Physical Review 65 (1944), 117–149.

119. Pemantle, R., Towards a theory of negative dependence, Journal of Mathematical Physics 41 (2000), 1371–1390.

120. Pfister, C.-E., Vande Velde, K., Almost sure quasilocality in the random cluster model, Journal of Statistical Physics 79 (1995), 765–774.

121. Pfister, C.-E., Velenik, Y., Random-cluster representation for the Ashkin–Teller model, Journal of Statistical Physics 88 (1997), 1295–1331.

122. Pirogov, S. A., Sinai, Ya. G., Phase diagrams of classical lattice systems, Theoretical and Mathematical Physics 25 (1975), 1185–1192.

123. Pirogov, S. A., Sinai, Ya. G., Phase diagrams of classical lattice systems, continuation, Theoretical and Mathematical Physics 26 (1976), 39–49.

124. Pisztora, Á., Surface order large deviations for Ising, Potts and percolation models, Probability Theory and Related Fields 104 (1996), 427–466.

125. Potts, R. B., Some generalized order–disorder transformations, Proceedings of the Cambridge Philosophical Society 48 (1952), 106–109.

126. Preston, C. J., Gibbs States on Countable Sets, Cambridge University Press, Cambridge, 1974.

127. Propp, J. G., Wilson, D. B., Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures and Algorithms 9 (1996), 223–252.

128. Reimer, D., Proof of the van den Berg–Kesten conjecture, Combinatorics, Probability, Computing 9 (2000), 27–32.

129. Rohde, S., Schramm, O., Basic properties of SLE (2001) (to appear).

130. Russo, L., On the critical percolation probabilities, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 56 (1981), 229–237.

131. Salas, J., Sokal, A. D., Dynamic critical behavior of a Swendsen–Wang-type algorithm for the Ashkin–Teller model, Journal of Statistical Physics 85 (1996), 297–361.

132. Schonmann, R. H., Metastability and the Ising model; Proceedings of the International Congress of Mathematicians, Berlin 1998, Fischer G., Rehmann U. (eds.), Documenta Mathematica, Extra volume III (1998), 173–181.

133. Schonmann, R. H., Multiplicity of phase transitions and mean-field criticality on highly nonamenable graphs, Communications in Mathematical Physics 219 (2001), 271–322.

134. Schramm, O., Scaling limits of loop-erased walks and uniform spanning trees, Israel Journal of Mathematics 118 (2000), 221–288.

135. Simon, B., Correlation inequalities and the decay of correlations in ferromagnets, Communications in Mathematical Physics 77 (1980), 111–126.

136. Slade, G., Bounds on the self-avoiding walk connective constant, Special Issue: Proceedings of the Conference in Honor of Jean-Pierre Kahane, 1993, Journal of Fourier Analysis and its Applications (1995), 525–533.

137. Smirnov, S., Critical percolation in the plane: conformal invariance, Cardy’s formula, scaling limits, Comptes Rendus des Séances de l’Académie des Sciences. Série I. Mathématique 333 (2001), 239–244.

138. Smirnov, S., Critical percolation in the plane. I. Conformal invariance and Cardy’s formula. II. Continuum scaling limit (2001) (to appear).

139. Smirnov, S., Werner, W., Critical exponents for two-dimensional percolation, Mathematics Research Letters 8 (2001), 729–744.

140. Swendsen, R. H., Wang, J. S., Nonuniversal critical dynamics in Monte Carlo simulations, Physical Review Letters 58 (1987), 86–88.

141. Tutte, W. T., Graph Theory, Addison-Wesley, Menlo Park, California, 1984.

142. Welsh, D. J. A., Percolation in the random-cluster process, Journal of Physics A: Mathematical and General 26 (1993), 2471–2483.

143. Welsh, D. J. A., Merino, C., The Potts model and the Tutte polynomial, Journal of Mathematical Physics 41 (2000), 1127–1152.

144. Widom, B., Rowlinson, J. S., New model for the study of liquid–vapor phase transition, Journal of Chemical Physics 52 (1970), 1670–1684.

145. Wilson, R. J., Introduction to Graph Theory, Longman, London, 1979.

146. Wiseman, S., Domany, E., Cluster method for the Ashkin–Teller model, Physical Review E 48 (1993), 4080–4090.

147. Wolff, U., Collective Monte Carlo updating for spin systems, Physical Review Letters 62 (1989), 361–364.

148. Wood, De Volson, Problem 5, American Mathematical Monthly 1 (1894), 99, 211–212.

149. Wu, F. Y., The Potts model, Reviews in Modern Physics 54 (1982), 235–268.

150. Zhang, Y., Unpublished (1988), see [71], page 289.

Statistical Laboratory, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, United Kingdom

E-mail: g.r.grimmett@statslab.cam.ac.uk

URL: http://www.statslab.cam.ac.uk/∼grg/