{{Short description|Type of random graph}} In statistical mechanics, probability theory, graph theory, etc. the '''random cluster model''' is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, electrical networks, etc.<ref name=":3">{{Cite journal|title=On the random-cluster model: I. Introduction and relation to other models|journal=Physica|volume=57|issue=4|pages=536|last1=Fortuin|last2=Kasteleyn|doi=10.1016/0031-8914(72)90045-6|bibcode=1972Phy....57..536F|year=1972}}</ref><ref name=":0">{{Cite arXiv|title=Random cluster models|last=Grimmett|eprint = math/0205237|year = 2002 }}</ref> It is also referred to as the '''RC model''' or sometimes the '''FK representation''' after its founders Cees Fortuin and Piet Kasteleyn.<ref name=":2">{{Citation|last=Newman|first=Charles M.|title=Disordered Ising Systems and Random Cluster Representations|date=1994|url=https://doi.org/10.1007/978-94-015-8326-8_15|work=Probability and Phase Transition|pages=247–260|editor-last=Grimmett|editor-first=Geoffrey|series=NATO ASI Series|place=Dordrecht|publisher=Springer Netherlands|language=en|doi=10.1007/978-94-015-8326-8_15|isbn=978-94-015-8326-8|access-date=2021-04-18|url-access=subscription}}</ref> The random cluster model has a critical limit, described by a conformal field theory.
== Definition ==
Let <math>G = (V,E)</math> be a graph, and <math>\omega: E \to \{0,1\}</math> be a '''bond configuration''' on the graph that maps each edge to a value of either 0 or 1. We say that a bond is ''closed'' on edge <math>e\in E</math> if <math>\omega(e)=0</math>, and '''open''' if <math>\omega(e)=1</math>. If we let <math>A(\omega) = \{e\in E : \omega(e)=1 \}</math> be the set of open bonds, then an '''open cluster''' or '''FK cluster''' is any connected component in <math>A(\omega)</math> union the set of vertices. Note that an open cluster can be a single vertex (if that vertex is not incident to any open bonds).
Suppose an edge is open independently with probability <math>p</math> and closed otherwise, then this is just the standard Bernoulli percolation process. The probability measure of a configuration <math>\omega</math> is given as
: <math>\mu(\omega) = \prod_{e \in E} p^{\omega(e)}(1-p)^{1-\omega(e)}.</math>
The RC model is a generalization of percolation, where each cluster is weighted by a factor of <math>q</math>. Given a configuration <math>\omega</math>, we let <math>C(\omega)</math> be the number of open clusters, or alternatively the number of connected components formed by the open bonds. Then for any <math>q>0</math>, the probability measure of a configuration <math>\omega</math> is given as
: <math>\mu(\omega) = \frac{1}{Z} q^{C(\omega)}\prod_{e \in E} p^{\omega(e)}(1-p)^{1-\omega(e)}. </math>
''Z'' is the partition function, or the sum over the unnormalized weights of all configurations,
: <math>Z = \sum_{\omega \in \Omega} \left\{q^{C(\omega)}\prod_{e \in E(G)} p^{\omega(e)}(1-p)^{1-\omega(e)} \right\}. </math>
The partition function of the RC model is a specialization of the Tutte polynomial, which itself is a specialization of the multivariate Tutte polynomial.<ref>{{Cite book|title=Surveys in Combinatorics 2005|last=Sokal|first=Alan|chapter=The multivariate Tutte polynomial (Alias Potts model) for graphs and matroids|year=2005|pages=173–226|doi=10.1017/CBO9780511734885.009|arxiv=math/0503607|isbn=9780521615235|s2cid=17904893}}</ref>
== Special values of ''q'' ==
The parameter <math>q</math> of the random cluster model can take arbitrary complex values. This includes the following special cases:
* <math>q\to 0</math>: linear resistance networks.<ref name=":3" /> * <math>q < 1</math>: negatively-correlated percolation. * <math>q=1</math>: Bernoulli percolation, with <math>Z=1</math>. * <math>q=2</math>: the Ising model. * <math>q\in \mathbb{Z}^{+}</math>: <math>q</math>-state Potts model.
== Edwards-Sokal representation == The Edwards-Sokal (ES) representation<ref>{{Cite journal|last1=Edwards|first1=Robert G.|last2=Sokal|first2=Alan D.|date=1988-09-15|title=Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm|url=https://link.aps.org/doi/10.1103/PhysRevD.38.2009|journal=Physical Review D|volume=38|issue=6|pages=2009–2012|doi=10.1103/PhysRevD.38.2009|pmid=9959355|bibcode=1988PhRvD..38.2009E|url-access=subscription}}</ref> of the Potts model is named after Robert G. Edwards and Alan D. Sokal. It provides a unified representation of the Potts and random cluster models in terms of a joint distribution of spin and bond configurations.
Let <math>G = (V, E)</math> be a graph, with the number of vertices being <math>n = |V|</math> and the number of edges being <math>m = |E|</math>. We denote a spin configuration as <math>\sigma\in \mathbb{Z}_q^n</math> and a bond configuration as <math>\omega\in \{0,1\}^m</math>. The joint measure of <math>(\sigma,\omega)</math> is given as : <math> \mu(\sigma,\omega) = Z^{-1}\psi(\sigma)\phi_p(\omega)1_A(\sigma,\omega), </math> where <math>\psi</math> is the uniform measure, <math>\phi_p</math> is the product measure with density <math>p = 1-e^{-\beta}</math>, and <math> Z </math> is an appropriate normalizing constant. Importantly, the indicator function <math>1_A</math> of the set : <math> A = \{ (\sigma,\omega) : \sigma_i = \sigma_j \text{ for any edge } (i,j) \text{ where } \omega = 1 \} </math> enforces the constraint that a bond can only be open on an edge if the adjacent spins are of the same state, also known as the SW rule.
The statistics of the Potts spins can be recovered from the cluster statistics (and vice versa), thanks to the following features of the ES representation:<ref name=":0" />
* The marginal measure <math> \mu(\sigma) </math> of the spins is the Boltzmann measure of the ''q''-state Potts model at inverse temperature <math> \beta </math>. * The marginal measure <math> \phi_{p, q}(\omega) </math> of the bonds is the random-cluster measure with parameters ''q'' and ''p.'' * The conditional measure <math> \mu(\sigma \,|\, \omega) </math> of the spin represents a uniformly random assignment of spin states that are constant on each connected component of the bond arrangement <math>\omega</math>. * The conditional measure <math> \phi_{p,q}(\omega \,|\, \sigma) </math> of the bonds represents a percolation process (of ratio ''p'') on the subgraph of <math> G </math> formed by the edges where adjacent spins are aligned. * In the case of the Ising model, the probability that two vertices <math> (i,j) </math> are in the same connected component of the bond arrangement <math>\omega</math> equals the two-point correlation function of spins <math> \sigma_i \text{ and } \sigma_j </math>,<ref name="ReferenceA">{{Cite journal|last1=Kasteleyn|first1=P. W.|last2=Fortuin|first2=C. M.|date=1969|title=Phase Transitions in Lattice Systems with Random Local Properties|journal=Physical Society of Japan Journal Supplement |volume=26|pages=11|bibcode=1969JPSJS..26...11K }}</ref> written <math>\phi_{p,q}(i \leftrightarrow j) = \langle \sigma_i\sigma_j \rangle</math>.
=== Frustration === There are several complications of the ES representation once frustration is present in the spin model (e.g. the Ising model with both ferromagnetic and anti-ferromagnetic couplings in the same lattice). In particular, there is no longer a correspondence between the spin statistics and the cluster statistics,<ref>{{Cite journal|last1=Cataudella|first1=V.|last2=Franzese|first2=G.|last3=Nicodemi|first3=M.|last4=Scala|first4=A.|last5=Coniglio|first5=A.|date=1994-03-07|title=Critical clusters and efficient dynamics for frustrated spin models|url=https://link.aps.org/doi/10.1103/PhysRevLett.72.1541|journal=Physical Review Letters|volume=72|issue=10|pages=1541–1544|doi=10.1103/PhysRevLett.72.1541|pmid=10055635|bibcode=1994PhRvL..72.1541C|hdl=2445/13250|hdl-access=free}}</ref> and the correlation length of the RC model will be greater than the correlation length of the spin model. This is the reason behind the inefficiency of the SW algorithm for simulating frustrated systems.
== Two-dimensional case ==
If the underlying graph <math>G</math> is a planar graph, there is a duality between the random cluster models on <math>G</math> and on the dual graph <math>G^*</math>.<ref name="wu82"/> At the level of the partition function, the duality reads :<math> \tilde{Z}_G(q,v) = q^{|V|-|E|-1}v^{|E|} \tilde{Z}_{G^*}\left(q, \frac{q}{v}\right) \qquad \text{with} \qquad v = \frac{p}{1-p}\quad \text{and}\quad \tilde{Z}_G(q,v) = (1-p)^{-|E|}Z_G(q,v) </math> On a self-dual graph such as the square lattice, a phase transition can only occur at the self-dual coupling <math>v_\text{self-dual}=\sqrt{q}</math>.<ref>{{cite arXiv |last1=Beffara |first1=Vincent |last2=Duminil-Copin |first2=Hugo |date=2013-11-27 |title=The self-dual point of the two-dimensional random-cluster model is critical for $q\geq 1$ |class=math.PR |eprint=1006.5073 }}</ref>
The random cluster model on a planar graph can be reformulated as a '''loop model''' on the corresponding medial graph. For a configuration <math>\omega</math> of the random cluster model, the corresponding loop configuration is the set of self-avoiding loops that separate the clusters from the dual clusters. In the transfer matrix approach, the loop model is written in terms of a Temperley-Lieb algebra with the parameter <math>\delta = q+q^{-1}</math>. In two dimensions, the random cluster model is therefore closely related to the O(n) model, which is also a loop model.
In two dimensions, the critical random cluster model is described by a conformal field theory with the central charge :<math> c = 13 - 6\beta^2 - 6\beta^{-2} \qquad \text{with} \qquad q = 4\cos^2(\pi\beta^2)\ . </math> Known exact results include the conformal dimensions of the fields that detect whether a point belongs to an FK cluster or a spin cluster. In terms of Kac indices, these conformal dimensions are respectively <math>2h_{0,\frac12}</math> and <math>2h_{\frac12,0}</math>, corresponding to the fractal dimensions <math>2-2h_{0,\frac12}</math> and <math>2-2h_{\frac12,0}</math> of the clusters.
== History and applications == RC models were introduced in 1969 by Fortuin and Kasteleyn, mainly to solve combinatorial problems.<ref name=":3" /><ref name=":1">{{Cite book|last=Grimmett|title=The random cluster model|url=http://www.statslab.cam.ac.uk/~grg/books/rcm1-1.pdf}}</ref><ref name="ReferenceA"/> After their founders, it is sometimes referred to as '''FK models'''.<ref name=":2" /> In 1971 they used it to obtain the FKG inequality. Post 1987, interest in the model and applications in statistical physics reignited. It became the inspiration for the Swendsen–Wang algorithm describing the time-evolution of Potts models.<ref>{{Cite journal|last1=Swendsen|first1=Robert H.|last2=Wang|first2=Jian-Sheng|date=1987-01-12|title=Nonuniversal critical dynamics in Monte Carlo simulations|journal=Physical Review Letters|volume=58|issue=2|pages=86–88|doi=10.1103/PhysRevLett.58.86|pmid=10034599|bibcode=1987PhRvL..58...86S}}</ref> Michael Aizenman and coauthors used it to study the phase boundaries in 1D Ising and Potts models.<ref>{{Cite journal|last1=Aizenman|first1=M.|last2=Chayes|first2=J. T.|last3=Chayes|first3=L.|last4=Newman|first4=C. M.|date=April 1987|title=The phase boundary in dilute and random Ising and Potts ferromagnets|journal=Journal of Physics A: Mathematical and General|volume=20|issue=5|pages=L313–L318|doi=10.1088/0305-4470/20/5/010|issn=0305-4470|bibcode=1987JPhA...20L.313A}}</ref><ref name=":1" />
== See also ==
*Tutte polynomial *Ising model *Random graph *Swendsen–Wang algorithm *FKG inequality
== References == <references>
<ref name="wu82">{{cite journal | last=Wu | first=F. Y. | title=The Potts model | journal=Reviews of Modern Physics | publisher=American Physical Society (APS) | volume=54 | issue=1 | date=1982-01-01 | issn=0034-6861 | doi=10.1103/revmodphys.54.235 | pages=235–268| bibcode=1982RvMP...54..235W }}</ref>
</references>
== External links == *[http://mathworld.wolfram.com/Random-ClusterModel.html Random-Cluster Model – Wolfram MathWorld]
Category:Graph theory Category:Random graphs Category:Percolation theory Category:Statistical mechanics