Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 30 / 2

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.