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

In bond percolation on an undirected graph $G=(V,E)$, a configuration is $\omega \in \{0,1{\}}^E$. The edge $e$ is open when ${\omega }_e=1$ and closed when ${\omega }_e=0$. Under ${\mathbb{P}}_p$, the coordinates are independent and identically distributed random variables with the Bernoulli distribution of parameter $p$. For a countable edge set, use the product sigma-algebra and the product measureThe open edges form a random subgraph with the original graph vertices. Its connected components of a graph are the percolation clusters. Write $x\leftrightarrow y$ when an open graph path joins $x$ to $y$; a zero-length graph path is allowed, so $x\leftrightarrow x$ always holds. The randomness is in the independently open bonds; all vertices remain present.

Order configurations coordinatewise: $\omega \le {\omega }^{\prime }$ means ${\omega }_e\le {\omega }_e^{\prime }$ for every edge. An increasing event $A$ is a measurable set such that $\omega \in A$ and $\omega \le {\omega }^{\prime }$ imply ${\omega }^{\prime }\in A$. Opening additional edges cannot destroy an increasing event. The Harris-FKG inequality, the product measure version of the FKG inequality, statesfor two increasing events. Equivalently, bounded coordinatewise increasing random variables $f,g$ satisfy ${\mathbb{E}}_p(fg)\ge {\mathbb{E}}_{p}f{\mathbb{E}}_{p}g$. The event inequality also holds for two decreasing events, by taking complements.

For disjoint occurrence of increasing events, a finite open edge set $K$ witnesses $A$ in $\omega$ if every configuration agreeing with $\omega$ on $K$ belongs to $A$. Since $A$ is an increasing event and all edges of $K$ are open, this says that the configuration with exactly $K$ open already forces $A$. Define $A\square B$ to consist of configurations admitting disjoint finite witnesses $K,L$ for $A,B$. For events depending on finitely many edges, this is the usual disjoint-occurrence definition; it also applies to finite-connection events on the infinite graph. The Van den Berg-Kesten inequality statesOn a countable graph, its finite-witness version follows by taking increasing unions over finite edge sets. The Harris-FKG inequality concerns simultaneous occurrence, whereas the Van den Berg-Kesten inequality requires separate certificates using disjoint coordinates.

Use integer graph vertices in the boxes: ${\Lambda }_n=[-n,n{]}^2\cap {\mathbb{Z}}^2$, and set ${\Lambda }_{-1}=\varnothing$. Thus $\partial {\Lambda }_0=\{0\}$, $g_0=1$, and $|\partial {\Lambda }_m|=8m$ for $m\ge 1$.

If $0\leftrightarrow \partial {\Lambda }_{m+n}$, erase loops from an open graph path to obtain a self-avoiding walk. Let $x$ be its first graph vertex on $\partial {\Lambda }_m$. Split at $x$. The prefix certifies $A_x=\{0\leftrightarrow x\}$, while a segment of the suffix certifies $B_x=\{x\leftrightarrow x+\partial {\Lambda }_n\}$: the final graph vertex is at supremum norm distance at least $n$ from $x$, so the suffix first hits that translated boundary. The two certificates use disjoint edges. Therefore the BK boundary-splitting estimate, the union bound, the Van den Berg-Kesten inequality, and translation invariance giveThe cases $m=0$ or $n=0$ follow directly from $g_0=1$, so this proves the bound including the endpoints.

Here is an explicit way to remove the polynomial boundary factor. For $p>0$ put $b_n=32n^2{g}_n$, $n\ge 1$. By symmetry in $m,n$, assume $m\le n$. ThenConsequently $a_n=\log b_n$ is a subadditive sequence. The Fekete lemma states that any real subadditive sequence satisfies $\lim a_n/n={\inf }_{n\ge 1}{a}_n/n$, possibly $-\infty$. In this case the direct horizontal open graph path gives $g_n\ge p^n$, so this limit of a sequence is bounded below by $\log p$. Since $g_n\le 1$, its upper bound is zero. Finally,has the same limit of a sequence. Thus the percolation one-arm decay rate exists andFor $p=0$, every $g_n$ with $n\ge 1$ is zero and $\gamma =0$. No exponential-decay theorem or assumption that $p$ is below the percolation critical probability is needed.

The union bound gives $g_k\le {\sum }_{x\in \partial {\Lambda }_k}{\mathbb{P}}_p(0\leftrightarrow x)$. Hence some boundary graph vertex has percolation two-point connection probability at least $g_k/(8k)$. The rotations and reflections of the square lattice let us choose such a graph vertex as $x=(k,j)$, $-k\le j\le k$. Reflection in the vertical line through $x$ sends $0$ to $e_{2k}=(2k,0)$ and fixes $x$. ThereforeThe Harris-FKG inequality applied to these two increasing events proves the reflection lower bound for two-point percolation:Every graph path from $0$ to $e_{2k}$ reaches $\partial {\Lambda }_{2k}$, so $h_{2k}\le g_{2k}$. Taking roots givesBoth outside expressions have limit of a sequence $\gamma$, proving the even case. For $p>0$, the Harris-FKG inequality with the last horizontal edge gives $h_{2k+1}\ge p{h}_{2k}$, and also $h_{2k+1}\le g_{2k+1}$. The lower bound has rootThe upper bound has the same limit of a sequence. At $p=0$ all positive-distance connection probabilities vanish. Thus ${\lim }_{n\to \infty }{h}_n^{1/n}=\gamma$ for every $p\in [0,1]$.

An $n$-step self-avoiding walk on a graph $G=(V,E)$ is a sequence $(v_0,v_1,\dots ,v_n)$ of $n+1$ distinct graph vertices such that $\{v_{i-1},v_i\}\in E$ for $1\le i\le n$. It has $n$ edges and no repeated vertex, including its starting graph vertex. The $0$-step self-avoiding walk consists of its starting graph vertex alone.

Represent the doubly infinite ladder graph by $\mathbb{Z}\times \{0,1\}$, with horizontal edges between successive columns and a vertical rung at each column. An allowed self-avoiding walk is coded by a word in $R,V$. Two successive $V$ steps revisit the preceding graph vertex and are forbidden. Conversely, every word without consecutive $V$ steps is a self-avoiding walk: horizontal steps strictly increase the column, and a column is visited vertically at most once. This establishes a bijection, not merely an upper bound.

For the directed ladder self-avoiding walk count, ${\sigma }_0=1$, ${\sigma }_1=2$, and for $n\ge 2$ a word either ends in $R$, or ends in $RV$. Removing that final block givesLet $\phi =(1+\sqrt{5})/2$ be the golden ratio, and $\psi =(1-\sqrt{5})/2$. The Binet formula for the Fibonacci number yieldsSince $|\psi |<\phi$, taking $n$th roots gives ${\lim }_{n\to \infty }{\sigma }_n^{1/n}=\phi$. This use of the golden-ratio symbol is independent of the connection rate in Question 1.

Let $c_n$ count $n$-step self-avoiding walks on the square lattice from one fixed graph vertex. Splitting a self-avoiding walk after $m$ steps and dropping the avoidance constraint on its suffix gives $c_{m+n}\le c_m{c}_n$. The Fekete lemma therefore gives the connective constant $\mu =\lim c_n^{1/n}$. The planar dual graph of the square lattice is a translated copy of it, so its connective constant is also $\mu$.

Put $q=1-p$ and assume $q\mu <1$. Choose $a>\mu$ with $qa<1$. The definition of the connective constant provides a finite $K$ such that $c_j\le K{a}^j$ for every $j\ge 0$. A simple dual graph cycle of length $\ell$ surrounding $0$ has a graph vertex in a box of radius $\ell +1$: its diameter is at most $\ell$, and its coordinate ranges straddle the origin. Choose such a graph vertex as the starting point, orient the graph cycle, and omit its closing edge. The remaining self-avoiding walk has length $\ell -1$. Consequently the number $N_{\ell }$ of these graph cycles obeysfor fixed finite constants. A specified graph cycle is open in dual bond percolation, equivalently all its crossed primal edges are closed, with probability $q^{\ell }$. HenceTo make this tail argument valid for every $q\mu <1$, rather than only extremely small $q$, use a finite modification of Bernoulli percolation. Condition all primal edges within ${\Lambda }_N$ to be open. This event has positive probability for $p>0$. If the resulting percolation cluster of $0$ is finite, its outer boundary contains a simple closed dual graph cycle surrounding the whole box. Such a graph cycle has length tending to infinity with $N$ and crosses no forced-open edge. Under the conditioning its remaining edge states retain the original independent law, so its probability is still $q^{\ell }$. Choose $N$ so that the above tail is less than $1/2$. The conditional probability that $0$ belongs to an infinite percolation cluster is then at least $1/2$, and thus $\theta (p)>0$.

This connective-constant Peierls bound proves that every $p>1-{\mu }^{-1}$ is above or at the onset of positive percolation probability. Taking the infimum givesThe case $p=1$ is immediate. This proof uses the Peierls argument, without assuming the exact Harris-Kesten theorem.

Write ${\mathcal{W}}_n$ for the deterministic set of $n$-step self-avoiding walks from $0$. Each uses $n$ distinct edges, so independence givesFor $n\ge 1$, the function $t\mapsto t^{1/n}$ on $[0,\infty )$ is a concave function. The Jensen inequality gives the root-moment bound for open self-avoiding walksEquivalently, the Lyapunov moment inequality compares exponents $1/n$ and $1$, both strictly positive. Taking the limit superior and the connective constant limit provesThis includes $p=0$ and $n=1$. No independence between the different self-avoiding walk indicators is asserted or needed.

The cubic lattice has graph vertices ${\mathbb{Z}}^d$ and an edge between $x,y$ when ${\sum }_i|x_i-y_i|=1$. In independent site percolation, every graph vertex is open with probability $p$ and closed with probability $1-p$, independently. The open subgraph contains only open graph vertices and the edges between them. Let $C_p(0)$ be the open connected component of a graph containing $0$, with $C_p(0)=\varnothing$ when $0$ is closed. The percolation probability isSince the cubic lattice is a locally finite graph, the König infinity lemma identifies an infinite open connected component of a graph with the existence of an infinite open graph ray from the origin. In particular, the origin itself must be open. The percolation critical probability is $p_c=\inf \{p:\theta (p)>0\}$.

Let $A_n$ be the event that the origin has an open graph path to the boundary of $[-n,n{]}^d\cap {\mathbb{Z}}^d$. The graph path can be stopped on its first boundary visit, so $A_n$ depends on only finitely many sites. Its probability $f_n(p)={\mathbb{P}}_p(A_n)$ is a finite sum of terms $p^a(1-p{)}^b$, and is therefore a continuous function of $p$. Also $A_{n+1}\subseteq A_n$, and the König infinity lemma gives ${\bigcap }_n{A}_n=\{0\leftrightarrow \infty \}$. By continuity from above of a measure,The monotone coupling of Bernoulli percolation described below shows that $\theta$ is nondecreasing. For $p<1$, its right limit of a function $\theta (p+)$ exists and is at least $\theta (p)$. For every fixed $n$,Taking the infimum in $n$ proves $\theta (p+)=\theta (p)$. This proves right continuity of percolation probability throughout $[0,1)$; at $1$ right continuity is understood relative to the parameter domain. The argument does not interchange two uncontrolled limits.

Use the probability space $([0,1{]}^{{\mathbb{Z}}^d},\mathcal{F},\mathbb{P})$ with the product measure of the uniform distribution on $[0,1]$. Its coordinate random variables $U_v$ are independent and identically distributed random variables. Define simultaneously for every parameterFor $r\le s$, the indicator function inequality $X_r(v)\le X_s(v)$ holds pointwise at every graph vertex. For fixed $p$, each coordinate has the Bernoulli distribution with parameter $p$, and the coordinates are independent because they are functions of distinct independent $U_v$. Thus every marginal configuration is exactly the required site percolation model. This is a continuum-indexed family of processes, all on one probability space, and is the standard monotone coupling of Bernoulli percolation.

Work on the common probability space from part (c). For a configuration of all the uniforms, the set $S=\{r\in [0,1]:I_r\text{ occurs}\}$ is an upper interval, possibly with or without its lower endpoint. It is nonempty because $I_1$ occurs, and the coupled onset parameter for origin percolation is $M=\inf S$. For $0<p\le 1$,Indeed, occurrence at some $r<p$ implies $M<p$. Conversely, if $M<p$, the definition of infimum yields occurrence at some $s<p$, and a rational $r$ between $s$ and $p$ also satisfies $I_r$. This also proves measurability of $M$ through its strict sublevel sets.

Choose a rational sequence increasing to $p$. By continuity from below of a measure and the monotone coupling of Bernoulli percolation,Moreover, $\{M<p\}\subseteq I_p\subseteq \{M\le p\}$. Hence $I_p$ is the disjoint union of $\{M<p\}$ and $I_p\cap \{M=p\}$, givingIt is important to retain the intersection with $I_p$: occurrence at the infimum is not automatic. At $p=0$ there is no left limit within the parameter domain, so the displayed left-limit assertion is for $p>0$.

Use the following general result, including its site version: independent site percolation on ${\mathbb{Z}}^d$ has almost surely at most one infinite percolation cluster at each fixed parameter; for every fixed $r>p_c$ it has exactly one almost surely. This is the uniqueness of the infinite percolation cluster, also called the Burton-Keane theorem. For $d\ge 2$, the additional general fact $p_c<1$ ensures a choice of a parameter strictly between $p_c$ and $1$. In dimension one, $p_c=1$ and the asserted interval is empty.

Fix $p\in (p_c,1]$ and choose $q\in (p_c,p)$. Let ${\mathcal{C}}_q$ be the unique infinite open connected component of a graph at $q$. Under the monotone coupling of Bernoulli percolation, it is contained in the unique infinite open connected component of a graph at $p$. On $I_p$, the origin and ${\mathcal{C}}_q$ therefore lie in that same connected component of a graph, and a finite $p$-open graph path connects $0$ to some graph vertex of ${\mathcal{C}}_q$.

For this fixed deterministic $p$, the countable set of uniforms satisfies $U_v\ne p$ at every graph vertex almost surely. Thus all uniforms on that finite graph path are strictly less than $p$, including its endpoints. If $t$ is their maximum, choose $r$ with $\max (q,t)<r<p$. The graph path is then $r$-open, and its endpoint remains connected to infinity through ${\mathcal{C}}_q$. Consequently $I_r$ occurs and $M<p$. We have provedPart (d) gives left continuity at this $p$; part (b) supplies right continuity when $p<1$. The same finite-path proof gives left continuity at $p=1$, since all uniforms are strictly less than $1$ almost surely. Thus $\theta$ is continuous on $(p_c,1]$, without asserting continuity at $p_c$. This is supercritical continuity of percolation probability.

Write $H(R)$ and $V(R)$ for the horizontal and vertical open-crossing increasing events of a rectangle in the rotated square lattice. At parameter $1/2$, planar duality for rectangle crossings says that failure of $H$ is exactly a closed dual vertical crossing. Quarter-turn symmetry and the boundary convention of the rotated rectangles identify the two alternatives on a square. Thus its crossing probability is $1/2$; a rectangle obtained by a harmless one-step boundary adjustment has crossing probability at least $1/2$. This is the finite-domain exact self-dual rectangle crossing probability, not an assumption about infinite percolation clusters.

We first prove a RSW reflection extension lemma. In coordinate units adapted to the rotated drawing, take $S=[0,n{]}^2$, $T=[-n,n{]}^2$, and $R=[-n,2n]\times [-n,n]$. Reveal the rightmost open vertical crossing $\Gamma$ of $S$, when one exists, using only its edges and the region to its right. Reflect $\Gamma$ across the horizontal axis. The part $D$ of $T$ to the left of these two paths remains unexposed and has the independent parameter-$1/2$ law. A horizontal crossing of $T$ must reach their union. Its probability is at least $1/2$. Reflection symmetry and the union bound give a probability at least $1/4$ of reaching the upper path $\Gamma$ through $D$. Conditional opening of the edges on $\Gamma$ can only help. Since $V(S)$ has probability at least $1/2$, the increasing event $B$ that a vertical crossing of $S$ is connected inside $T$ to its left side has probability at least $1/8$.

Reflect this construction in the vertical midline of $S$ to obtain an increasing event $B^{\prime }$ of the same probability, connecting a vertical crossing of $S$ to the right side of $[0,2n]\times [-n,n]$. On $H(S)\cap B\cap B^{\prime }$, the horizontal crossing of $S$ meets both vertical crossings, so all three graph paths join and give $H(R)$. The Harris-FKG inequality now yieldsThe exploration only conditions the exposed side of the extremal graph path; reflecting a drawn path does not assert that its reflected edges are open. This distinction is what makes the extension argument valid.

To pass from aspect ratio $3/2$ to $3$, put four rectangles of width $3h/2$ and height $h$ next to each other, with successive left boundaries separated by $h/2$. Adjacent rectangles overlap in a square of side $h$. Require horizontal crossings of the four rectangles and vertical crossings of the three overlap squares. Every consecutive pair of horizontal crossings meets the vertical crossing in its overlap; together they form a horizontal crossing of width $3h$. The Harris-FKG inequality gives a strictly positive bound, for these compatible scales, ofThe construction works on the rotated square lattice with the boundary sites used in the source drawing. Integer roundings do not create a scale restriction: for an odd height use the largest smaller compatible even height, and use eight horizontal rectangles and seven overlap squares, whose union has auxiliary aspect ratio $5$, so that its width exceeds the desired $3m$ width for all sufficiently large $m$. Truncate its horizontal crossing on first reaching the desired right side. The number of extra rectangles and overlap-square crossings is bounded independently of $m$, and every factor is bounded below by the same positive constants. The finitely many smallest rectangles each have positive crossing probability, since a specified finite open graph path suffices. Therefore a constant $c>0$ works at every integer scale. Taking $\tau =c/2$ ensures the requested strict inequality:This proves the required instance of the Russo-Seymour-Welsh theorem through reflection, exploration and gluing. The parameter in this calculation is $1/2$.

First obtain a polynomial critical one-arm upper bound from part (a). Fix a sufficiently large integer radius $r$. Use rotated-coordinate boxes $B_r=[-r,r{]}^2$ for this geometric construction, in the axes of part (a). Surround $B_r$ by a square ring inside $B_{3r}$. It can be assembled from the four stripsThe first two require horizontal dual crossings; the last two require vertical dual crossings. Their corner overlaps are squares, so the adjacent long crossings intersect there and their union contains a dual graph cycle surrounding the inner box. Translate the strips by the half-lattice displacement of the planar dual graph and adjust the endpoints by one lattice unit if needed. All aspect ratios remain bounded. Part (a) and the same overlap gluing give a uniform lower bound $c_1>0$ for each dual crossing at $1/2$. Applying the Harris-FKG inequality to these decreasing events in the primal configuration gives a closed dual circuit with probability at least $\delta =c_1^4>0$. We may replace $\delta$ by a smaller number in $(0,1)$.

Use the independent annular barriers for percolation at radii $r_j=r_{0}10^j$. Their supporting edge sets are disjoint, so the circuit events are independent. In the original unrotated coordinates, $B_{3r}$ lies inside ${\Lambda }_{5r}$ and the ring still separates the origin from infinity. These fixed geometric comparisons let us bound the original $g_N$. An open graph path from $0$ to distance $N$ must avoid every such closed dual circuit inside ${\Lambda }_N$. Thus, for some constants $C<\infty$ and $\alpha >0$,where the first bound is used only when at least one of the indicated rings fits; increasing $C$ handles smaller $N$.

Now let $\epsilon =p-1/2>0$ and use the monotone coupling of Bernoulli percolation on edges. The event $\{0\leftrightarrow \partial {\Lambda }_N\}$ only needs edges whose endpoints lie in ${\Lambda }_N$, because a first boundary hit gives an internal graph path. There are exactly $4N(2N+1)$ such edges. Each changes state between parameters $1/2$ and $p$ with probability $\epsilon$. The union bound therefore gives the finite-box comparison for percolation parametersFor sufficiently small $\epsilon$, choose $N=\lfloor {\epsilon }^{-1/(\alpha +2)}\rfloor$, so that $N$ is at least half the unrounded value. Both terms then have order ${\epsilon }^{\alpha /(\alpha +2)}$. In particular,for a finite $A$. Increase $A$ to cover the remaining compact range of parameters by $\theta (p)\le 1$. This near-critical percolation power upper bound requires only a positive crossing constant, not the exact value of a critical exponent. It also implies $\theta (1/2)=0$ through the critical one-arm probability bound.