Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 212 (Random Discrete Structures)

In bond percolation on the square lattice, exactly one of the following occurs in the rectangle: an open left-to-right primal crossing, or a closed top-to-bottom crossing in the planar dual graph. These alternatives are disjoint and exhaustive by planar duality for rectangle crossings.

At $p=1/2$, the closed dual edges have the same law as open primal edges. Rotating the dual rectangle through a right angle identifies its top-to-bottom crossing with the original left-to-right crossing; the slight difference between the side lengths $\ell +1$ and $\ell$ is exactly the boundary shift introduced by dualization. Thus the event and its complement have equal probability, so

Solved by gpt-5.6-sol high.

WriteThe Russo-Seymour-Welsh theorem and the Harris-FKG inequality give the standard one-arm extension estimate: there is $c>0$ such thatuniformly in $r$. Indeed, on the one-arm event to scale $r$, a fixed finite collection of open rectangle crossings in the annulus ${\Lambda }_{2r}\setminus {\Lambda }_r$, each having probability bounded below by RSW, joins that arm to $\partial {\Lambda }_{2r}$; FKG multiplies the lower bounds. Iteration shows that $\pi (ar)$ and $\pi (r)$ are comparable for every fixed $a>0$. This proves the estimate suggested in the hint.

Fix $x\in \partial {\Lambda }_n$ and choose $r=\lfloor n/4\rfloor$. If $0⟷x$, there is an open arm from $0$ to distance $r$ and another from $x$ to distance $r$. These are independent events because they use disjoint edge sets, so the extension estimate gives

For the reverse inequality, take one-arm events from $0$ and $x$ at scale comparable with $n$, in disjoint boxes. A fixed collection of open crossings of rectangles of bounded aspect ratio joins the two arms. The Russo-Seymour-Welsh theorem bounds the probability of every added crossing below uniformly in $n$ and in the position of $x$ along the four sides; the Harris-FKG inequality and the arm-extension estimate therefore giveThis is the usual RSW gluing lemma for two one-arm events. Enlarging the constants handles the finitely many small $n$, proving the claim with positive constants $c_1,c_2$.

Solved by gpt-5.6-sol high.

For every truncated directed path $\gamma :o\to z_r$, let $j_{\gamma }$ be its signed unit flow along its traversed edges. Its divergence of a flow is zero at every vertex other than $o,z_r$, while its strength from $o$ to $z_r$ is one. The displayed expression in the question isIt is a nonnegative linear combination of such path flows. Hence it obeys flow conservation at every interior vertex, is antisymmetric on oppositely directed edges, and is supported on open edges. It is therefore a flow from $o$ to $z_r$ for every configuration $\omega$.

Solved by gpt-5.6-sol high.

The strength of the linear combination is the same linear combination of the unit strengths:Taking expectations cancels each denominator. Since the truncated paths partition the path space,

Solved by gpt-5.6-sol high.

Expanding the square and using the independence of the percolation edges givesThe ratio equals $p^{-N_r(\gamma ,{\gamma }^{\prime })}$, where $N_r$ is the number of common edges in the two truncated paths. It is at most $p^{-N}$ for $N=|\xi \cap {\xi }^{\prime }|$, under the convention in the hypothesis; in particular $N\ge 1$ because both paths contain $o$. For every integer $N\ge 1$,The tail-sum formula and the assumed exponential intersection tail therefore yield

Solved by gpt-5.6-sol high.

Let the energy of a flow be $\mathcal{E}(\theta )={\sum }_e\theta (e{)}^2$, with each unoriented edge counted once. Expanding as in part (i), dropping orientation signs, and summing over common edges givesuniformly in $r$.

Part (i), $\mathbb{E}{X}_r=1$, and the Paley-Zygmund inequality give a constant $a>0$ such that $\mathbb{P}(X_r>1/2)\ge a$ for every $r$. The preceding uniform expectation bound and Markov inequality allow a constant $L$ such thatOn this event, ${\theta }_{\omega }/X_r$ is a unit open flow from $o$ to $z_r$ with energy at most $4L$.

The events that there is such a bounded-energy unit flow from $o$ out of $B(o,r)$ are decreasing in $r$. Their intersection still has probability at least $a/2$. A diagonal compactness argument produces on this intersection a unit flow from $o$ to infinity, supported on its open cluster, with finite energy. The finite-energy flow criterion for transience makes that open cluster transient.

Thus a transient open cluster exists with positive probability. This existence event is a tail event: changing finitely many edges cannot destroy transience in every infinite component, because transience is invariant under finite graph modifications. The Kolmogorov zero-one law upgrades its probability to one.

Solved by gpt-5.6-sol high.

Take an increasing exhaustion $G_n$ of $G$ by finite connected vertex sets, identify every vertex outside $G_n$ to one boundary vertex, and choose a uniform spanning tree of the resulting finite wired graph. The weak limit as $n\to \infty$ is the wired uniform spanning forest of $G$.

For Wilson algorithm rooted at infinity, enumerate $V$ as $v_1,v_2,\dots$. Run a simple random walk from $v_1$ forever and add its chronological loop erasure. Transience makes the infinite loop erasure well-defined. Next, from the first vertex not already in the forest, run an independent random walk until it hits the existing forest; if it never hits, run it forever. Add its loop erasure and continue through the enumeration. Wilson's theorem rooted at infinity says that the resulting forest has the wired uniform spanning forest law.

Solved by gpt-5.6-sol high.

Run Wilson algorithm rooted at infinity with $w_1,\dots ,w_K$ first in the enumeration. Couple its first $K$ walks with the independent walks in the hypothesis. On the positive-probability event that their ranges are pairwise disjoint, no walk from $w_j$ hits any earlier loop-erased range. Wilson's algorithm therefore creates $K$ distinct trees, soThe component-number zero-one law for the wired uniform spanning forest says that its number of trees is almost surely constant; it follows from tail triviality of the wired uniform spanning forest and the fact that all its trees are infinite. The displayed positive probability must consequently equal one.

Solved by gpt-5.6-sol high.

Write ${\tau }_p(x)={\mathbb{P}}_p(0⟷x)$ and $r=1-\chi (p{)}^{-1}$. The percolation susceptibility decomposes over the ${\ell }^1$ spheres asIf ${\mathbb{E}}_p{M}_n>r^n$ for every $n\ge 1$, thena contradiction. Hence some $m\ge 1$ satisfies ${\mathbb{E}}_p{M}_m\le r^m$.

Solved by gpt-5.6-sol high.

Set $a={\mathbb{E}}_p{M}_m={\sum }_{|x|=m}{\tau }_p(x)$. If $|u|\ge m$, an open self-avoiding path from $0$ to $u$ first meets the ${\ell }^1$ sphere of radius $m$ at some $x$. Its portions from $0$ to $x$ and from $x$ to $u$ use disjoint edge sets. The van den Berg-Kesten inequality and translation invariance therefore giveLet $s_k={\sup }_{|u|\ge km}{\tau }_p(u)$. Since $|u-x|\ge |u|-m$, the last inequality gives $s_k\le a{s}_{k-1}$ and $s_0\le 1$. Induction yields

Solved by gpt-5.6-sol high.

For $j=0,\dots ,k-1$, let $E_j$ be the increasing event that $ju⟷(j+1)u$. Their intersection implies $0⟷ku$. By translation invariance and the Harris-FKG inequality,

Solved by gpt-5.6-sol high.

Combine parts (a)--(c). For every $k\ge 1$,Taking $k$th roots and letting $k\to \infty$ gives

Solved by gpt-5.6-sol high.