Site percolation

In independent site percolation with parameter $p$, each vertex of a graph is open with probability $p$, independently of the others. Retain those vertices and every original edge whose two endpoints are retained. This gives an induced subgraph, whose connected components of a graph are the percolation clusters. A closed vertex is absent from the usable network, whereas bond percolation keeps all vertices and instead removes individual edges.

A specified simple graph path of $m$ edges has $m+1$ distinct vertices. Its probability of being entirely open is therefore $p^{m+1}$, including the starting vertex. Conditional on that vertex being open, it is $p^m$ by independence. For a two-edge graph path at $p=1/2$, the unconditional probability is $1/8$, compared with $1/4$ in bond percolation. This comparison concerns a fixed route; percolation critical probabilities require analysis of all possible routes on the specified infinite graph.

For independent site percolation on the triangular lattice, the critical probability is $p_c=1/2$. Self-duality, crossing estimates, and exclusion of an infinite critical cluster identify the threshold.

Conditioned on the sites revealed by an exploration interface, every unrevealed site retains its independent Bernoulli law. The explored boundary supplies boundary conditions for subsequent crossing events.

Dependent percolation allows the open states of different vertices or edges to be statistically dependent.

A bond percolation law is one-independent if the bond states in any two sets with disjoint endpoint sets are independent as collections. In particular, states of bonds in a matching in a graph are mutually independent. The law need not be invariant under translations or positively associated.

Place side-$2n$ square lattice boxes around the points $3nv$, $v\in {\mathbb{Z}}^2$. The width-$2n$ rectangle joining adjacent boxes has length $5n$. Declare a coarse bond open when its long rectangle is crossed and each endpoint box is crossed in the transverse direction. Nonincident coarse bonds use disjoint fine-bond sets, while incident good bonds give connected open paths inside their common endpoint box. When fixed-aspect crossing probabilities tend to one, these coarse bond probabilities tend to one. The Peierls circuit bound for one-independent percolation then yields an infinite fine-lattice open cluster.

If each bond has closed probability at most $q$ in one-independent bond percolation on the square lattice, a set of $\ell$ bonds contains a matching in a graph of size at least $\ell /4$: divide horizontal bonds by the parity of their left endpoint and vertical bonds by the parity of their lower endpoint. Each of the four classes is a matching. Mutual independence in the largest class proves the circuit bound. There are at most $4\ell 3^{\ell }$ dual circuits of length $\ell$ surrounding the origin. For sufficiently small $q$, the sum of these circuit probabilities is less than one, so the origin has a positive chance of belonging to an infinite percolation cluster.

Color the vertices of a periodic graph independently red or blue with equal probabilities, and declare a vertex of its line graph open exactly when the corresponding edge has equal-colored endpoints. The resulting site percolation has marginal $1/2$ and is a finite-range dependent random field: sets at line-graph distance greater than one use disjoint color inputs. Red and blue open clusters cannot join. If the original graph has an infinite red component and an infinite blue component, its line graph consequently has at least two infinite percolation clusters. One explicit amenable graph with that property is obtained by replacing each square-lattice vertex by a complete graph on ten vertices, joining neighboring blocks completely. Blocks containing both colors have independent probability $511/512$; a Peierls argument proves that they percolate, and their infinite cluster carries both a red and a blue component. Thus finite-range dependence, even with all site marginals nondegenerate, does not substitute for finite energy in percolation uniqueness.

On a finite graph, the random-cluster model assigns an edge configuration $\omega$ probability proportional towhere $o,c,k$ count open edges, closed edges, and open connected components.

For $q\ge 1$, the random-cluster measure lies between the two Bernoulli product measures displayed above. The upper Holley condition ratio is $q^{k(\omega \wedge \eta )-k(\eta )}\ge 1$. The lower ratio is $q^{k(\omega \vee \eta )-k(\omega )+|\eta \setminus \omega |}\ge 1$, because adding an edge reduces the component count by at most one. The comparisons persist under wired limits and give $p_c(1)\le p_c(q)\le q{p}_c(1)/(1+(q-1)p_c(1))$.

The multiplicative factor $q$ assigned to each connected component of a graph in a finite random-cluster measure. At fixed edge probability, the weight of a configuration with $k$ components includes $q^k$. For $q=1$ this reduces to independent bond percolation; increasing $q$ at fixed $p$, for $q\ge 1$, suppresses increasing events by random-cluster weight monotonicity.

The threshold for the origin to have an infinite percolation cluster under a consistently chosen infinite-volume random-cluster measure, conventionally the wired measure: $p_c(q)=\inf \{p:{\theta }^{\mathrm{w}}(p,q)>0\}$. The definition alone makes no assertion about percolation exactly at the threshold.

The finite-volume random-cluster weight monotonicity passes to consistently wired or free infinite-volume measures for finite increasing connection events. Decreasing these events to origin-to-infinity connectivity yields $\theta (p,q_1)\ge \theta (p,q_2)$ for $q_1\le q_2$. The corresponding supercritical parameter sets are nested, and hence $p_c(q_1)\le p_c(q_2)$.

For fixed $p\in (0,1)$ and $1\le q_1\le q_2$, the random-cluster measure at $q_1$ stochastically dominates that at $q_2$. In Holley's condition, Bernoulli factors cancel. Put $a=k(S)-k(S\cup T)$ and $b=k(S\cap T)-k(T)$; supermodularity of graph component count gives $b\ge a\ge 0$, and the weight ratio is $(q_2/q_1{)}^a{q}_2^{b-a}\ge 1$. The comparison also holds with the same boundary wiring in both measures.

Planar random-cluster duality relates edge odds by $[p/(1-p)][p^{\ast }/(1-p^{\ast })]=q$. The fixed point $p=p^{\ast }$ has odds $\sqrt{q}$, giving the displayed parameter. A self-dual parameter does not by itself establish a critical threshold on an arbitrary planar graph. At this parameter the symmetric cluster weight at the self-dual parameter makes the primal-dual cluster counts explicit.

The planar cluster-count identity rewrites $o(\omega )+2k(\omega )$ as $|V|-1+k(\omega )+k({\bar{\omega }}^{\ast })$. At the self-dual parameter of the random-cluster model, $p/(1-p)=\sqrt{q}$, so its weight is $(\sqrt{q}{)}^{o(\omega )+2k(\omega )}$ up to a configuration-independent factor. Absorbing $(\sqrt{q}{)}^{|V|-1}$ into normalization proves the symmetric weight, with the unbounded dual face counted.

For an edge with endpoints already connected without that edge, including any boundary wiring, the conditional open probability is $p$. Otherwise opening the edge merges two components, so the conditional probability is $p/(p+q(1-p))$. For $q\ge 1$, this conditional probability increases when more other edges are open or more boundary vertices are identified. This is the local mechanism of boundary monotonicity of the random-cluster measure.

A boundary condition for a finite-box random-cluster measure is a partition of the boundary vertices. All vertices in one block are identified before counting open components; the identifications carry no Bernoulli edge factors. The weight is $p^{o(\omega )}(1-p{)}^{|E|-o(\omega )}{q}^{k_{\xi }(\omega )}$. A coarser partition makes more identifications. General partitions need not have a planar realization.

Here $\xi ⪯\zeta$ means each block of $\xi$ lies in a block of $\zeta$, and the measure order is stochastic domination of probability measures. The random-cluster single-edge conditional probability is increasing in both exterior open edges and wiring for $q\ge 1$. Couple two heat-bath Markov chains by identical update edges and uniform random variables, starting from ordered states. Order persists, and convergence of the finite chains to their stationary laws proves the displayed inequality. At $q=1$, the law does not depend on the boundary partition.

All boundary vertices are identified into one vertex for component counting. This is the most wired random-cluster boundary condition on a fixed boundary, and maximizes increasing-event probabilities when $q\ge 1$ by boundary monotonicity of the random-cluster measure.

For $q\ge 1$, finite random-cluster measures with all boundary graph vertices identified have a weak infinite-volume limit of a sequence. On a regular lattice it is invariant under translations and lattice reflections and has positive association of the random-cluster model. Its conditional single-edge open probability lies between $p/(p+q(1-p))$ and $p$. Connection events can be approximated by increasing finite-volume path events, so their positive-association inequalities pass to the limit of a sequence.

Positive association of random variables and translation invariance give $C_{m+n}\ge C_m{C}_n$ for axis connection probabilities. The Fekete lemma applied to $-\log C_n$ proves the displayed limit of a sequence and the bound $C_n\le e^{-n\alpha }$. The lower single-edge conditional bound gives $C_n\ge [p/(p+q(1-p)){]}^n$, so the decay rate is finite and nonnegative. It may be zero.

Choose a graph vertex $x=(n,x_2,\dots ,x_d)$ on the boundary of a lattice box. Translation and reflection invariance identify the probabilities of $0\leftrightarrow x$ and $x\leftrightarrow 2n{e}_1$. Their intersection implies $0\leftrightarrow 2n{e}_1$, so positive association of random variables gives $C_{2n}\ge \varphi (0\leftrightarrow x{)}^2$. A union bound and lattice symmetries choose such an $x$ with probability at least the box-boundary connection probability divided by the number of boundary graph vertices. This polynomial factor disappears in the exponential rate, identifying boundary and axial inverse correlation lengths.

The boundary partition has singleton blocks, so no different boundary vertices are identified. Open component counting is the ordinary counting in the finite graph, including isolated vertices. This is the least wired random-cluster boundary condition.

For $0\le p\le 1$ and $q\ge 1$, the FKG inequality implies that increasing functions of a random-cluster configuration have nonnegative covariance. The conclusion can fail for $0<q<1$.

On a finite connected graph, fixing $p=1/2$ and sending $q\downarrow 0$ makes the random-cluster model converge to the uniform law on connected spanning subgraphs: the factor $q^{k(\omega )}$ selects the minimum possible component count $k=1$, while all surviving configurations have equal remaining weight.

If $p,q\downarrow 0$ with $q/p\to 0$, the random-cluster model on a finite connected graph converges to the uniform spanning tree. Relative to a tree, an acyclic configuration with $k>1$ components pays a factor $(q/p{)}^{k-1}$, while every additional cycle pays a factor asymptotic to $p$.

The Edwards-Sokal coupling assigns one common random spin to every random-cluster component. For $q=2$ it couples the random-cluster model to the Ising model.

Given a random-cluster configuration, its components receive independent uniform colors under the Edwards-Sokal coupling. Two vertices have equal Potts spins with probability $1$ if connected and $1/q$ otherwise. Averaging proves the identity. With a wired component fixed to color $1$, the same argument gives normalized spontaneous magnetization $(q{\pi }^1({\sigma }_0=1)-1)/(q-1)={\varphi }^{\mathrm{w}}(0\leftrightarrow \infty )$ in infinite volume. Thus its onset is the wired random-cluster critical probability, transformed to ${\beta }_c=-\log (1-p_c)$ in this convention.

A heat-bath Markov chain repeatedly chooses one coordinate and redraws it from its conditional distribution given all other coordinates. The target distribution is reversible and stationary for these updates.

For a random field $(Y_x)$, level-set percolation studies the random vertex set $\{x:Y_x\ge a\}$ as the threshold $a$ varies.

The critical threshold is the boundary between levels at which an unbounded superlevel component can occur and levels at which every superlevel component is almost surely finite.

A random field is finite-range dependent if collections indexed by sets farther apart than a fixed distance are independent. Sparse subsets of long paths then restore enough independence for path-counting arguments.