Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 28 (Percolation and Related Topics)

Give each nearest-neighbor edge of the cubic lattice an independent Bernoulli distribution state, open with probability $p$. The resulting product measure is denoted ${\mathbb{P}}_p$. In this bond percolation model, $C(0)$ is the percolation cluster of the origin, andThe uniform-label monotone coupling of Bernoulli percolation shows that ${\theta }_d$ is increasing.

Let $c_n(d)$ count $n$-step self-avoiding walks starting at the origin, with $c_0(d)=1$. Splitting a walk after $n$ steps, and discarding the avoidance constraint between the two pieces, gives $c_{n+m}(d)\le c_n(d)c_m(d)$. The Fekete lemma therefore gives the connective constantThe locally finite graph structure means that an infinite percolation cluster at the origin supplies an open self-avoiding walk of every length. Each specified walk has $n$ distinct edges and is open with probability $p^n$. The union bound givesFor $p\mu (d)<1$ the right side tends to zero. Hence the connective-constant lower bound for percolation is $p_c(d)\ge \mu (d{)}^{-1}$.

For the upper bound first work on the square lattice. A finite open percolation cluster has an outer boundary containing a simple closed graph cycle of dual edges, all crossing closed primal edges. Such a dual bond percolation circuit separates that cluster from infinity. Write $N_{\ell }$ for the number of simple dual circuits of length $\ell$ surrounding the origin. Each circuit meets the positive horizontal ray at distance at most $\ell$: its bounding box contains the origin and its diameter is bounded by its length. Choose such an intersection as an anchor and orient the circuit. Removing its last edge leaves a rooted self-avoiding walk of length $\ell -1$ in the translated square lattice. Consequently, for an absolute constant $K$,The exact constant and this possible overcount do not matter. If $(1-p)\mu (2)<1$, the root test givesA summable circuit count alone need not give a total sum below one. To use its tail correctly, let $B_R=[-R,R{]}^2\cap {\mathbb{Z}}^2$ and condition every edge internal to $B_R$ to be open. This finite event has positive probability. A closed dual circuit surrounding all of $B_R$ crosses no internal edge of $B_R$, and so its closed-edge probability remains $(1-p{)}^{\ell }$ under this conditioning. Its length tends to infinity with $R$. Choose $R$ so large that the union bound for all such circuits is below one. With positive conditional probability, none occurs.

On that event, $C(0)$ contains $B_R$ and cannot be finite: a finite cluster containing $B_R$ would have an enclosing closed dual circuit. Thus ${\theta }_2(p)>0$ whenever $p>1-\mu (2{)}^{-1}$. This is the connective-constant Peierls bound, proved by excluding short circuits through the open-box conditioning. An embedded coordinate plane in the cubic lattice has exactly the same bond percolation law as the square lattice, so $p_c(d)\le p_c(2)$. Together,There are $2d$ choices for the first step of a self-avoiding walk and at most $2d-1$ thereafter, because immediate reversal is forbidden. Hence $c_n(d)\le 2d(2d-1{)}^{n-1}$ and $\mu (d)\le 2d-1$. In particular $\mu (2)\le 3$. Substituting with the correct directions of the inequalities gives

Use the coordinatewise partial order: $\omega \le \eta$ means $\omega (e)\le \eta (e)$ for every $e\in E$. An increasing event $A$ is upward closed: $\omega \in A$ and $\omega \le \eta$ imply $\eta \in A$.

Under the independent Bernoulli distribution product measure ${\mathbb{P}}_p$ on these coordinates, the Harris-FKG inequality statesfor increasing events $A,B$. For $K\subseteq E$, let $[\omega {]}_K$ be the cylinder of configurations agreeing with $\omega$ on $K$. The disjoint occurrence of increasing events $A\square B$ consists of configurations for which there exist disjoint $K,L$ with $[\omega {]}_K\subseteq A$ and $[\omega {]}_L\subseteq B$. For increasing events, witnesses can be taken to prescribe only open coordinates. The BK inequality isPositive association rewards simultaneous occurrence; the disjoint-witness requirement in the BK inequality gives a bound in the opposite direction. The inequalities also apply to different independent Bernoulli parameters in different coordinates.

Regard the boxes as sets of lattice graph vertices. Write ${\tau }_p(x,y)={\mathbb{P}}_p(x\leftrightarrow y)$, and put $g_0=1$. On the event defining $g_n$, choose an open self-avoiding walk from the origin to its first visit to $\partial {\Lambda }_n$. Let $y$ be its first visit to $\partial {\Lambda }_m$. Its initial segment witnesses $0\leftrightarrow y$. Its remaining segment ends at a point $z$ withFor $m<n$, truncate this remaining segment on its first visit to $y+\partial {\Lambda }_{n-m}$. The two segments use disjoint edges, so they are disjoint witnesses. For $m=n$, the second event is the sure event with empty witness. Thus the union bound, the BK inequality and translation invariance giveAn unrestricted connection event can depend on infinitely many edges. Apply the finite-coordinate BK inequality first to connections confined to growing boxes and take increasing limits; each occurrence has a finite path witness. This justifies its use here. The estimate is the weighted BK boundary-splitting estimate.

By summing cluster indicators and using Tonelli theorem, the percolation susceptibility isIf $\chi (p)<\infty$, then $S_m\to 0$. At $p=0$ all $g_k$ vanish, so any positive exponential rate works. Otherwise choose $m\ge 1$ with $a=S_m\in (0,1)$. Iterating the weighted BK boundary-splitting estimate gives, for $k=jm+r$ with $0\le r<m$,For $k\ge m$, $\lfloor k/m\rfloor \ge k/(2m)$, so $g_k\le \exp [-(-\log a)k/(2m)]$. To include the finitely many smaller indices without a prefactor, note that $p<1$ under finite susceptibility andTherefore one may takeFor $k<m$ this follows from $\mu (p)k\le -\log g_1$, and for $k\ge m$ it follows from the iterated estimate. This proves exponential one-arm decay from finite susceptibility with exactly the requested unit prefactor.

The purpose of the RSW lemma is to turn local crossing information into control at every fixed shape and scale. Work with independent bond percolation on the square lattice. Let $H(a,b)$ be the event of an open left-to-right graph path in $[0,a]\times [0,b]\cap {\mathbb{Z}}^2$, and write $h_p(a,b)={\mathbb{P}}_p(H(a,b))$.

A useful precise uniform version of the RSW lemma is the following uniform RSW crossing estimate. If for a fixed parameter $p$ and some $\delta >0$,then for every fixed aspect ratio $\rho >1$ there is $c(\delta ,\rho )>0$, independent of $n$, such thatIn particular this bounds length $2n$ in terms of the uniform square bound at length $n$. The constants need not be sharp. The hypotheses used in the proof are planarity, translation and reflection symmetries, the Harris-FKG inequality and independence of unexplored edges. At a self-dual parameter the same argument for dual crossings gives an upper bound strictly below one as well. Neither an exact value of $p_c$ nor the existence of an infinite cluster is an assumption of this estimate.

Here is the gluing picture behind the RSW lemma. For increasing crossing or attachment events, the Harris-FKG inequality provides a lower bound on their joint probability. If an event of probability at least $\delta$ is a union of two reflection-related increasing alternatives $A_1,A_2$, the square-root trick for positively associated events givesIndeed their decreasing complements are positively associated too, so ${\mathbb{P}}_p(A_1^c\cap A_2^c)\ge {\mathbb{P}}_p(A_1^c{)}^2$. This prevents a square crossing from concentrating all its useful attachment locations on just one side.

The nontrivial first gluing step enlarges a square to aspect ratio $3/2$. Explore an extremal square crossing, revealing the edges on the explored side but leaving its other side unexamined. In that unexplored region the conditional law is still independent bond percolation. Compare possible attachments to the crossing with their reflected alternatives. Reflection symmetry and the preceding square-root estimate give a positive bound, depending only on $\delta$, for the required attachment after averaging over the explored crossing. Carry out the reflected construction at the other end and use the Harris-FKG inequality to combine the increasing attachment events with the original crossing. Planarity ensures that the relevant transverse paths actually meet. This RSW reflection extension lemma yields a lower bound $u(\delta )>0$ for the $3n/2$-by-$n$ crossing. The exploration is important: a reflection compares the laws of fresh configurations; reflecting the picture of an open path does not make the reflected edges open.

From that first extension, longer rectangles are obtained by a genuinely transverse gluing. Two $3n/2$-by-$n$ rectangles shifted by $n/2$ overlap in an $n$-by-$n$ square. Require a horizontal crossing in each long rectangle and a vertical crossing of the overlap square. Each horizontal crossing crosses that overlap from left to right, and therefore meets its vertical crossing. Their union crosses the $2n$-by-$n$ rectangle. The Harris-FKG inequality gives a lower bound $u(\delta {)}^2\delta$. Repeat a bounded number of times for any fixed $\rho$. Integer rounding uses neighboring lattice rectangles and bounded additional gluing steps; finitely many smallest scales can be absorbed into the constant. The constants deteriorate with $\rho$ but not with $n$. Merely requiring horizontal crossings in adjacent squares would not suffice, since their endpoints need not coincide; the overlap crossing solves that problem.

I apply the RSW lemma to the exact threshold for bond percolation on the square lattice. The planar duality for rectangle crossings says that an open horizontal crossing and a closed dual vertical crossing are complementary. At $p=1/2$, the dual edge states have the same law as the primal ones. For the balanced lattice rectangle with side lengths $n+1,n$, the rotated dual crossing rectangle has those same side lengths: its transverse lengths before rotation are $n,n+1$. Thus the exact self-dual rectangle crossing probability is $1/2$. Restricting a crossing of this rectangle to its first visit to the shorter vertical side givesThe one-unit balance avoids assuming an exact one-half probability for every finite vertex-square convention. The RSW lemma now gives scale-independent positive bounds for all fixed-aspect-ratio primal and closed dual rectangle crossings.

Arrange four appropriately overlapping long rectangles around a square ring. Closed dual crossings along the four sides, with transverse overlap crossings if needed, join to a closed dual graph cycle surrounding the inner square. The Harris-FKG inequality, applied to the closed dual states, and the RSW lemma give a constant $b>0$ for this circuit event, uniformly over ring size. Choose disjoint rings with radii increasing, for example, by a factor of four. Their circuit events depend on disjoint edge sets, so they are independent. An open graph path from the origin to infinity would have to avoid every one of these dual barriers. Its probability is at most $(1-b{)}^j$ after $j$ rings and therefore zero. HenceThis is the independent annular barriers for percolation argument. It is worth separating it from the other inequality: the absence of an infinite cluster at one parameter alone does not prove that every larger parameter percolates.

For the reverse inequality use sharpness of the percolation transition: below $p_c$, independent bond percolation on the cubic lattice has exponentially decaying connection probabilities. One can see why this is the relevant general ingredient through the finite-set criterion for percolation sharpness. For a finite set $S$ containing the origin putIf ${\phi }_p(S)<1$, split a long open self-avoiding walk at its first exit from $S$. Its internal connection, exit edge and subsequent connection have disjoint witnesses. The BK inequality gives a contraction by ${\phi }_p(S)$ each time distance decreases by the diameter of $S$ plus a fixed step. Iteration proves exponential decay of subcritical percolation at such $p$.

To identify this finite-set threshold with $p_c$, the Margulis–Russo formula expresses the derivative of $g_n(p)$ as the sum of pivotal-edge probabilities. Explore the cluster attached to the box boundary, and let $S$ be its complement. On failure of the origin-to-boundary event, $0\in S$; all edges from $S$ to the boundary cluster are closed, while the internal edges of $S$ remain fresh. A boundary edge is pivotal precisely when its endpoint in $S$ is connected to the origin inside $S$. Removing the factor $1-p$ for a closed pivotal edge yields the general differential inequalityFor $p>{\tilde{p}}_c$ every finite-set quantity on the right is at least one. Integrating from any $p_0\in ({\tilde{p}}_c,p)$ gives a positive lower bound for $g_n(p)$ independent of $n$, and taking $n\to \infty$ gives $\theta (p)>0$. Combined with the contraction below ${\tilde{p}}_c$, this proves $p_c={\tilde{p}}_c$ and the stated sharpness conclusion. This outline supplies the extra threshold argument rather than assuming the desired critical value.

If $p_c(2)>1/2$, sharpness would give $g_n(1/2)\le C{e}^{-cn}$. But a square crossing starting somewhere on the left side entails an open connection from that starting graph vertex to distance $n$. A union bound over the $n+1$ possible starting graph vertices givescontradicting exponential decay. Therefore $p_c(2)\le 1/2$, and the two directions establishThis is the Harris-Kesten theorem. The overall mechanism is that self-duality supplies a square crossing, the RSW lemma transports it between shapes and creates barriers at every scale, and sharpness converts the finite-scale crossing information into the exact threshold.

For a finite graph $G=(V,E)$, let $o(\omega )={\sum }_{e\in E}\omega (e)$, and let $k_G(\omega )$ count connected components of the spanning open subgraph, including isolated graph vertices. The random-cluster model with $p\in [0,1]$ and $q>0$ isThe partition function $Z_{G,p,q}$ is the sum of these weights over all configurations, making the expression a probability measure.

For the lattice box, take all nearest-neighbor edges with both endpoints in ${\Lambda }_n$. A random-cluster boundary condition $\xi$ is a partition of the boundary graph vertices. Vertices in one block are identified, or wired together, before counting components; the identifications do not add random edges. Let $k_{\xi }(\omega )$ be the number of components of the resulting quotient open graph. ThenThe free random-cluster boundary condition has singleton blocks, while the wired random-cluster boundary condition has one boundary block. Arbitrary partitions are allowed; no assumption that the partition itself has a planar realization is needed for the monotonicity statement.

Write $\xi ⪯\zeta$ if every block of $\xi$ is contained in a block of $\zeta$, so $\zeta$ makes at least as many identifications. The precise boundary monotonicity of the random-cluster measure isEquivalently, the expectation of every real-valued order-preserving function is larger under the more wired measure. This is stochastic domination of probability measures on the coordinatewise configuration order.

To prove it, condition on every edge except $e=\{u,v\}$. If $u,v$ are already connected using those open edges and the boundary wiring, opening $e$ does not change $k_{\xi }$, so its conditional open probability is $p$. If they are not connected, opening it reduces $k_{\xi }$ by one. The ratio of the open weight to the closed weight is then $p/[q(1-p)]$. Thus the random-cluster single-edge conditional probability isFor $q\ge 1$ the second number is at most the first. Adding open edges or making the boundary partition coarser can only turn a disconnected pair into a connected one. Therefore these conditional open probabilities are increasing in both the exterior configuration and the amount of wiring.

Run a heat-bath Markov chain for each boundary partition. At every step choose the same uniformly sampled edge in both chains, sample the same independent uniform variable $U$, and set that edge open if $U$ is below its conditional open probability. Start both chains at the all-closed configuration. By the preceding inequality, the two configurations remain ordered at every update. Each marginal chain has its corresponding random-cluster measure as its stationary distribution: resampling one coordinate from its conditional distribution preserves that law. Because $0<p<1$ and $q>0$, every update gives both possible states positive probability; the finite chain is an irreducible Markov chain with aperiodicity, and hence converges to its unique stationary distribution. Taking expectations of any order-preserving function and passing to the limit proves the claimed stochastic domination of probability measures. At $q=1$ the two conditional probabilities agree, and the boundary condition has no effect on the independent bond percolation law.

For the final identity fix a plane embedding of the finite planar graph, and include the unbounded face in its planar dual graph. In the dual configuration ${\bar{\omega }}^{\ast }$, a dual edge is open exactly when its crossed primal edge is closed. Let $m=o(\omega )$. The spanning open primal subgraph has $|V|$ graph vertices, $m$ edges, and $k(\omega )$ components. The Euler formula for a connected planar graph, applied componentwise with the common exterior face accounted for, gives its number of faces asDeleting a closed primal edge merges its incident original faces precisely when its dual edge joins distinct dual components. Consequently the faces of the open primal subgraph correspond exactly to components of the open complementary dual subgraph. This remains true for bridges and loops, with their dual loops and bridges, and for a disconnected primal graph. Thus the planar cluster-count identity isAt the self-dual parameter of the random-cluster model, put $s=\sqrt{q}$ andFor fixed $G$ the factor $(1-p_{\mathrm{sd}}{)}^{|E|}$ is independent of $\omega$. The weight is therefore proportional toAbsorbing the remaining graph-dependent factor into the normalization gives the symmetric cluster weight at the self-dual parameter:Counting the outer dual face and all isolated primal graph vertices is essential for the constant in the Euler identity. No assumption that $G$ is self-dual is required for this proportionality.