Random cluster model

In physics, 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.^[1][2] It is also referred to as the RC model or sometimes the FK representation after its founders Kees Fortuin and Piet Kasteleyn.^[3]

Definition[]

Let ${\displaystyle G=(V,E)}$ be a graph, and ${\displaystyle \omega :E\to \{0,1\}}$ 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 ${\displaystyle e\in E}$ if ${\displaystyle \omega (e)=0}$, and open if ${\displaystyle \omega (e)=1}$. If we let ${\displaystyle A(\omega )=\{e\in E:\omega (e)=1\}}$ be the set of open bonds, then an open cluster is any connected component in ${\displaystyle A(\omega )}$. 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 ${\displaystyle p}$ and closed otherwise, then this is just the standard Bernoulli percolation process. The probability measure of a configuration ${\displaystyle \omega }$ is given as

${\displaystyle \mu (\omega )=\prod _{e\in E}p^{\omega (e)}(1-p)^{1-\omega (e)}.}$

The RC model is a generalization of percolation, where each cluster is weighted by a factor of ${\displaystyle q}$. Given a configuration ${\displaystyle \omega }$, we let ${\displaystyle C(\omega )}$ be the number of open clusters, or alternatively the number of connected components formed by the open bonds. Then for any ${\displaystyle q>0}$, the probability measure of a configuration ${\displaystyle \omega }$ is given as

${\displaystyle \mu (\omega )={\frac {1}{Z}}q^{C(\omega )}\prod _{e\in E}p^{\omega (e)}(1-p)^{1-\omega (e)}.}$

Z is the partition function, or the sum over the unnormalized weights of all configurations,

${\displaystyle Z=\sum _{\omega \in \Omega }\left\{q^{C(\omega )}\prod _{e\in E(G)}p^{\omega (e)}(1-p)^{1-\omega (e)}\right\}.}$

Note that we can recover the percolation model by setting ${\displaystyle q=1}$, in which case ${\displaystyle Z=1}$.

Edwards-Sokal representation[]

The Edwards-Sokal (ES) representation^[4] of the Potts model is named after Robert G. Edwards and Alan D. Sokal. It allows for a unified representation of the spin model and RC model as a joint distribution of the two. Furthermore, it naturally generalizes the Swensden-Wang (SW) algorithm for arbitrary ferromagnetic spin models.

Let the number of vertices be ${\displaystyle n=|V|}$ and the number of edges be ${\displaystyle m=|E|}$. We denote a spin state as ${\displaystyle \sigma \in \mathbb {Z} _{q}^{n}}$ and a bond configuration as ${\displaystyle \omega \in \{0,1\}^{m}}$. The measure of ${\displaystyle (\sigma ,\omega )}$ is given as

${\displaystyle \mu (\sigma ,\omega )=Z^{-1}\psi (\sigma )\phi _{p}(\omega )1_{A}(\sigma ,\omega ),}$

where ${\displaystyle \psi }$ is the uniform measure, and ${\displaystyle \phi _{p}}$ is the product measure with density ${\displaystyle p=1-e^{-\beta }}$. Furthermore, ${\displaystyle Z}$ is an appropriate normalizing constant, and the indicator function ${\displaystyle 1_{A}}$ enforces the following constraint,

${\displaystyle A=\{(\sigma ,\omega ):\sigma _{i}=\sigma _{j}{\text{ for any edge }}(i,j){\text{ where }}\omega =1\},}$

meaning that a bond can only be open on an edge if the adjacent spins are of the same state, known as the SW rule.

To relate the spin model to the RC model, the following statistical features can be shown:^[2]

• The marginal measure ${\displaystyle \mu (\sigma )}$ of the spins is the Boltzmann measure of the q-state Potts model at inverse temperature ${\displaystyle \beta }$.
• The marginal measure ${\displaystyle \mu (\omega )}$ of the bonds is the random-cluster measure with parameters q and p.
• The conditional measure ${\displaystyle \mu (\sigma \,|\,\omega )}$ of the spin represents a uniformly random assignment of spin states on each connect component.
• The conditional measure ${\displaystyle \mu (\omega \,|\,\sigma )}$ of the bonds represents a percolation process (of ratio p) on edges where adjacent spins are aligned.
• The probability that two vertices ${\displaystyle (i,j)}$ are in the same open cluster is proportional to the two-point correlation function of spins ${\displaystyle \sigma _{i}{\text{ and }}\sigma _{j}}$.^[5]

These features ensure that the spin statistics can be recovered completely from the cluster statistics.

Frustration[]

There are several complications of the ES representation once frustration is present in the spin model. For example, there is no longer a correspondence between the spin statistics and the cluster statistics,^[6] 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.

Relation to other models[]

The random cluster model is equivalent to the q-state Potts model for ${\displaystyle q\in \mathbb {Z} ^{+}}$ (with the ${\displaystyle q=1}$ case being Bernoulli percolation and the ${\displaystyle q=2}$ case being the Ising model). In general, ${\displaystyle q}$ can be any positive real number, with ${\displaystyle q\leq 1}$ favoring the formation of fewer clusters and ${\displaystyle q\geq 1}$ favoring the formation of more clusters (in comparison to percolation). The ${\displaystyle q\to 0}$ limit describes linear resistance networks.^[1]

The partition function of the RC model is a specialization of the Tutte polynomial, which itself is a specialization of the multivariate Tutte polynomial.^[7]

History and applications[]

RC models were introduced in 1969 by Fortuin and Kasteleyn, mainly to solve combinatorial problems.^[1][8][9] After their founders, it is sometimes referred to as FK models.^[3] 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.^[10] Michael Aizenman and coauthors used it to study the phase boundaries in 1D Ising and Potts models.^[11][8]

See also[]

• Tutte polynomial
• Ising model
• Random graph
• Swendsen–Wang algorithm
• FKG inequality

References[]

External links[]

• Random-Cluster Model – Wolfram MathWorld