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

A cylinder event in $\{0,1{\}}^{E(G)}$ is an event determined by the states of finitely many edges. It is increasing when $\omega \in A$ and ${\omega }^{\prime }\ge \omega$ coordinatewise imply ${\omega }^{\prime }\in A$.

Let ${\mu }_n$ be the uniform spanning tree measure on the finite connected induced graph $G_n$. Uniform spanning-tree edge indicators are negatively associated: increasing events depending on disjoint edge sets have nonpositive covariance. Together with the spatial Markov property, this implies the free-boundary monotonicity under graph enlargement: for every increasing cylinder event $A$, ${\mu }_n(A)$ is eventually nonincreasing once $G_n$ contains all edges on which $A$ depends.

Define the free uniform spanning forest measure byfor increasing cylinder events. These limits determine a unique probability measure, independent of the exhaustion; equivalently, ${\mu }_n$ converges weakly to ${\mu }_F$ on the product space.

Fix a finite nonempty vertex set $K$. Once $G_n$ contains $K$ and every edge incident to it, every spanning tree of $G_n$ contains an edge of the finite cutbecause otherwise $K$ is disconnected from the rest of $G_n$. Henceand the same holds in the weak limit. If the free spanning forest had a finite component, its vertex set would be some finite connected $K$ and all edges of ${\partial }_{E}K$ would be absent. Taking the countable union over finite $K$ proves that every component is infinite almost surely.

Because $T$ itself is a tree, every finite induced connected exhaustion has the unique spanning tree consisting of all its edges. Thus its free spanning forest is deterministically $T$.

By the stated transience criterion, choose an edge $e=uv$ whose two complementary subtrees are transient. Run Wilson algorithm rooted at infinity first from $u$. With positive probability its loop-erased walk remains forever in the $u$-side. Starting next from $v$, there is likewise positive conditional probability that its walk remains forever in the $v$-side. On this event the two rays never use $e$, so $e$ is absent from the wired uniform spanning forest. The wired law is therefore not the deterministic free law.

Fix $ϵ>0$ and choose a cylinder event $B$ with ${\mathbb{P}}_p(A△B)<ϵ$. Translate $B$ far enough that $B$ and $\varphi (B)$ depend on disjoint edge sets. They are independent, while automorphism invariance gives $\varphi (A)=A$. The symmetric-difference inclusion supplied in the question givesAlso $|{\mathbb{P}}_p(A)-{\mathbb{P}}_p(B)|<ϵ$, and independence gives ${\mathbb{P}}_p(B\cap \varphi (B))={\mathbb{P}}_p(B{)}^2$. Letting $ϵ\downarrow 0$ yieldsso ${\mathbb{P}}_p(A)\in \{0,1\}$.

The number $N_{\infty }$ is invariant under lattice automorphisms, so part a makes it almost surely equal to one constant in $\{0,1,2,\dots ,\infty \}$. For $p>p_c$ the constant is nonzero.

Suppose it were a finite $k\ge 2$. As boxes increase to ${\mathbb{Z}}^d$, with positive probability one box meets all $k$ infinite clusters. On that event, open a finite collection of edges inside the box joining those clusters. The finite-energy property of Bernoulli percolation gives the modified event positive probability, but it has fewer than $k$ infinite clusters. This contradicts almost-sure constancy. Hence the only possibilities are

The open descendants of any vertex form a Galton-Watson process with offspring distribution $\mathrm{Bin}(k,p)$. If $kp\le 1$, it dies out almost surely, so $N_{\infty }=0$.

If $kp>1$, let $\theta >0$ be its survival probability. At level $n$, each vertex begins an independent descendant subtree; the event that its edge to its parent is closed while its descendant open cluster is infinite has probability $(1-p)\theta >0$. Thus the number of such vertices at level $n$ is binomial with $k^n$ trials and a fixed positive success probability. For every fixed $M$, the probability of at least $M$ successes tends to one. Their infinite clusters are separated by their closed parent edges, so $\mathbb{P}(N_{\infty }\ge M)=1$ for every $M$, and hence $N_{\infty }=\infty$ almost surely.

The van den Berg-Kesten inequality says that for increasing cylinder events $A$ and $B$ under product bond percolation,where $A\square B$ is the event that $A$ and $B$ have disjoint finite witness edge sets.

Let $A_n$ be the increasing cylinder event that an open path joins $0$ to the boundary of the box $[-n,n{]}^d$. If two edge-disjoint open paths run from $0$ to infinity, then $A_n\square A_n$ occurs for every $n$. Therefore the van den Berg-Kesten inequality giveswhere continuity from above identifies ${\lim }_n{\mathbb{P}}_p(A_n)=\theta (p)$.

For $\omega \in \{0,1{\}}^{E(G)}$, write $o(\omega )$ and $c(\omega )$ for its numbers of open and closed edges and $k(\omega )$ for the number of connected components of the open spanning subgraph. The free random-cluster model is

Put $s=1-p$. On the four-cycle, the total unnormalized weight isThe event $N\leftrightarrow S$ contains all configurations with zero or one closed edge and exactly two of the six configurations with two closed edges, so its weight isDivide numerator and denominator by $q$. As $s\to 0$ and $sq\to \infty$, the omitted numerator terms are $o(1+2s^{2}q)$, while the middle denominator terms areConsequently

Take $A=\{N\leftrightarrow S\}$ and let $s=1-p\downarrow 0$ withThen $sq\to \infty$, $s^{2}q\to 0$, and $s^4{q}^3=s^{-1/2}\to \infty$. Part d gives ${\mathbb{P}}_{\mathrm{FK}}^{p,q}(A)\to 0$.

On a four-cycle, $A\square A$ occurs exactly when all four edges are open, because the two length-two paths from $N$ to $S$ are the only disjoint witnesses. HenceChoosing $s$ sufficiently small gives the two numerical inequalities in the question.

Project $X$ to its label in ${\mathbb{Z}}^2$. At each step the label makes a nearest-neighbor move with probability $4/5$ and holds with probability $1/5$ when $X$ crosses between layers. This lazy planar random walk is recurrent because ordinary random walk on ${\mathbb{Z}}^2$ is recurrent.

Whenever the label returns to that of $x_0$, the layer coordinate belongs to a two-state irreducible chain, and there is a uniformly positive chance to equal the original layer. Infinitely many label returns therefore give infinitely many returns to $x_0$. Thus simple random walk on $G$ is recurrent.

The Aldous-Broder algorithm starts the recurrent random walk at $x_0$ and, whenever it first visits a vertex $v\ne x_0$, adds the edge by which it entered $v$. Recurrence ensures that every vertex is eventually visited. The collection of first-entrance edges is a spanning tree and has the infinite-volume uniform spanning-tree law.

Fix a simple path of 2022 vertices in the first layer. The event that all its edges belong to the uniform spanning tree has positive probability: a finite acyclic edge set can be extended to a spanning tree in every sufficiently large finite exhaustion, and the transfer-current determinant for that forest has a positive infinite-volume limit.

The event that $T_1$ has a component of size at least 2022 is invariant under translations of ${\mathbb{Z}}^2$. The uniform spanning-tree law on this transitive recurrent graph is translation ergodic, so an invariant event of positive probability has probability one. Therefore $T_1$ almost surely has such a component.

The event that $T_1$ is connected is translation invariant and hence has probability zero or one. Layer-exchange symmetry gives the same probability for connectivity of $T_2$. If $T_1$ were connected almost surely, both induced forests would therefore be connected almost surely.

On that event the spanning tree must contain exactly one vertical edge: it needs at least one to join the two layers, while two vertical edges together with the unique paths inside the connected $T_1$ and $T_2$ would form a cycle. But a translation-invariant random set cannot contain exactly one vertical edge almost surely. Every specified vertical edge would have probability zero of being the unique one, and their countable union would still have probability zero. This contradiction proves that $T_1$ is almost surely not connected.