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

This is the Fekete lemma, with its possible extended-real limit made explicit. Put $L={\inf }_{m\ge 1}{x}_m/m$. Since $x_n\le n{x}_1$, $L$ cannot be $+\infty$; it may be $-\infty$.

Fix $m\ge 1$ and write $n=qm+r$, with $0\le r<m$. Repeated subadditivity giveswhere for this calculation set $x_0=0$. The finitely many possible remainder terms are bounded. Since $q/n\to 1/m$,This holds for every $m$, whereas $x_n/n\ge L$ by the definition of an infimum. If $L$ is finite, the upper and lower bounds agree. If $L=-\infty$, choosing $m$ with arbitrarily negative $x_m/m$ shows that $x_n/n\to -\infty$. ThusA finite real limit is not guaranteed: $x_n=-n^2$ is a subadditive sequence and has $x_n/n=-n\to -\infty$. If the limit is intended to be real rather than extended real, one must add a linear lower bound.

Split a self-avoiding walk of length $m+n$ after its first $m$ steps. Its prefix is one of the $c_m$ walks, and its translated suffix is a self-avoiding walk of length $n$ from the origin. The pair determines the original walk, although not every pair can be concatenated without intersection. ThereforeAll $c_n$ are positive, so $x_n=\log c_n$ is a subadditive sequence. The Fekete lemma gives existence of ${\lim }_n{n}^{-1}\log c_n$ and consequently of the connective constant.

For a lower bound, all words of length $n$ using only north and east steps produce distinct self-avoiding walks: the sum of the two coordinates increases at each step. Thus $c_n\ge 2^n$. For an upper bound, there are four choices for the first step and at most three thereafter, since a self-avoiding walk cannot immediately reverse its previous edge. Hence $c_n\le 43^{n-1}$. Taking $n$th roots provesThe elementary upper bound counts all non-backtracking walks, including some that self-intersect, so it is an upper estimate rather than an equality.

Count partially directed self-avoiding walks using north, east and west steps. Within one horizontal level, a self-avoiding walk must move consistently east or consistently west. It can change horizontal direction only after a north step. Conversely, these rules guarantee self-avoidance: every visited horizontal level is new, and its horizontal run is monotone.

Let $a_n$ count these walks, including $a_0=1$. A horizontal run has generating functionEvery walk decomposes uniquely into an initial horizontal run followed by zero or more pairs consisting of a north step and a horizontal run. Therefore the generating function isComparing coefficients yields $a_0=1$, $a_1=3$, and $a_n=2a_{n-1}+a_{n-2}$ for $n\ge 2$. Solving this linear recurrence relation givesThese are a subset of all self-avoiding walks, so $c_n\ge a_n$ andAllowing either horizontal direction at successive heights gives the strict gain over the north-east-only family.

Write $a=P(A_1)=P(A_2)$. The complements are decreasing events. The Harris-FKG inequality for a product measure givesThe same correlation inequality for two decreasing events follows from that for their increasing complements, since their covariance is unchanged. ThusBoth $1-a$ and the square root are nonnegative, so rearranging gives the square-root bound for increasing events:No independence between the events themselves is asserted; independence is the coordinate property of the underlying product measure.

For bond percolation, let $C(0)$ be the percolation cluster of the origin. Its percolation probability isWe prove $\theta (1/2)=0$ by alternating arms at the self-dual parameter, using the uniqueness of the infinite percolation cluster proved in Question 4. Suppose instead that $\theta (1/2)>0$.

At $p=1/2$, declaring a dual edge open exactly when its crossing primal edge is closed produces independent dual bond percolation with the same parameter on ${\mathbb{Z}}^2+(1/2,1/2)$. It therefore also has an infinite percolation cluster almost surely, and at most one. The two preliminary arguments below imply that, for a sufficiently large square, the probability of two primal infinite exterior arms starting through its top and bottom sides exceeds $3/4$. Applying the same arguments to the dual lattice gives probability greater than $3/4$ for dual infinite exterior arms starting through the left and right sides. Thus all four arms occur together with positive probability, by the union bound.

Here are precise boundary conventions for the alternating exterior-arm separation lemma. Use the primal graph vertex box $[-N,N{]}^2$, the dual graph vertex box $[-N+1/2,N-1/2{]}^2$, and the common continuous square with sides at $\pm (N+1/4)$. The primal arms first cross its top and bottom; the dual arms first cross its left and right. Subsequent graph vertices of every arm lie outside this continuous square. Large $N$ gives the required probabilities for both boxes, by the same rotational symmetry and boundary-side estimate. Primal open paths and dual open paths cannot cross, since the two states of a crossing edge are complementary.

The two primal arms cannot meet in the exterior. If they did, a finite simple primal crosscut in the exterior would join the top and bottom entry points. Together with one of the two arcs of the square boundary it would enclose a bounded region containing one of the dual entry points. That dual exterior arm could not reach infinity without crossing the primal crosscut or the forbidden square interior. This is the alternating exterior-arm separation lemma. Thus the two primal arms are disjoint.

Now modify only the primal edges with both endpoints in $[-N,N{]}^2$, making them open. Their grid supplies a simple interior path joining the two primal arm roots. The unchanged exterior arms and this connector form a proper doubly infinite simple primal path. Such a path separates the plane into two sides, by the Jordan curve theorem applied to its one-point compactification in the sphere. The left and right dual arms lie on opposite sides. Preserve their tails from their first exterior dual graph vertices; none of those tails crosses a modified edge. Their original boundary attachment edges may be destroyed, but the infinite exterior tails themselves remain. They now belong to two distinct infinite dual clusters, since any dual connection between them would have to cross the doubly infinite primal path.

This modification has positive probability by the finite-energy property of Bernoulli percolation: condition on the exterior configuration and open the finitely many interior edges. The exterior projections of the four-arm event have positive probability. The resulting positive-probability event with two infinite dual clusters contradicts uniqueness of the infinite percolation cluster on the dual lattice. Therefore

Only the selected paths are drawn. The black connector lies in the finitely modified box; the two blue infinite dual tails remain outside and on opposite sides.

The proof uses self-duality, symmetry, positive association, finite-energy property of Bernoulli percolation and uniqueness; it does not assume the Harris-Kesten theorem as a black box. The boundary language means an infinite ray whose first graph vertex is on the side and all later graph vertices are outside the graph vertex box. It cannot mean literal intersection of two disjoint sets, a closed box boundary and its strict complement.

Assume $\theta (1/2)>0$. The event that some infinite percolation cluster exists is invariant under lattice translations. By translation ergodicity of Bernoulli percolation, its positive probability is therefore one.

Let $D_N$ be the event that an infinite percolation cluster meets the finite graph vertex box $B_N=[-N,N{]}^2$. These increasing events increase with $N$, and their union is the event that some infinite percolation cluster exists. Continuity from below of a measure givesAn infinite percolation cluster meeting $B_N$ contains an infinite simple open ray in a graph from a graph vertex of the box. This follows from local finiteness and the König infinity lemma. That ray visits the finite box only finitely many times; its last box graph vertex lies on the boundary, and the subsequent ray is outside. Thus $D_N$ is also the event that the box boundary intersects an infinite percolation cluster, and is the union of the four exterior-side arm events.

Consequently, for every $ϵ>0$, choose $N$ withFor $ϵ\ge 1$ any sufficiently large $N$ still satisfies the strict inequality. No uniqueness assertion is needed for this preliminary step.

Let $E_T,E_B,E_L,E_R$ be the increasing events that an infinite simple open ray in a graph starts at the indicated side and immediately leaves the box, with all later graph vertices outside it. A corner exit is assigned according to the direction of its outgoing edge. The four events have the same probability $a_N$ by rotational symmetry. Their union is $D_N$ from the preceding step.

The Harris-FKG inequality applies to these exterior-ray events by approximation with finite connections to larger boxes and passage to decreasing limits. Positive association of the four decreasing events $E_s^c$, by iterating the Harris-FKG inequality, givesEquivalently, one may apply the preceding square-root bound for increasing events first to the two opposite-side unions and then to the two individual sides of one pair. ThereforeA union bound now showsChoose $N$ such that $1-\mathbb{P}(D_N)<(1/8{)}^4$. ThenThe infinite exterior clusters touched by these two sides need not be the same. The same argument works for dual boxes and any sufficiently large size; this permits the matching primal/dual contours used in the full proof.

At $p=1/2$, explore the directed out-cluster of the origin by a deterministic breadth-first procedure. Maintain the set of reached graph vertices and a queue of untested edges with one reached and one unreached endpoint. For each such edge, reveal its orientation. Add the unreached endpoint if the arrow points from the reached endpoint to it; otherwise discard that edge. edges whose endpoints are both already reached need no further test.

An untested edge has an independent fair orientation even though the choice of the next edge depends on earlier discoveries. Its probability of pointing toward the unreached endpoint is $1/2$, whichever geometric direction that represents. Thus the discovery procedure has exactly the same transition probabilities as the ordinary bond percolation cluster exploration at density $1/2$. In particular, for every $m$, the probability of reaching at least $m$ graph vertices agrees in the two models. The uniform random orientation out-cluster comparison impliesA locally finite graph has an infinite directed simple ray from the origin exactly when its directed out-cluster is infinite: the exploration predecessor edges form a finitely branching rooted tree, to which the König infinity lemma applies. Conversely, such a ray visits infinitely many reachable graph vertices. HenceFairness of orientations is essential to this comparison; for general $p$ the success probability depends on the geometric direction of exploration. As usual, an infinite directed path means a ray with distinct graph vertices. Allowing a finite directed cycle to be traversed repeatedly would define an infinite walk instead and would make the claimed conclusion false.

Order configurations coordinatewise: $\omega \le \eta$ means $\omega (e)\le \eta (e)$ for every edge. Then stochastic domination is the conditionEquivalently, ${\mathbb{E}}_{{\mu }_1}f\ge {\mathbb{E}}_{{\mu }_2}f$ for every real-valued order-preserving function $f$. The equivalence follows on this finite space by writing $f$, up to an additive constant, as a nonnegative linear combination of indicators of its increasing upper level sets. A coupling of probability distributions supported on pairs $(X_1,X_2)$ with $X_1\ge X_2$ proves this domination; conversely such an ordered coupling of probability distributions exists on a finite partially ordered space.

For the coordinatewise lattice operations $\omega \vee \eta$ and $\omega \wedge \eta$, Holley's condition isThis sufficient condition implies ${\mu }_1\ge {\mu }_2$ by the Holley inequality. It is often stated first for strictly positive probability weights, as will hold for the random-cluster application, but the displayed condition is also sufficient for nonnegative weights.

For clarity about the zero-weight case, apply the four functions theorem to an increasing event $A$, with the first two functions ${\mu }_1{1}_{A^c}$ and ${\mu }_2{1}_A$, and the last two ${\mu }_1{1}_A$ and ${\mu }_2{1}_{A^c}$. If $\omega \notin A$ and $\eta \in A$, then $\omega \vee \eta \in A$ and $\omega \wedge \eta \notin A$. The pointwise hypothesis is exactly the displayed cross-lattice inequality. Its summed conclusion giveswhich rearranges to ${\mu }_1(A)\ge {\mu }_2(A)$. This establishes the same statement without a positivity-of-support assumption.

Identify a configuration with its set $S$ of open edges. Let $k(S)$ count the connected components of a graph on the full graph vertex set, including isolated graph vertices. The random-cluster measure isFor $p\in (0,1)$ and finite $q\ge 1$ all its weights are positive. We compare $1\le q_1\le q_2$, taking ${\mu }_1={\mu }_{p,q_1}$ and ${\mu }_2={\mu }_{p,q_2}$.

The key fact is supermodularity of graph component count:To prove it, orient the graph edges arbitrarily and let $U_S$ be the real span of their incidence vectors for edges in $S$. Its dimension of a vector space is $r(S)=|V|-k(S)$: on each connected component of a graph these vectors span the vectors whose coordinates sum to zero. Since $U_{S\cup T}=U_S+U_T$ and $U_{S\cap T}\subset U_S\cap U_T$, the dimension formula for a sum of subspaces giveswhich is exactly the component-count inequality.

Put $a=k(S)-k(S\cup T)\ge 0$ and $b=k(S\cap T)-k(T)\ge 0$. The preceding inequality gives $b\ge a$. In the ratio of the two sides of Holley's condition, the normalization constants and Bernoulli edge factors cancel, because $|S\cup T|+|S\cap T|=|S|+|T|$. The ratio is thereforeBy the Holley inequality, ${\mu }_{p,q_1}$ stochastically dominates ${\mu }_{p,q_2}$. Thus increasing cluster weight suppresses every increasing event:The random-cluster single-edge conditional probability confirms the mechanism: it is $p$ when the endpoints are already connected, and $p/(p+q(1-p))$ otherwise. Larger $q$ favours configurations with more separate components. The condition $q\ge 1$ enters explicitly in the last factor $q_2^{b-a}$.

Use consistently wired boundary conditions in increasing finite boxes and let ${\varphi }_{p,q}^{\mathrm{w}}$ be the usual wired infinite-volume random-cluster measure. The finite-volume comparison just proved applies with boundary graph vertices identified, since it is still a comparison on a finite graph. Passing to the infinite-volume limit preserves the inequality for every increasing event determined by finitely many edges.

For fixed $m$, let $A_m$ be the event that the origin connects by an open path in $[-m,m{]}^2$ to its boundary. It is such a finite increasing event. Therefore, for $q_1\le q_2$,The events decrease to the event that the origin has an infinite percolation cluster, by local finiteness. Continuity from above of a measure givesDefine the random-cluster critical probability by $p_c(q)=\inf \{p:{\theta }^{\mathrm{w}}(p,q)>0\}$. The set in which percolation occurs at $q_2$ is a subset of that at $q_1$, whenceThe same proof works if free boundary conditions are used consistently throughout. It compares critical probabilities; it does not presume whether an infinite percolation cluster exists at the critical parameter itself.

The Burton-Keane theorem says that for independent bond percolation on the hypercubic lattice ${\mathbb{Z}}^d$, $d\ge 2$, at every fixed $p\in [0,1]$, there is almost surely at most one infinite percolation cluster. It does not assert that such a cluster exists, nor does it assert absence of percolation at the critical parameter. The cases $p=0$ and $p=1$ are immediate; assume $0<p<1$ for the proof.

Let $N_{\infty }$ be the number of infinite percolation clusters. This random variable is translation invariant. By translation ergodicity of Bernoulli percolation, it is almost surely a constant $k\in \{0,1,2,\dots ,\infty \}$. One way to see ergodicity is to approximate an invariant event by events on finite sets of edges, translate one approximation far enough to make the two approximations independent, and then let the approximation error vanish. Its probability equals its square, hence is zero or one.

The other probabilistic input is the finite-energy property of Bernoulli percolation. Conditionally on all edges outside a finite set, every prescribed inside configuration has positive probability, namely a product of powers of $p$ and $1-p$. Thus an event of positive probability can be followed by a specified finite modification and still gives a positive-probability image event. Outside infinite arms are unaffected.

First exclude a finite $k\ge 2$. Some finite box meets at least two infinite percolation clusters with positive probability. Open all edges in and incident to that box. These clusters merge. Opening finitely many edges cannot create an infinite percolation cluster solely out of finite clusters, since it joins only finitely many such clusters. Hence the number of infinite percolation clusters decreases with positive probability, contradicting its almost-sure constant value. This rules out every finite multiplicity greater than one.

Now suppose $k=\infty$. With positive probability a finite box meets at least three distinct infinite percolation clusters. Retain an exterior infinite ray from each of three of them. Replace the finitely many interior and boundary edges by a minimal tree joining their three attachment graph vertices, and close all unused edges there. The exterior rays belong to distinct original clusters, so have no outside connections to each other. The resulting joined cluster has a branch graph vertex $v$ with exactly three incident open edges, and deleting $v$ leaves three infinite components. If a terminal lies in the middle of the interior connecting path, its exterior ray supplies the third branch there. Such a graph vertex is a trifurcation vertex in percolation. A finite box has only finitely many candidate locations and modifications; therefore some fixed graph vertex has positive trifurcation probability. By translation invariance, that probability is a common number $\tau >0$ at every graph vertex.

The decisive deterministic input is the trifurcation boundary-counting lemma. Let $T$ be all these degree-three trifurcation vertices in percolation in a finite box $B_n$. In each infinite percolation cluster meeting $T$, delete the graph vertices of $T$, contract each remaining connected component of a graph adjacent to $T$ to a node, and retain the incidences with the deleted graph vertices, including direct edges between graph vertices of $T$. This is a finite tree: a cycle would connect two neighbours of an original trifurcation vertex in percolation without passing through it, contradicting its three-way separation. Every deleted graph vertex has degree three. Every leaf component is infinite, since a finite leaf would give a finite branch after removing its adjacent trifurcation vertex in percolation. The elementary tree degree identity therefore supplies at least $|T\cap C|+2$ infinite leaf components for a cluster containing $T$.

Each such infinite component reaches the outer graph vertex boundary ${\partial }^{+}{B}_n$, and different components reach different boundary graph vertices. Summing over the clusters yields, in particular,For a nearest-neighbour lattice box,Taking expectations and using the common trifurcation probability givesThis contradicts $\tau >0$ and excludes infinitely many infinite percolation clusters. Thus only $k=0$ or $k=1$ remains:The proof explains the role of the amenable boundary growth of lattice boxes: finite-energy property of Bernoulli percolation would make branching points have positive volume density, while their disjoint infinite branches can only be supplied through a boundary of lower order. It uses no planar duality and works in every indicated dimension.