Empires and percolation: regions merging at a constant rate

Start with the plane divided into unit squares, and let neighbouring regions merge at random, like countries forming empires. If every pair of adjacent regions merges at the same constant rate, does an infinite empire appear after a finite time? Simulations and a non-rigorous argument say yes, and a standard percolation technique "almost" proves it, but the details have never been completed.

Problem

At each time $t \ge 0$ the plane is partitioned into polygonal regions, starting at $t = 0$ from the unit squares of the square grid (or the hexagonal lattice, or a Voronoi tessellation). As time increases, every pair of adjacent regions $A, B$ (sharing a boundary of positive length) merges into the single region $A \cup B$ at rate $\lambda(A, B)$ , independently of everything else. Call the process hegemonic if regions of infinite area appear at some finite time.

Question. For the constant rate $\lambda(A, B) \equiv 1$ for all adjacent $A, B$ , is the process hegemonic?

More generally: give conditions on the rate function $\lambda$ that are sufficient for hegemony, and conditions sufficient for its failure.

Background

Aldous discussed the model with Vlada Limic in 2001 and wrote it up with J. R. Ong and W. Zhou in 2009, under the name empire process. It is a spatial analogue of mean-field coalescence, where the Smoluchowski coagulation equation describes gelation, and of bond percolation, where infinite clusters appear above a critical density. Aldous conjectures that percolation does occur when $\lambda \equiv 1$ ; he notes that the standard Peierls contour method is almost enough to prove it, but the estimates could not quite be completed.

What is known

If $\lambda(A, B)$ equals the length of the common boundary, started from the square grid, the region areas are distributed like bond percolation clusters with $p = 1 - e^{-t}$ ; since the critical probability is $1/2$ , infinite regions appear at time $\log 2$ . More generally, $\lambda(A, B) \ge c\,L(A, B)$ for some $c > 0$ , where $L$ is the boundary length, implies hegemony (Aldous, Ong and Zhou, 2010).
Conversely, if $\sum_j \lambda(A, B_j)\,\mathrm{peri}(B_j) \le C\,\mathrm{peri}(A)$ for every region $A$ with neighbours $B_j$ , the process is not hegemonic.
The constant-rate case falls in the gap between these conditions. A special feature is that each initial boundary segment is still part of a boundary at time $t$ with probability exactly $e^{-t}$ , but these events are dependent.
A non-rigorous analytic argument on the hexagonal lattice and simulations on an $81 \times 81$ grid support hegemony for $\lambda \equiv 1$ (Aldous, Ong and Zhou, 2010).

What would count as progress

A rigorous proof that the constant-rate process is hegemonic, for instance by completing the Peierls contour estimate on the hexagonal lattice, or a proof that it is not.
New sufficient conditions narrowing the gap, for example for rates depending only on the areas of the two regions.
Larger simulations estimating the critical density of empires for $\lambda \equiv 1$ with error bars, to sharpen the numerical evidence.
Proofs that the answer does not depend on the initial tessellation, or that hegemony has probability zero or one, two presumptions made in the original paper.

References

D. J. Aldous, J. R. Ong and W. Zhou, Empires and percolation: stochastic merging of adjacent regions, J. Phys. A 43 (2010), 025001; arXiv:0911.0601.
D. J. Aldous, Random partitions of the plane via Poissonian coloring, and a self-similar process of coalescing planar partitions, arXiv:1701.00131 (2016).

Source

Imported from David Aldous's open problems empires, curated by David Aldous. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.