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

A self-avoiding walk is a finite sequence of graph vertices $v_0,\dots ,v_n$ in which successive vertices are adjacent and no graph vertex is repeated; its length is $n$, the number of edges. Include the zero-length walk.

Split a length-$m+n$ walk from $v$ into its first $m$ edges and remaining $n$ edges. After fixing the first segment, the number of possible suffixes is at most ${\sigma }_n$, since forgetting the prohibition on revisiting its earlier vertices can only increase that number. Thus ${\sigma }_{m+n}(v)\le {\sigma }_m(v){\sigma }_n$, and taking the supremum givesEvery finite-radius ball is finite because degrees are bounded. An infinite connected graph has vertices arbitrarily far from each root, so shortest paths give ${\sigma }_n(v)\ge 1$. Also ${\sigma }_n\le \Delta (\Delta -1{)}^{n-1}$ for $n\ge 1$: after the first edge, an immediate reversal is forbidden. In particular $\Delta \ge 2$ and these suprema are finite.

Apply the Fekete lemma: a real subadditive sequence $a_{m+n}\le a_m+a_n$ satisfies $\lim a_n/n={\inf }_{n\ge 1}{a}_n/n$, allowing negative infinity. Here $a_n=\log {\sigma }_n\ge 0$, so the limit is finite. The uniform connective constant of a bounded-degree graph is therefore

The equal rooted counts imply that the self-avoiding walk generating function is $Z_G(x)={\sum }_{n\ge 0}{\sigma }_n{x}^n$. The Cauchy-Hadamard theorem identifies the radius of a power series $\sum a_n{x}^n$ as the reciprocal of $\mathrm{limsup}|a_n{|}^{1/n}$. ConsequentlyEquivalently, the root test gives convergence when $x\mu <1$ and divergence when $x\mu >1$. At the positive boundary $x={\mu }^{-1}$, the preceding infimum formula gives ${\sigma }_n{\mu }^{-n}\ge 1$, so this particular series diverges there as well.

The bipartite graph property means that a walk starting in $V_0$ ends there precisely when its length is even. Thus the even-length walk generating function on a bipartite graph is $Z_G^0(x)={\sum }_{k\ge 0}{\sigma }_{2k}{x}^{2k}$. Deleting the last edge of an odd-length self-avoiding walk leaves an even-length one; each such prefix has at most $\Delta$ possible last-edge choices. Hence ${\sigma }_{2k+1}\le \Delta {\sigma }_{2k}$, and for $x\ge 0$,These inequalities also hold with infinite values. Their finite positive prefactor shows that the two power series have the same radius of convergence $1/\mu$; alternatively apply the root formula to the even subsequence.

Consider a walk in the replaced graph that starts and ends in $V_0$. Each passage through a triangle enters at one port and leaves at a different port. It cannot revisit that triangle: the first passage uses at least two of its three vertices, whereas a later completed passage would need two previously unused ports. Nor can it immediately return through its entry port, since that would repeat a graph vertex. Contracting each passage therefore gives a self-avoiding walk in $G$ ending in $V_0$.

Conversely, each length-$2k$ walk of this kind in $G$ visits $k$ distinct vertices of $V_1$. At each one, its incoming and outgoing ports determine exactly two routes through the triangle: the direct internal edge or the two internal edges through the third port. Including the two external edges, these have lengths three and four. The choices at distinct triangles are independent combinatorial choices, so that walk contributes $(x^3+x^4{)}^k$ to the new generating function. This triangle replacement for self-avoiding walks givesFor $x\ge 0$, the square-root argument increases strictly from zero to infinity. Nonnegative coefficients and the radius from part (iii) therefore give the unique positive thresholdThis identifies the radius of the restricted series, without assuming that the new graph has equal counts from every graph vertex.

Order configurations coordinatewise. The FKG lattice condition on the masses of a finite Boolean lattice isThe FKG inequality states that under this condition, increasing real-valued functions $f,g$ satisfy $\mathbb{E}[fg]\ge \mathbb{E}[f]\mathbb{E}[g]$. In particular increasing events satisfy $P(A\cap B)\ge P(A)P(B)$. For a product measure with coordinate weights $w_e(0),w_e(1)$, the pair $(\min ({\omega }_e,{\eta }_e),\max ({\omega }_e,{\eta }_e))$ has the same two entries as $({\omega }_e,{\eta }_e)$. Multiplying over coordinates gives equality in the lattice condition, including degenerate Bernoulli parameters without division by zero.

For independent bond percolation on the nearest-neighbor cubic lattice, write ${\theta }_d(p)={\mathbb{P}}_p(|C(0)|=\infty )$. Define the percolation critical probability and the connective constant bywhere $c_n(d)$ counts rooted $n$-step self-avoiding walks. Translation invariance makes the root irrelevant, and part (i) proves existence of the latter limit.

First work on the square lattice, whose dual is another translated square lattice. Put $q=1-p$ and assume $q\mu (2)<1$. If the open cluster at the origin is finite, its exterior edge boundary contains a closed dual simple circuit surrounding the origin. To see this planar fact, surround its finitely many vertices by their unit square cells and follow the exterior boundary: its crossing primal edges are closed. Resolving repeated boundary vertices into simple circuits leaves a circuit separating the origin from infinity.

Let $a_n$ count such dual circuits of length $n$. Every one crosses the positive horizontal ray at distance at most $n$, because it surrounds the origin and its horizontal span is at most its length. Choosing a ray-crossing edge, an orientation and all but the last edge encodes it by one of at most $Cn$ rooted length-$n-1$ self-avoiding walks. Thus $a_n\le Cn{c}_{n-1}(2)$. Choose $b>\mu (2)$ with $qb<1$. The root-count limit gives $c_{n-1}(2)\le C_b{b}^n$, soThis summable tail alone need not make the probability of every enclosing circuit less than one. Choose a large $R$ and let $A_R$ be the absence of enclosing closed dual circuits of length at least $R$, with $P(A_R)>1/2$. Let $B_R$ require every primal edge inside $[-R,R{]}^2$ to be open. It has positive probability. Both events are increasing. The finite-measure Harris-FKG inequality extends to $A_R$ by decreasing limits over finitely many circuit exclusions, so $P(A_R\cap B_R)\ge P(A_R)P(B_R)>0$.

On $B_R$ the origin is connected to every graph vertex of that box. Any closed dual circuit enclosing the origin must then enclose the whole box, hence have length at least $R$. On $A_R\cap B_R$ no such circuit exists, so the origin cluster is infinite. This proves the connective-constant Peierls bound, $p_c(2)\le 1-1/\mu (2)$. Finally the lattice in dimension $d\ge 2$ contains a coordinate copy of the square lattice, whose edge law is unchanged. Percolation in that subgraph implies percolation in the full graph, and hence

Fix $k\ge 1$ and write $n=qk+r$ with $1\le r\le k$ and $q\ge 0$. Repeatedly use the given inequality with its second index equal to $k$. This yieldsThere are only finitely many possible remainders for fixed $k$, soTaking $k=1$ rules out positive infinity for this upper limit. Let $L=\mathrm{liminf}{x}_n/n$, which may be negative infinity, and choose $k_j\to \infty$ with $x_{k_j}/k_j\to L$. The assumption ${\alpha }_{k_j}/k_j\to 0$ then gives $\mathrm{limsup}{x}_n/n\le L$. This also works when $L=-\infty$, by taking an arbitrarily negative upper bound. Therefore the asymmetrically almost-subadditive sequence hasThe last infimum identity follows from the fixed-$k$ bound and from the convergence of the corrected ratios to $\gamma$. No positivity assumption on ${\alpha }_n$ is required.

A connection to a box boundary can be witnessed by a finite self-avoiding open path stopped at its first boundary hit. On the event of reaching radius $m+n$, split such a path at its first graph vertex $z\in \partial {\Lambda }_n$. Its prefix witnesses connection from zero to $z$ within ${\Lambda }_n$. Its remaining segment reaches a point $y$ with $\Vert y{\Vert }_{\infty }=m+n$, so $\Vert y-z{\Vert }_{\infty }\ge m$; truncate it at its first hit of $z+\partial {\Lambda }_m$. The two witnessing edge sets are disjoint, giving disjoint occurrence of increasing events.

Use the BK inequality: for increasing finite-coordinate events in a Bernoulli product measure, $P(A\square B)\le P(A)P(B)$, where the square means disjoint open-edge witnesses. For each fixed $z$, the first event has probability at most ${\beta }_n$, and the second has probability exactly ${\beta }_m$ by translation invariance. A union bound over $z$ givesThe two boxes can overlap, so replacing BK by an independence claim would be incorrect. Restricting each event to paths stopped at its local boundary makes all the relevant coordinate sets finite, as required by the stated inequality.

Put $x_n=\log {\beta }_n$ and ${\alpha }_n=\log |\partial {\Lambda }_n|$. Here $|\partial {\Lambda }_n|=(2n+1{)}^d-(2n-1{)}^d$, so ${\alpha }_n=O(\log n)=o(n)$. A fixed straight open path of length $n$ gives $p^n\le {\beta }_n\le 1$. Part (a) therefore gives the almost-subadditive percolation decay rateIn particular the limit is finite for the prescribed $0<p<1$.

For every site, $P(R(x)\ge r)={\beta }_r$. This event depends only on edges with both endpoints in $x+{\Lambda }_r$: any connecting path can be stopped on its first hit of that boundary. Since $\lambda >0$, ${\beta }_r\to 0$, so all clusters have finite radius almost surely, by a countable union over sites. Set the radius of an isolated site to zero.

Write $a_n=(d/\lambda )\log n$. It suffices to take $0<ϵ<1$, since larger error intervals contain one such interval. For any small $\delta >0$, the decay-rate limit gives, for all large $r$,For the upper tail use $r_{+}=\lceil (1+ϵ)a_n\rceil$ and a union bound:provided $\delta <\lambda ϵ/(1+ϵ)$.

For the lower tail let $r_{-}=\lfloor (1-ϵ)a_n\rfloor +1$. Choose sites in ${\Lambda }_{n-r_{-}}$ spaced by $2r_{-}+1$ in each coordinate. Their radius-$r_{-}$ boxes are vertex-disjoint, so their local connection events are independent. There are $N_n\ge c(n/r_{-}{)}^d$ such sites for large $n$. If $M_n\le (1-ϵ)a_n$, none of these events occurs. Thuswhereif $\delta <\lambda ϵ/(1-ϵ)$. Choose one $\delta$ satisfying both restrictions. The integer choices give the required strict inequalities. Thus the maximum cluster radius under exponential one-arm decay has convergence in probability:The logarithmic box-packing loss does not change the leading constant $d/\lambda$.

Independent bond percolation turns a deterministic graph into a random network: each edge is open with probability $p$, independently, and a percolation cluster is a connected component of its open subgraph. Site percolation instead randomizes vertices. On the cubic lattice the percolation probability $\theta (p)=P_p(0\leftrightarrow \infty )$ is the order parameter and $p_c=\inf \{p:\theta (p)>0\}$ is the critical probability. A monotone coupling, using independent uniform edge labels and opening labels below $p$, makes the growth of connectivity with $p$ transparent.

For $d\ge 2$, $0<p_c<1$: self-avoiding walk counting gives $p_c\ge 1/\mu (d)$, and the planar bound proved above gives an upper bound below one. Below $p_c$, clusters are finite and connection probabilities decay exponentially, a percolation sharpness theorem rather than a consequence of the threshold definition alone. Above $p_c$ there is almost surely a unique infinite percolation cluster. At criticality, the presence of an infinite percolation cluster must be addressed for the particular model. In two dimensions there is none. The transition replaces a finite characteristic length by scale-free geometry, followed by a macroscopic connected component.

Percolation critical exponents quantify different aspects of this change. Use power-law notation for leading exponents; it may suppress amplitudes and logarithmic corrections. From the subcritical side, define the percolation susceptibility $\chi (p)={\mathbb{E}}_p|C(0)|$ and an exponential correlation length $\xi (p)=1/\lambda (p)$, using a fixed norm for the one-arm rate. Above criticality the unrestricted expectation is infinite, so a finite-cluster percolation susceptibility must exclude the infinite percolation cluster. The principal observables are:

The last distribution is not the distribution seen from a uniformly chosen site: the latter is weighted by cluster size. In the scaling description this accounts for $1/\delta =\tau -2$. Under the usual below-upper-critical-dimension scaling hypotheses, further scaling relations for critical exponents includeThey organize the exponents into a small number of independent quantities; they are not automatic identities following only from their definitions. A percolation cluster fractal dimension $D_f$ describes the mass of a large critical cluster of radius $r$ as roughly $r^{D_f}$, with the scaling relation for critical exponents $D_f=d-\beta /\nu$ in this regime.

The percolation universality hypothesis is that ordinary short-range independent models in the same spatial dimension share these exponents and their continuum behavior despite differing microscopic lattices or using bonds rather than sites. The threshold itself is not universal. Long-range connections, correlations or changes of geometry can change the universality class, so the hypothesis does not include every random graph called percolation.

Two dimensions have a particularly strong geometric structure. Closed planar dual graph circuits obstruct primal open paths. The Harris-Kesten theorem fixes the square lattice bond percolation threshold at $p_c=1/2$, using planar duality and crossing estimates. Self-duality alone is not a proof; uniform rectangle-crossing control is a crucial extra ingredient. The Russo-Seymour-Welsh theorem keeps critical crossing probabilities of rectangles of fixed aspect ratio bounded away from zero and one at all scales. Closed dual circuits on disjoint annular scales then rule out an infinite critical cluster and reveal why arbitrarily large finite structures persist.

Critical site percolation on the triangular lattice has rigorously established conformal invariance of planar percolation for crossing limits and an SLE description of interfaces. These results are specific to this model. The exact planar valuesare rigorously established there; its one-arm probability has exponent $5/48$. In the corresponding scaling description these values give $\eta =5/24$, $\delta =91/5$, $\tau =187/91$ and $D_f=91/48$. The percolation universality hypothesis predicts the same planar exponents for square lattice bond percolation, but the triangular-lattice theorem by itself does not prove that transfer. This distinction separates exact model-specific mathematics from a broader physical prediction.

Dimension changes the importance of loops and correlations between growing branches. The mean-field percolation exponents come from approximating critical clusters by branching processes. Their values are $\beta =1$, $\gamma =1$, $\delta =2$, $\nu =1/2$, $\eta =0$ and $\tau =5/2$. The predicted upper critical dimension of percolation is six. One way to see its role is the triangle diagram appearing in the percolation triangle condition: if the long-distance Fourier connectivity behaves like $|k{|}^{-2}$, its infrared contribution is proportional to ${\int }_0^{\epsilon }{r}^{d-7}dr$. It is finite above six and logarithmically divergent at six. This motivates mean-field behavior above six and logarithmic corrections at six, without turning that heuristic into a proof for every lattice.

Lace expansion makes the mean-field picture rigorous in suitable high-dimensional regimes. For nearest-neighbor percolation, sufficiently high dimensions are covered; sufficiently spread-out models have mean-field results for every $d>6$. Between two and six the exponents depend nontrivially on dimension, and exact three-dimensional values are not supplied by the planar theory. Hyperscaling relation illustrates the change: mean-field values give $2\beta +\gamma =3$, while $d\nu =d/2$, so the naive equality fails above six. In $d=1$, $p_c=1$ and no infinite percolation cluster exists for $p<1$; this is a degenerate endpoint case rather than the ordinary interior transition.