Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 13 / 6

The Harris lemma says that, in any finite product of independent Bernoulli coordinates, two increasing events satisfyThe coordinates need not have the same parameter. For completeness, the same statement for increasing functions follows by induction on the number of coordinates. Conditional on the last bit, induction makes the conditional covariance nonnegative; the covariance of the two conditional means is $p(1-p)(a_1-a_0)(b_1-b_0)\ge 0$. The covariance decomposition proves the induction step. Complementing both events gives the inequality for decreasing events too. Finite-cylinder approximation extends it to the countable product setting when needed.

For increasing events $A_1,\dots ,A_r$ of a common probability $a$, their decreasing complements giveTherefore the nth root trick isThis is a lower bound for an individual success probability when a symmetric union is very likely. Without equality of the individual probabilities, the conclusion applies to their maximum. Independence among the $A_j$ is not required.

Let $T$ be the torus graph $(\mathbb{Z}/(5n)\mathbb{Z}{)}^2$, with independent bond density $p$. For $n$ large, all rectangles below are too small to identify any of their own vertices or edges. Let $E_n$ be the event that somewhere in $T$ there is a horizontal open crossing of a $4n$ by $n$ rectangle or a vertical open crossing of an $n$ by $4n$ rectangle. It is increasing and invariant under translations and a quarter turn. These symmetries act transitively on all $50n^2$ bonds, including both orientations. Thus it is a transitive increasing event.

A fixed $4n$ by $n$ rectangle has its ordinary planar distribution, so the supplied lower bound gives ${\mathbb{P}}_{1/2}^T(E_n)>c_4$. Choose any $0<\eta <\min (c_4,1/2)$. Since $p-1/2>0$ is fixed and $\log (50n^2)\to \infty$, the Friedgut-Kalai sharp threshold theorem implies ${\mathbb{P}}_p^T(E_n)>1-\eta$ for all sufficiently large $n$. As $\eta$ is arbitrary,It remains to transfer this symmetric statement to a fixed rectangle, without a growing union-bound loss. On each circular coordinate take the ten positions $a_j=\lfloor jn/2\rfloor$, $0\le j<10$. Consecutive circular gaps are at most $\lceil n/2\rceil$. Use the one hundred $3n$ by $2n$ rectangles starting at pairs $(a_i,a_j)$ and their one hundred quarter-turn images. Every crossed $4n$ by $n$ rectangle contains the full horizontal width of one of the first family, with its vertical span contained in that rectangle's height-$2n$ span: the permissible starting intervals in each coordinate have length $n$, so the chosen positions always supply a suitable start. The crossing, restricted between those two vertical sides, gives a crossing of the chosen $3n$ by $2n$ rectangle. The analogous assertion holds in the rotated family.

Consequently $E_n$ implies at least one of these two hundred increasing crossing events. Their common success probability is $a_n=h_p(3n,2n)$. The nth root trick givesOnly two hundred translates are used, independently of scale. This bounded exponent is the essential finite-torus crossing amplification step.

For a requested height $N$, set $s=\lfloor N/2\rfloor$. Glue $k$ width-$3s$, height-$2s$ rectangles, each successive pair overlapping in a square of side $2s$. Their horizontal crossings and the $k-1$ vertical overlap crossings imply a crossing of the union, which has width $(k+2)s$. An overlap square has crossing probability at least $a_s=h_p(3s,2s)$. Thus the Harris lemma givesChoose $k$ fixed and large enough that $(k+2)s\ge \lambda N$ for all sufficiently large $N$. Increasing height and shortening width can only help, so uniformly for $m\le \lambda N$,In particular it exceeds $1-\epsilon$ for every sufficiently large $N$, with the bound depending only on $p,\lambda ,\epsilon$.

Put $q=1-p_0$. In one-independent bond percolation, bond states in two sets with disjoint endpoint sets are independent as collections. In particular, the states of any finite matching in a graph are mutually independent, by induction on its size. Neither translation invariance nor the Harris lemma is assumed for this law.

If the origin's open cluster is finite, the outer boundary of the union of its vertex-centered unit squares contains a closed dual circuit surrounding the origin. A specified circuit of length $\ell$ corresponds to $\ell$ distinct closed primal bonds. Partition those bonds into four matchings in a graph: horizontal bonds according to the parity of the left endpoint's horizontal coordinate, and vertical bonds according to the parity of the lower endpoint's vertical coordinate. Some class has at least $\ell /4$ bonds. Their mutual independence and their individual closed probabilities at most $q$ implyThis is the Peierls circuit bound for one-independent percolation.

There are at most $4\ell 3^{\ell }$ dual circuits of length $\ell$ enclosing the origin. To obtain this crude bound, choose a crossing of the positive horizontal ray; its distance from the origin is at most $\ell$, since the circuit also extends to the other side of the origin. There are at most $\ell$ choices for its dual edge, at most two orientations, and at most three choices at each subsequent step of a nonbacktracking walk. The stated bound allows extra slack and overcounting. The union bound now givesFor instance choose $p_0=1-10^{-8}<1$, so $x=3q^{1/4}=0.03$. The exact sum isIt follows that $\tilde{\mathbb{P}}(|C_0|=\infty )>0$. This deliberately nonoptimal constant suffices for existence of a universal $p_0$.

Fix $p>1/2$, and use separated-block percolation renormalization to apply the preceding one-independent bond percolation result. Place a squareat each coarse vertex $v\in {\mathbb{Z}}^2$. For a horizontal coarse edge $e=\{v,v+(1,0)\}$, let $R_e$ be the width-$5n$, height-$2n$ rectangle joining the two endpoint squares. Declare $e$ good if $R_e$ has a horizontal open crossing and both endpoint squares have vertical open crossings. For vertical coarse edges use the rotated definition.

The rectangle crossing in bond percolation limit proved above shows that each of these three events has probability tending to one. The Harris lemma givesChoose $n$ so large that every coarse bond has good probability at least the $p_0<1$ from the preceding part.

The good-bond process really is one-independent. Its determining bonds lie entirely in the corresponding $R_e$. Nonincident horizontal coarse edges either lie in rows separated by at least $3n$, while their strips have width $2n$, or in the same row separated by at least one coarse edge; their rectangles are then separated by at least $n$. The vertical case is identical. A horizontal rectangle and a vertical rectangle can intersect only if the horizontal edge's endpoint column is the vertical edge's column and the vertical edge has an endpoint in the horizontal edge's row, which would make the coarse edges incident. Thus sets of nonincident coarse edges use disjoint fine-bond sets, and those sets are independent. The positive gap avoids the shared-boundary-bond problem that occurs with touching block constructions.

An infinite good coarse cluster produces an infinite connected fine open set. To verify connectivity, a long horizontal crossing of $R_e$ contains a horizontal crossing of each endpoint square. It therefore meets every vertical crossing of that square. For collinear good edges the transverse crossing of their shared square joins their long crossings; for perpendicular good edges their long crossings meet inside the shared square. Concatenating along the coarse cluster gives a connected open fine set visiting boxes at arbitrarily large distances.

The one-independent result gives positive probability that the coarse origin belongs to an infinite good cluster. On this event some vertex of the finite square $S_0$ belongs to an infinite fine open cluster. The union bound and translation invariance of the original independent law implyso $\theta (p)>0$. Since this holds for every $p>1/2$, and the Harris theorem for square-lattice bond percolation gives $\theta (p)=0$ for $p\le 1/2$, we obtain the Harris-Kesten theorem: