### Empires and Percolation

Consider a partition of the plane into polygonal sets (which we'll call empires). Two empires (say A and B) are adjacent if they share a non-trivial boundary line. We will consider processes whose (only) qualitative dynamics is
• two adjacent empires A,B may merge into one (A union B).
We make a continuous time Markov process by specifying
• two adjacent empires A,B may merge into one (A union B) at stochastic rate r(A,B)
where r(A,B) depends only on the geometry of A and B. Such a process can be started at time 0, either by a regular configuration (squares or triangles or hexagons) or by the Voronoi tesselation associated with a Poisson point process. Say the process percolates if at some finite time there exist infinite empires.

PROBLEM. Give conditions on the rate function r which are sufficient for percolation, and give conditions on the rate function r which are sufficient for non-percolation.

PROBLEM. In particular, for r = 1 does percolation occur?

DISCUSSION. On one hand, the particular case
(1) r(A,B) = length of boundary between A and B
is essentially just the usual bond percolation process on the planar dual graph, and so percolation does occur. On the other hand, consider a statistic such as

• s(t) = E (area of empire containing typical point)
at time t. To prove non-percolation it is enough to prove (d/dt) s(t) = O(s(t)) and this holds for e.g.
(2) r(A,B) = min(area(A), area(B))/max(area(A), area(B)) \times 1/N(A,B)
where N(A,B) is the number of empires adjacent to A or B.

History. Problem discussed with Vlada Limic in 2001. In the case r = 1 we conjecture that percolation does occur. This case has the special property that each piece of the original (t = 0) boundary is present at time t with probability $e^{-t}$. The standard Peierls contour method is almost enough to prove this conjecture, but we could never quite finish the details of the estimates.

Update (10/2009). The preceding material has been written up as this short paper but the problems remain open.

Update (6/2017). A related process is studied in Random partitions of the plane via Poissonian coloring, and a self-similar process of coalescing planar partitions.