Random cluster model

Last updated

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. [1] [2] It is also referred to as the RC model or sometimes the FK representation after its founders Cees Fortuin and Piet Kasteleyn. [3] The random cluster model has a critical limit, described by a conformal field theory.

Contents

Definition

Let be a graph, and 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 if , and open if . If we let be the set of open bonds, then an open cluster or FK cluster is any connected component in 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 and closed otherwise, then this is just the standard Bernoulli percolation process. The probability measure of a configuration is given as

The RC model is a generalization of percolation, where each cluster is weighted by a factor of . Given a configuration , we let be the number of open clusters, or alternatively the number of connected components formed by the open bonds. Then for any , the probability measure of a configuration is given as

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

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

Special values of q

The parameter of the random cluster model can take arbitrary complex values. This includes the following special cases:

Edwards-Sokal representation

The Edwards-Sokal (ES) representation [5] 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 be a graph, with the number of vertices being and the number of edges being . We denote a spin configuration as and a bond configuration as . The joint measure of is given as

where is the uniform measure, is the product measure with density , and is an appropriate normalizing constant. Importantly, the indicator function of the set

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: [2]

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, [7] 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 is a planar graph, there is a duality between the random cluster models on and on the dual graph . [8] At the level of the partition function, the duality reads

On a self-dual graph such as the square lattice, a phase transition can only occur at the self-dual coupling . [9]

The random cluster model on a planar graph can be reformulated as a loop model on the corresponding medial graph. For a configuration 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 . 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

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 and , corresponding to the fractal dimensions and of the clusters.

History and applications

RC models were introduced in 1969 by Fortuin and Kasteleyn, mainly to solve combinatorial problems. [1] [10] [6] 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. [11] Michael Aizenman and coauthors used it to study the phase boundaries in 1D Ising and Potts models. [12] [10]

See also

Related Research Articles

<span class="mw-page-title-main">Lattice model (physics)</span>

In mathematical physics, a lattice model is a mathematical model of a physical system that is defined on a lattice, as opposed to a continuum, such as the continuum of space or spacetime. Lattice models originally occurred in the context of condensed matter physics, where the atoms of a crystal automatically form a lattice. Currently, lattice models are quite popular in theoretical physics, for many reasons. Some models are exactly solvable, and thus offer insight into physics beyond what can be learned from perturbation theory. Lattice models are also ideal for study by the methods of computational physics, as the discretization of any continuum model automatically turns it into a lattice model. The exact solution to many of these models includes the presence of solitons. Techniques for solving these include the inverse scattering transform and the method of Lax pairs, the Yang–Baxter equation and quantum groups. The solution of these models has given insights into the nature of phase transitions, magnetization and scaling behaviour, as well as insights into the nature of quantum field theory. Physical lattice models frequently occur as an approximation to a continuum theory, either to give an ultraviolet cutoff to the theory to prevent divergences or to perform numerical computations. An example of a continuum theory that is widely studied by lattice models is the QCD lattice model, a discretization of quantum chromodynamics. However, digital physics considers nature fundamentally discrete at the Planck scale, which imposes upper limit to the density of information, aka Holographic principle. More generally, lattice gauge theory and lattice field theory are areas of study. Lattice models are also used to simulate the structure and dynamics of polymers.

The Ising model, named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent magnetic dipole moments of atomic "spins" that can be in one of two states. The spins are arranged in a graph, usually a lattice, allowing each spin to interact with its neighbors. Neighboring spins that agree have a lower energy than those that disagree; the system tends to the lowest energy but heat disturbs this tendency, thus creating the possibility of different structural phases. The model allows the identification of phase transitions as a simplified model of reality. The two-dimensional square-lattice Ising model is one of the simplest statistical models to show a phase transition.

In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. By studying the Potts model, one may gain insight into the behaviour of ferromagnets and certain other phenomena of solid-state physics. The strength of the Potts model is not so much that it models these physical systems well; it is rather that the one-dimensional case is exactly solvable, and that it has a rich mathematical formulation that has been studied extensively.

In physics and mathematics, the Gibbs measure, named after Josiah Willard Gibbs, is a probability measure frequently seen in many problems of probability theory and statistical mechanics. It is a generalization of the canonical ensemble to infinite systems. The canonical ensemble gives the probability of the system X being in state x as

<span class="mw-page-title-main">Tutte polynomial</span> Algebraic encoding of graph connectivity

The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph and contains information about how the graph is connected. It is denoted by .

The quantum Heisenberg model, developed by Werner Heisenberg, is a statistical mechanical model used in the study of critical points and phase transitions of magnetic systems, in which the spins of the magnetic systems are treated quantum mechanically. It is related to the prototypical Ising model, where at each site of a lattice, a spin represents a microscopic magnetic dipole to which the magnetic moment is either up or down. Except the coupling between magnetic dipole moments, there is also a multipolar version of Heisenberg model called the multipolar exchange interaction.

In statistical mechanics, the two-dimensional square lattice Ising model is a simple lattice model of interacting magnetic spins. The model is notable for having nontrivial interactions, yet having an analytical solution. The model was solved by Lars Onsager for the special case that the external magnetic field H = 0. An analytical solution for the general case for has yet to be found.

The spherical model is a model of ferromagnetism similar to the Ising model, which was solved in 1952 by T. H. Berlin and M. Kac. It has the remarkable property that for linear dimension d greater than four, the critical exponents that govern the behaviour of the system near the critical point are independent of d and the geometry of the system. It is one of the few models of ferromagnetism that can be solved exactly in the presence of an external field.

Monte Carlo in statistical physics refers to the application of the Monte Carlo method to problems in statistical physics, or statistical mechanics.

In mathematics, the Fortuin–Kasteleyn–Ginibre (FKG) inequality is a correlation inequality, a fundamental tool in statistical mechanics and probabilistic combinatorics, due to Cees M. Fortuin, Pieter W. Kasteleyn, and Jean Ginibre. Informally, it says that in many random systems, increasing events are positively correlated, while an increasing and a decreasing event are negatively correlated. It was obtained by studying the random cluster model.

The Swendsen–Wang algorithm is the first non-local or cluster algorithm for Monte Carlo simulation for large systems near criticality. It has been introduced by Robert Swendsen and Jian-Sheng Wang in 1987 at Carnegie Mellon.

The Wolff algorithm, named after Ulli Wolff, is an algorithm for Monte Carlo simulation of the Ising model and Potts model in which the unit to be flipped is not a single spin but a cluster of them. This cluster is defined as the set of connected spins sharing the same spin states, based on the Fortuin-Kasteleyn representation.

In the context of the physical and mathematical theory of percolation, a percolation transition is characterized by a set of universal critical exponents, which describe the fractal properties of the percolating medium at large scales and sufficiently close to the transition. The exponents are universal in the sense that they only depend on the type of percolation model and on the space dimension. They are expected to not depend on microscopic details such as the lattice structure, or whether site or bond percolation is considered. This article deals with the critical exponents of random percolation.

Dynamical mean-field theory (DMFT) is a method to determine the electronic structure of strongly correlated materials. In such materials, the approximation of independent electrons, which is used in density functional theory and usual band structure calculations, breaks down. Dynamical mean-field theory, a non-perturbative treatment of local interactions between electrons, bridges the gap between the nearly free electron gas limit and the atomic limit of condensed-matter physics.

Conductivity near the percolation threshold in physics, occurs in a mixture between a dielectric and a metallic component. The conductivity and the dielectric constant of this mixture show a critical behavior if the fraction of the metallic component reaches the percolation threshold.

The model is a simplified statistical mechanical spin model. It is a generalization of the Ising model. Although it can be defined on an arbitrary graph, it is integrable only on one and two-dimensional lattices, in several special cases.

The two-dimensional critical Ising model is the critical limit of the Ising model in two dimensions. It is a two-dimensional conformal field theory whose symmetry algebra is the Virasoro algebra with the central charge . Correlation functions of the spin and energy operators are described by the minimal model. While the minimal model has been exactly solved, see also, e.g., the article on Ising critical exponents, the solution does not cover other observables such as connectivities of clusters.

The three-state Potts CFT, also known as the parafermion CFT, is a conformal field theory in two dimensions. It is a minimal model with central charge . It is considered to be the simplest minimal model with a non-diagonal partition function in Virasoro characters, as well as the simplest non-trivial CFT with the W-algebra as a symmetry.

Replica cluster move in condensed matter physics refers to a family of non-local cluster algorithms used to simulate spin glasses. It is an extension of the Swendsen-Wang algorithm in that it generates non-trivial spin clusters informed by the interaction states on two replicas instead of just one. It is different from the replica exchange method, as it performs a non-local update on a fraction of the sites between the two replicas at the same temperature, while parallel tempering directly exchanges all the spins between two replicas at different temperature. However, the two are often used alongside to achieve state-of-the-art efficiency in simulating spin-glass models.

The Typical Medium Dynamical Cluster Approximation (TMDCA) is a non-perturbative approach designed to model and obtain the electronic ground state of strongly correlated many-body systems. It addresses critical aspects of mean-field treatments of strongly correlated systems systems, such as the lack of an intrinsic order parameter to characterize quantum phase transitions and the description of spatial dependent features. Additionally, the TMDCA tackles the challenge of accurately modeling strongly correlated systems when imperfections disrupt the fundamental assumptions of band theory, as seen in density functional theory, such as the independent particle approximation and material homogeneity.

References

  1. 1 2 3 Fortuin; Kasteleyn (1972). "On the random-cluster model: I. Introduction and relation to other models". Physica. 57 (4): 536. Bibcode:1972Phy....57..536F. doi:10.1016/0031-8914(72)90045-6.
  2. 1 2 Grimmett (2002). "Random cluster models". arXiv: math/0205237 .
  3. 1 2 Newman, Charles M. (1994), Grimmett, Geoffrey (ed.), "Disordered Ising Systems and Random Cluster Representations", Probability and Phase Transition, NATO ASI Series, Dordrecht: Springer Netherlands, pp. 247–260, doi:10.1007/978-94-015-8326-8_15, ISBN   978-94-015-8326-8 , retrieved 2021-04-18
  4. Sokal, Alan (2005). "The multivariate Tutte polynomial (Alias Potts model) for graphs and matroids". Surveys in Combinatorics 2005. pp. 173–226. arXiv: math/0503607 . doi:10.1017/CBO9780511734885.009. ISBN   9780521615235. S2CID   17904893.
  5. Edwards, Robert G.; Sokal, Alan D. (1988-09-15). "Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm". Physical Review D. 38 (6): 2009–2012. Bibcode:1988PhRvD..38.2009E. doi:10.1103/PhysRevD.38.2009. PMID   9959355.
  6. 1 2 Kasteleyn, P. W.; Fortuin, C. M. (1969). "Phase Transitions in Lattice Systems with Random Local Properties". Physical Society of Japan Journal Supplement. 26: 11. Bibcode:1969JPSJS..26...11K.
  7. Cataudella, V.; Franzese, G.; Nicodemi, M.; Scala, A.; Coniglio, A. (1994-03-07). "Critical clusters and efficient dynamics for frustrated spin models". Physical Review Letters. 72 (10): 1541–1544. Bibcode:1994PhRvL..72.1541C. doi:10.1103/PhysRevLett.72.1541. hdl: 2445/13250 . PMID   10055635.
  8. Wu, F. Y. (1982-01-01). "The Potts model". Reviews of Modern Physics. 54 (1). American Physical Society (APS): 235–268. Bibcode:1982RvMP...54..235W. doi:10.1103/revmodphys.54.235. ISSN   0034-6861.
  9. Beffara, Vincent; Duminil-Copin, Hugo (2013-11-27). "The self-dual point of the two-dimensional random-cluster model is critical for $q\geq 1$". arXiv: 1006.5073 [math.PR].
  10. 1 2 Grimmett. The random cluster model (PDF).
  11. Swendsen, Robert H.; Wang, Jian-Sheng (1987-01-12). "Nonuniversal critical dynamics in Monte Carlo simulations". Physical Review Letters. 58 (2): 86–88. Bibcode:1987PhRvL..58...86S. doi:10.1103/PhysRevLett.58.86. PMID   10034599.
  12. Aizenman, M.; Chayes, J. T.; Chayes, L.; Newman, C. M. (April 1987). "The phase boundary in dilute and random Ising and Potts ferromagnets". Journal of Physics A: Mathematical and General. 20 (5): L313–L318. Bibcode:1987JPhA...20L.313A. doi:10.1088/0305-4470/20/5/010. ISSN   0305-4470.