Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 15 3 ii Solution Created 2026-10-03 Updated 2026-10-14
We first specify the standard hypotheses of percolation uniqueness on an amenable quasi-transitive graph. A locally finite graph has finite degree at every vertex; a quasi-transitive graph, or graph of finite type, has finitely many vertex orbits under the acting group of graph automorphisms. Here the site percolation law is invariant under and independent, with one parameter for each orbit. Initially suppose . This gives the finite-energy property of Bernoulli percolation: conditional on all states outside any finite set, every assignment inside that set has positive probability. An amenable graph has finite sets with , where denotes the external vertex boundary. Finite type bounds the degrees uniformly, so internal and external boundary conventions are equivalent here.
Let be the number of infinite percolation clusters, taking values in . Each event is invariant. Part (i), together with countability of these possibilities, shows that is an almost-sure constant.
Suppose first that this constant is a finite integer . Some finite connected set meets all infinite percolation clusters with positive probability, since increasing finite sets exhaust the graph. Make every vertex of open. This joins all the infinite clusters. Opening a finite set cannot produce a new infinite cluster from finite clusters: only finitely many clusters meet its finite boundary, and their finite union is finite. By the finite-energy property the modified event has positive probability, contradicting the almost-sure value . Thus a finite must be or .
Suppose instead that almost surely. Some finite connected set meets three distinct infinite percolation clusters with positive probability. Open all of . Its vertices belong to one open cluster, and deleting from that cluster leaves at least three infinite components. This is an encounter box in percolation. We use boxes rather than assume that the local geometry permits a single trifurcation vertex in percolation.
Here is the boundary-counting contradiction in detail. Translates of have the same positive encounter probability. Finite type and bounded degree allow a deterministic packing of mutually disjoint such translates whose centers have positive lower density in the interiors of the Følner sets : every vertex is within a fixed distance of one chosen orbit, and a bounded-radius greedy packing discards only a bounded number of possible centers per chosen center. Boundary layers of any fixed thickness have size . The expected number of encounter boxes wholly inside is consequently at least for a fixed and all large .
On the other hand, contract the open encounter boxes in each cluster to vertices and retain the part inside . Each contracted encounter box separates at least three branches that run to infinity, and each branch must leave . Choose a minimal forest connecting all these boundary exits. Every encounter junction has degree at least three in that forest: its three infinite branches remain in different components after deleting the junction, so none can be omitted. The leaves are boundary exits. For each nontrivial tree, the degree-sum identity gives at most the number of leaves minus two vertices of degree at least three. Thus the number of encounter boxes is at most a constant times , where the constant accounts for the bounded boundary degrees. Taking expected values contradicts amenability. This excludes and provesThere is a genuine endpoint qualification if different orbit parameters are allowed to be or . Subdivide each horizontal edge of the square lattice once. Open every original vertex deterministically and close every new midpoint deterministically. This is an invariant independent law on an amenable graph that is also a quasi-transitive graph, but its infinite open clusters are the distinct vertical columns. Thus the finite-energy property must be included when interpreting a general vector . The homogeneous endpoint laws themselves cause no problem: they give zero or one infinite cluster.
The conclusion is false for -independent laws, even with all site marginals equal to . Here is a fully specified monochromatic line-graph percolation counterexample. Form a graph by replacing each vertex of by a complete graph on ten vertices and putting every possible edge between the blocks of two neighboring lattice vertices. Every vertex of has degree . The graph is connected, periodic and amenable: a square of blocks has volume of order and boundary of order . Assign independent fair red/blue colors to the vertices of .
Call a block good when it contains both colors. Good-block indicators are independent, withThey percolate. To verify this without presupposing a site threshold, put . A finite nearest-neighbor good-block cluster around a good origin is surrounded by a circuit of bad blocks in the matching square graph, where horizontal, vertical and diagonal neighbors are allowed. A surrounding circuit of length has an anchor within . Overcounting its choices by gives the Peierls argumentThe sum bound follows directly from , with . An infinite good-block cluster therefore exists with positive probability, and by part (i) it exists almost surely. Inside each of its blocks the red vertices are connected to one another, as are the blue vertices; between adjacent good blocks the complete bipartite joining edges connect each color. Hence has both an infinite red component and an infinite blue component almost surely.
Now use site percolation on , the line graph of : its vertices are the edges of , two adjacent when they share an endpoint. Declare such a site open exactly when have the same color. Each site has open probability . Sets of sites at graph distance greater than one involve disjoint sets of underlying color variables, so this is a translation-invariant -independent law. The line graph is again connected, locally finite, amenable and of finite type. The infinite red and blue components of yield infinite open clusters in . An open path in cannot change color at a shared endpoint, so those two clusters are distinct. Thus almost surely. Local color constraints destroy the finite-energy property, precisely the ingredient missing from the uniqueness proof.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 15 4 i Solution Created 2026-10-03 Updated 2026-10-14
Let be the martini lattice and its planar dual graph. Write and . Both are periodic, connected, bounded-degree plane graphs with bounded face sizes. Dual bond percolation declares a dual bond open exactly when its crossing primal bond is closed, giving independent dual parameter .
First, . Suppose instead that the sum exceeds , and choose . Both the primal model at and the dual model at are strictly subcritical. Sharpness of the percolation transition gives exponential connection-radius decay on each periodic graph, uniformly over its finitely many vertex types. A crossing of a rectangle of side lengths proportional to starts at one of boundary vertices and travels distance of order . A union bound therefore shows that each crossing probability tends to zero. But planar duality for rectangle crossings says that exactly one of an open primal left-to-right crossing and an open dual top-to-bottom crossing occurs, using the complementary boundary convention. Their probabilities sum to . This contradiction proves the first inequality.
For the opposite inequality, we need noncoexistence of primal and dual infinite percolation clusters. The four-fold version in Q3(iii) cannot be assumed without change: this decorated honeycomb lattice has three-fold rotation symmetry. Here is the necessary three-fold symmetric primal-dual noncoexistence argument.
Assume both models percolate at complementary parameters . For a large disc, the probability of having no exterior infinite arm is at most in each model. Divide its boundary into six arcs by splitting each -degree sector at the same relative angle. In the primal model let be the failure probabilities for the two alternating arc types. Rotation symmetry and the FKG inequality giveSlide the splitting point across one sector. Initially the first arc is empty; finally the second is empty. A jump occurs only when an arc gains or loses an edge-crossing point. An arm using that point requires its crossing bond to be open. The FKG inequality therefore ensures that a failure probability changes by at most a factor at a single jump: for a newly added arm event , and . At the first reversal of the order of , their ratio is consequently at most . At that splitting point,Thus every one of the six primal arcs has an exterior arm with probability tending to . On the same six arcs the dual failure probabilities satisfy , so at least one dual arc type has failure at most ; its three rotations have the same bound. Take two of those dual arcs separated by one arc, and the two intervening primal arcs. A union bound gives four alternating primal/dual infinite exterior arms with positive probability when is sufficiently small. The separation and finite-closure argument of Q3(iii), together with percolation uniqueness on an amenable quasi-transitive graph, gives a contradiction. This proves noncoexistence. The arc balancing is the extra step needed for three-fold symmetry; it is also developed in Bollobás and Riordan's original paper on dual lattices.
If , choose . Both complementary models would then percolate, contradicting noncoexistence. Hence . Combining the two inequalities proves the dual threshold relation: