Percolation theory
Encyclopedia
In mathematics
, percolation theory describes the behavior of connected
clusters in a random graph
. The applications of percolation theory to materials science
and other domains are discussed in the article percolation
.
of the name) is as follows. Assume that some liquid is poured on top of some porous
material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is modelled
mathematically as a three-dimensional network of n × n × n points (or vertices
/sites) the connections (or edge
s/bonds) between each two neighbors may be open (allowing the liquid through) with probability p, or closed with probability 1 – p, and they are assumed to be independent. Therefore, for a given p, what is the probability that an open path exists from the top to the bottom? The behavior for large n is of primary interest. This problem, called now bond-percolation, was introduced in the mathematics literature by , and has been studied intensively by mathematicians and physicists since. When a site is occupied with probability p or empty (its edges are also removed) with probability 1-p, the problem is called "site percolation". The question is the same: for a given p, what is the probability that a path exists between top and bottom? Of course the same questions can be asked for any lattice dimension.
As is quite typical, it is actually easier to examine infinite networks than just large ones. In this case the corresponding question is: does an infinite open cluster exist? That is, is there a path of connected points of infinite length "through" the network? By Kolmogorov's zero-one law
, for any given p, the probability that an infinite cluster exists is either zero or one. Since this probability is an increasing function of p (proof via coupling
argument), there must be a critical p (denoted by pc) below which the probability is always 0 and above which the probability is always 1. In practice, this criticality is very easy to observe. Even for n as small as 100, the probability of an open path from the top to the bottom increases sharply from very close to zero to very close to one in a short span of values of p.
In some cases pc may be calculated explicitly. For example, for the square lattice
Z2 in two dimensions, pc = 1/2, a fact which was an open question for more than 20 years and was finally resolved by Harry Kesten
in the early 1980s, see . A limit case for lattices in many dimensions is given by the Bethe lattice
, whose threshold is at pc = 1/(z − 1) for a coordination number
z. For most infinite lattice graphs, pc cannot be calculated exactly. For example, pc is not known for bond-percolation in hypercubic lattice in two dimensions.
states that the value of pc is connected to the local structure of the graph, while the behavior of clusters below, at, and above pc are invariant with respect to the local structure, and therefore, in some sense are more natural quantities to consider.
This universality also means that for the same dimension independent of the type of the lattice or type of percolation (e.g., bond or site) the fractal dimension
of the clusters at pc is the same.
The dual graph
of the square lattice Z2 is also the square lattice. It follows that, in two dimensions, the supercritical phase is dual to a subcritical percolation process. This provides essentially full information about the supercritical model with d = 2. The main result for the supercritical phase in three and more dimensions is that, for sufficiently large N, there is an infinite open cluster in the two-dimensional slab Z2 × [0, N]d−2. This was proved by .
In two dimensions with p < 1/2, there is with probability one a unique infinite closed cluster. Thus the subcritical phase may be described as finite open islands in an infinite closed ocean. When p > 1/2 just the opposite occurs, with finite closed islands in an infinite open ocean. The picture is more complicated when d ≥ 3 since pc < 1/2, and there is coexistence of infinite open and closed clusters for p between pc and 1 − pc.
at the critical point p = pc believed to be of power-law type. Scaling theory predicts the existence of critical exponents, depending on the number d of dimensions, that determine the class of the singularity. When d = 2 these predictions are backed up by arguments from quantum field theory
and quantum gravitation, and include predicted numerical values for the exponents. Most of these predictions are conjectural except when the number d of dimensions satisfies either d = 2 or d ≥ 19. They include:
See . In dimension ≥ 19, these facts are largely proved using a technique known as the lace expansion. It is believed that a version of the lace expansion should be valid for 7 or more dimensions, perhaps with implications also for the threshold case of 6 dimensions. The connection of percolation to the lace expansion is found in .
In dimension 2, the first fact ("no percolation in the critical phase") is proved for many lattices, using duality. Substantial progress has been made on two-dimensional percolation through the conjecture of Oded Schramm
that the scaling limit
of a large cluster may be described in terms of a Schramm–Loewner evolution. This conjecture was proved by in the special case
of site percolation on the triangular lattice.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, percolation theory describes the behavior of connected
Glossary of graph theory
Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
clusters in a random graph
Random graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
. The applications of percolation theory to materials science
Materials science
Materials science is an interdisciplinary field applying the properties of matter to various areas of science and engineering. This scientific field investigates the relationship between the structure of materials at atomic or molecular scales and their macroscopic properties. It incorporates...
and other domains are discussed in the article percolation
Percolation
In physics, chemistry and materials science, percolation concerns the movement and filtering of fluids through porous materials...
.
Introduction
A representative question (and the sourceEtymology
Etymology is the study of the history of words, their origins, and how their form and meaning have changed over time.For languages with a long written history, etymologists make use of texts in these languages and texts about the languages to gather knowledge about how words were used during...
of the name) is as follows. Assume that some liquid is poured on top of some porous
Porosity
Porosity or void fraction is a measure of the void spaces in a material, and is a fraction of the volume of voids over the total volume, between 0–1, or as a percentage between 0–100%...
material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is modelled
Mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used not only in the natural sciences and engineering disciplines A mathematical model is a...
mathematically as a three-dimensional network of n × n × n points (or vertices
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
/sites) the connections (or edge
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
s/bonds) between each two neighbors may be open (allowing the liquid through) with probability p, or closed with probability 1 – p, and they are assumed to be independent. Therefore, for a given p, what is the probability that an open path exists from the top to the bottom? The behavior for large n is of primary interest. This problem, called now bond-percolation, was introduced in the mathematics literature by , and has been studied intensively by mathematicians and physicists since. When a site is occupied with probability p or empty (its edges are also removed) with probability 1-p, the problem is called "site percolation". The question is the same: for a given p, what is the probability that a path exists between top and bottom? Of course the same questions can be asked for any lattice dimension.
As is quite typical, it is actually easier to examine infinite networks than just large ones. In this case the corresponding question is: does an infinite open cluster exist? That is, is there a path of connected points of infinite length "through" the network? By Kolmogorov's zero-one law
Kolmogorov's zero-one law
In probability theory, Kolmogorov's zero-one law, named in honor of Andrey Nikolaevich Kolmogorov, specifies that a certain type of event, called a tail event, will either almost surely happen or almost surely not happen; that is, the probability of such an event occurring is zero or one.Tail...
, for any given p, the probability that an infinite cluster exists is either zero or one. Since this probability is an increasing function of p (proof via coupling
Coupling (probability)
In probability theory, coupling is a proof technique that allows one to compare two unrelated variables by "forcing" them to be related in some way.-Definition:...
argument), there must be a critical p (denoted by pc) below which the probability is always 0 and above which the probability is always 1. In practice, this criticality is very easy to observe. Even for n as small as 100, the probability of an open path from the top to the bottom increases sharply from very close to zero to very close to one in a short span of values of p.
Square lattice
In mathematics, the square lattice is a type of lattice in a two-dimensional Euclidean space. It is the two-dimensional version of the integer lattice. It is one of the five types of two-dimensional lattices as classified by their symmetry groups; its symmetry group is known symbolically as p4m.Two...
Z2 in two dimensions, pc = 1/2, a fact which was an open question for more than 20 years and was finally resolved by Harry Kesten
Harry Kesten
Harry Kesten is an American mathematician best known for his work in probability, most notably on random walks and percolation theory.- Biography :...
in the early 1980s, see . A limit case for lattices in many dimensions is given by the Bethe lattice
Bethe lattice
A Bethe lattice or Cayley tree , introduced by Hans Bethe in 1935, is a connected cycle-free graph where each node is connected to z neighbours, where z is called the coordination number. It can be seen as a tree-like structure emanating from a central node, with all the nodes arranged in shells...
, whose threshold is at pc = 1/(z − 1) for a coordination number
Coordination number
In chemistry and crystallography, the coordination number of a central atom in a molecule or crystal is the number of its nearest neighbours. This number is determined somewhat differently for molecules and for crystals....
z. For most infinite lattice graphs, pc cannot be calculated exactly. For example, pc is not known for bond-percolation in hypercubic lattice in two dimensions.
Universality
The universality principleUniversality (dynamical systems)
In statistical mechanics, universality is the observation that there are properties for a large class of systems that are independent of the dynamical details of the system. Systems display universality in a scaling limit, when a large number of interacting parts come together...
states that the value of pc is connected to the local structure of the graph, while the behavior of clusters below, at, and above pc are invariant with respect to the local structure, and therefore, in some sense are more natural quantities to consider.
This universality also means that for the same dimension independent of the type of the lattice or type of percolation (e.g., bond or site) the fractal dimension
Fractal dimension
In fractal geometry, the fractal dimension, D, is a statistical quantity that gives an indication of how completely a fractal appears to fill space, as one zooms down to finer and finer scales. There are many specific definitions of fractal dimension. The most important theoretical fractal...
of the clusters at pc is the same.
Subcritical and supercritical
The main fact in the subcritical phase is "exponential decay". That is, when p < pc, the probability that a specific point (for example, the origin) is contained in an open cluster of size r decays to zero exponentially in r. This was proved for percolation in three and more dimensions by and independently by . In two dimensions, it formed part of Kesten's proof that pc = 1/2.The dual graph
Dual graph
In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual...
of the square lattice Z2 is also the square lattice. It follows that, in two dimensions, the supercritical phase is dual to a subcritical percolation process. This provides essentially full information about the supercritical model with d = 2. The main result for the supercritical phase in three and more dimensions is that, for sufficiently large N, there is an infinite open cluster in the two-dimensional slab Z2 × [0, N]d−2. This was proved by .
In two dimensions with p < 1/2, there is with probability one a unique infinite closed cluster. Thus the subcritical phase may be described as finite open islands in an infinite closed ocean. When p > 1/2 just the opposite occurs, with finite closed islands in an infinite open ocean. The picture is more complicated when d ≥ 3 since pc < 1/2, and there is coexistence of infinite open and closed clusters for p between pc and 1 − pc.
Critical
The model has a singularityMathematical singularity
In mathematics, a singularity is in general a point at which a given mathematical object is not defined, or a point of an exceptional set where it fails to be well-behaved in some particular way, such as differentiability...
at the critical point p = pc believed to be of power-law type. Scaling theory predicts the existence of critical exponents, depending on the number d of dimensions, that determine the class of the singularity. When d = 2 these predictions are backed up by arguments from quantum field theory
Quantum field theory
Quantum field theory provides a theoretical framework for constructing quantum mechanical models of systems classically parametrized by an infinite number of dynamical degrees of freedom, that is, fields and many-body systems. It is the natural and quantitative language of particle physics and...
and quantum gravitation, and include predicted numerical values for the exponents. Most of these predictions are conjectural except when the number d of dimensions satisfies either d = 2 or d ≥ 19. They include:
- There are no infinite clusters (open or closed)
- The probability that there is an open path from some fixed point (say the origin) to a distance of r decreases polynomially, i.e. is on the order ofBig O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
r α for some α- α does not depend on the particular lattice chosen, or on other local parameters. It depends only on value of the dimension d (this is an instance of the universalityUniversality (dynamical systems)In statistical mechanics, universality is the observation that there are properties for a large class of systems that are independent of the dynamical details of the system. Systems display universality in a scaling limit, when a large number of interacting parts come together...
principle). - αd decreases from d = 2 until d = 6 and then stays fixed.
- α6 = −1
- α2 = −5/48.
- α does not depend on the particular lattice chosen, or on other local parameters. It depends only on value of the dimension d (this is an instance of the universality
- The shape of a large cluster in two dimensions is conformally invariantConformal mapIn mathematics, a conformal map is a function which preserves angles. In the most common case the function is between domains in the complex plane.More formally, a map,...
.
See . In dimension ≥ 19, these facts are largely proved using a technique known as the lace expansion. It is believed that a version of the lace expansion should be valid for 7 or more dimensions, perhaps with implications also for the threshold case of 6 dimensions. The connection of percolation to the lace expansion is found in .
In dimension 2, the first fact ("no percolation in the critical phase") is proved for many lattices, using duality. Substantial progress has been made on two-dimensional percolation through the conjecture of Oded Schramm
Oded Schramm
Oded Schramm was an Israeli-American mathematician known for the invention of the Schramm–Loewner evolution and for working at the intersection of conformal field theory and probability theory.-Biography:...
that the scaling limit
Scaling limit
In physics or mathematics, the scaling limit is a term applied to the behaviour of a lattice model in the limit of the lattice spacing going to zero. A lattice model which approximates a continuum quantum field theory in the limit as the lattice spacing goes to zero corresponds to finding a second...
of a large cluster may be described in terms of a Schramm–Loewner evolution. This conjecture was proved by in the special case
of site percolation on the triangular lattice.
Different models
- The first model studied was Bernoulli percolation. In this model all bonds are independent. This model is called bond percolation by physicists.
- A generalization next was introduced as the Fortuin–Kasteleyn random cluster model, which has many connections with the Ising modelIsing modelThe Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
and other Potts modelPotts modelIn 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...
s. - Bernoulli (bond) percolation on complete graphComplete graphIn the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
s is an example of a random graphRandom graphIn mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
. The critical probability is p = 1/N. - Directed percolationDirected percolationIn statistical physics Directed Percolation refers to a class of models that mimic filtering of fluids through porous materials along a given direction. Varying the microscopic connectivity of the pores, these models display a phase transition from a macroscopically permeable to an impermeable ...
, which has connections with the contact process. - First passage percolation.
- Invasion percolation.
- Percolation with dependency links was introduced by Parshani et.al.
- Opinion Model
See also
- Critical exponents
- Directed percolationDirected percolationIn statistical physics Directed Percolation refers to a class of models that mimic filtering of fluids through porous materials along a given direction. Varying the microscopic connectivity of the pores, these models display a phase transition from a macroscopically permeable to an impermeable ...
- Erdős–Rényi modelErdos–Rényi modelIn graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
- FractalFractalA fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
- Giant componentGiant componentIn network theory, a giant component is a connected component of a given random graph that contains a constant fraction of the entire graph's vertices....
- Graph TheoryGraph theoryIn mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
- Invasion percolation
- Network theoryNetwork theoryNetwork theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology...
- Optimal path
- Percolation thresholdPercolation thresholdPercolation threshold is a mathematical term related to percolation theory, which is the formation of long-range connectivity in random systems. Below the threshold a giant connected component does not exist while above it, there exists a giant component of the order of system size...
- Percolation critical exponents
- Random media
- Scale-free networkScale-free networkA scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P of nodes in the network having k connections to other nodes goes for large values of k as...
- Shortest path
- UniversalityUniversalityUniversality may refer to:* Universality in physical science * Universality * Universality , meaning present in all places and all times* Universality...