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 We make a continuous time Markov process by specifying
two adjacent empires A,B may merge into one \( A \cup 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) = \mathbb{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) = \frac{ \min(area(A), area(B))}{\max(area(A), area(B))} \times \frac{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.

Back to Open Problem list