Poisson-Voronoi percolation in the hyperbolic plane
with small intensities

We will study percolation on the Voronoi tessellation generated by a homogeneous Poisson point process on the hyperbolic plane $\mathbb{H}^{2}$. That is, with each point of a constant intensity Poisson process on $\mathbb{H}^{2}$ we associate its Voronoi cell – which is the set of all points of the hyperbolic plane that are closer to it than to any other point of the Poisson process – and we colour each cell black with probability $p$ and white with probability $1-p$, independently of the colours of all other cells. See Figure 1 for a depiction of computer simulations of this process.

We say that percolation occurs if there is an infinite connected cluster of black cells. For each intensity $\lambda>0$ of the underlying Poisson process, the critical probability is defined as

To the best of our knowledge, hyperbolic Poisson-Voronoi percolation was first studied by Benjamini and Schramm in the influential paper [9]. Amongst other things, they showed that $0<p_{c}(\lambda)<1/2$ for all $\lambda>0$; that $p_{c}(\lambda)$ is a continuous function of $\lambda$; and that $p_{c}(\lambda)\to 0$ as $\lambda\searrow 0$.

They also asked for the asymptotics of $p_{c}(\lambda)$ as $\lambda\searrow 0$, and specifically for “the derivative at $0$”. Here we answer this question, by showing:

For comparison, Benjamini and Schramm gave an upper bound $p_{c}(\lambda)\leq\frac{1}{2}-\frac{1}{4\pi\lambda+2}$, whose asymptotics are $\pi\lambda+o(\lambda)$ as $\lambda\searrow 0$.

The results of Benjamini and Schramm highlight striking differences between Poisson-Voronoi percolation in the hyperbolic plane and Poisson-Voronoi percolation in the ordinary, Euclidean plane. For starters, in the latter case it is known [50, 10] that the critical probability equals $1/2$ for all values of the intensity parameter $\lambda$. More strikingly perhaps is the difference in the behaviour of the number of infinite, black clusters. In the Euclidean case there are no infinite black clusters when $p\leq 1/2$ and precisely one infinite black cluster otherwise (almost surely). For the hyperbolic case, Benjamini and Schramm showed that if $p\leq p_{c}(\lambda)$ all black clusters are finite; if $p\geq 1-p_{c}(\lambda)$ then there is precisely one infinite black cluster; but if $p_{c}(\lambda)<p<1-p_{c}(\lambda)$ then there are infinitely many, distinct, infinite, black clusters (almost surely).

Related work. Percolation theory is an active area of modern probability theory with a considerable history, going back to the work of Broadbent and Hammersley [12] in the late fifties. By now there is an immense amount of research articles, mostly centered on percolation on lattices. We direct the reader to the monographs [11, 22] for an overview.

Poisson-Voronoi tessellations (mostly in $d$-dimensional, Euclidean space) are one of the central models studied in stochastic geometry. They are studied in connection with many different applications and have a long history going back at least to the work of Meijering [34] in the early fifties. For an overview, see the monographs [37, 39] and the references therein.

In the early nineties, Vahidi-Asl and Wierman [46] introduced first passage percolation (a notion related to, but distinct from percolation as we have defined it above) on planar, Euclidean Poisson-Voronoi tessellations. A few years later, Zvavitch [50] proved that in the Euclidean plane almost surely all black clusters are finite when $p\leq 1/2$ (and $\lambda>0$ arbitrary). About a decade after that Bollobás and Riordan were able to complement this result by showing that, almost surely, there exists an infinite black cluster when $p>1/2$ (and $\lambda>0$ arbitrary) – thus establishing $p_{c}=1/2$ for planar, Euclidean Poisson-Voronoi percolation. Since then planar, Euclidean Poisson-Voronoi percolation, especially “at criticality”, has received a fair amount of additional attention. See e.g. [1, 2, 41, 49]. Poisson-Voronoi percolation on the projective plane was studied by Freedman [17], and Poisson-Voronoi percolation on more general two and three dimensional manifolds was studied by Benjamini and Schramm in [8]. Poisson-Voronoi percolation on higher dimensional Euclidean space has been studied as well, in [4, 3, 15].

Fuchsian groups can be seen as the analogue in the hyperbolic plane of lattices in the Euclidean plane. Lalley [29, 30] studied percolation on Fuchsian groups and amongst other things established that the critical probabilities for “existence” and “uniqueness” of infinite clusters are distinct. Works on continuum percolation models over Poisson processes in the hyperbolic plane include [5, 16, 42, 44, 45]. Aspects of hyperbolic Poisson-Voronoi tessellations besides percolation that have been studied include the (expected) combinatorial structure of their cells, random walks on them and anchored expansions – see for example [6, 7, 13, 19, 26, 27]. Percolation on hyperbolic Poisson-Voronoi tessellations was first studied specifically by Benjamini and Schramm in [9]. In the recent paper [24] the current authors showed that $p_{c}(\lambda)\to 1/2$ as $\lambda\to\infty$ for Poisson-Voronoi percolation on the hyperbolic plane, proving a conjecture from [9].

Comparing Theorem 1 with Isokawa’s formula (stated as Theorem 6 below), we see that our result can be rephrased as : as $\lambda\searrow 0$, the critical probability is asymptotic to the reciprocal of the “typical degree” (defined precisely in Section 2.3 below). A similar phenomenon happens in several Euclidean percolation models when one sends the dimension to infinity. The most well-known result in this direction is probably that for both site and bond percolation on $\mathbb{Z}^{d}$, we have that $p_{c}=(1+o_{d}(1))\cdot(2d)^{-1}$, as was shown concurrently and independently by Gordon [21], Hara and Slade [25] and Kesten [28]. Prior to that there were non-rigorous derivations of the result in the physics literature and Cox and Durret [14] had proved the analogous result for oriented percolation (which is technically easier to analyze). Penrose [36] proved an analogous result for the Gilbert model on $d$-dimensional Euclidean space as the dimension tends to infinity, and Meester, Penrose and Sarkar [33] extended this result to the random connection model. The analogous phenomenon was shown by Penrose [35] for spread out percolation in fixed dimension when the connections get more and more spread out.

Sketch of the main ideas used in the proof. The intuition guiding the proof is that when $\lambda$ is small and $p$ is of the same order as $\lambda$ then black clusters are “locally tree like”, in the sense that while there will be some short cycles in the black subgraph of the Delaunay graph, but these will be “rare”. (The Delaunay graph is the abstract combinatorial graph whose vertices are the Poisson points and whose edges are precisely those pairs of points whose Voronoi cells meet.) This is also the intuition behind the results on high-dimensional and spread-out percolation mentioned above. In fact, in several of the works cited it is in fact shown that if we scale $p$ as a constant $\mu$ divided by the degree (so that the origin has $\mu$ black neighbours in expectation) then the cluster of the origin behaves more and more like a Galton-Watson tree with a Poisson$(\mu)$ offspring distribution as the dimension grows.

Before going further, it is instructive to informally discuss in a bit more detail the situation for the high-dimensional Gilbert model analyzed by Penrose in [36]. In that model, we build a random graph on a constant intensity Poisson process on $\mathbb{R}^{d}$ by joining any pair of Poisson points at distance $<1$ by an edge. We seek the critical intensity $\lambda_{c}$ such that there is a.s. no percolation for $\lambda<\lambda_{c}$ and there is a positive probability of percolation when $\lambda>\lambda_{c}$. We consider the scenario where $d$ is large and the intensity is $\lambda=\mu\cdot\pi_{d}^{-1}$ with $\pi_{d}$ the volume of the $d$-dimensional unit ball and $\mu>0$ a fixed constant. We add the origin $o$ to the Poisson process (note that this a.s. does not change whether or not there is an infinite component), and think of “exploring” the cluster of the origin. We do this in an iterative fashion : we first add the neighbours of the origin to the cluster, then we consider each of these neighbours in turn and add their neighbours to the cluster, and so on. Of course the neighbours of the origin are precisely those Poisson points that fall inside the $d$-dimensional unit ball $B$. In particular their number follows a Poisson distribution with mean $\mu$. Once we have already added some points to the cluster of the origin and we consider the neighbours of a previously added point $u$, we add those Poisson points that fall inside the ball of radius one around $u$ from which we have removed the union of all radius one balls around points we have processed already. Because of the high-dimensional geometry, the volume of this set difference is typically very close to the volume of a unit radius ball with nothing removed – at least during the initial stages of the exploration. In other words, at least during the first few exploration steps, the number of new points that gets added in each exploration step is approximately distributed like a Poisson random variable with mean $\mu$. This naturally leads to the aforementioned connection with Galton-Watson trees with Poisson$(\mu)$ offspring distribution. Essentially, the geometric reason why this works out is the “concentration of measure” for high dimensional balls (see for instance [32], Chapter 13) : in high-dimensional Euclidean space, the volume of the unit ball is concentrated near its boundary. From this one can derive that, in a sense that can be made precise, most pairs of points connected by an edge in the Gilbert graph will have distance close to one. Moreover, the mass of a $d$-dimensional ball is also concentrated near its equator, from which one can derive that – in a sense that can be made precise – for most pairs of points with a common neighbour, their distance will be very close to $\sqrt{2}$ and, more generally, most pairs with graph distance $k$ will have Euclidean distance close to $\sqrt{k}$ (for $k$ fixed).

A similar phenomenon, but maybe even more extreme in a sense, happens in the hyperbolic plane for disks of large radius $r$ : The area of a hyperbolic disk $B$ of large radius $r$ is concentrated near its boundary; and if we take two points at random from $B$ then typically their distance is close to $2r$, the maximal possible distance between any two points in $B$. In the current paper, we consider a Poisson point process ${\mathcal{Z}}$ on the hyperbolic plane with small intensity $\lambda>0$. We again include the origin and try to analyze the black cluster of the Voronoi cell of the origin in the Voronoi tessellation for ${\mathcal{Z}}\cup\{o\}$, where the cell of the origin is coloured black and all other cells are each coloured black with probability $p$ and white with probability $1-p$. By Isokawa’s formula (stated as Theorem 6 below) the expected number of cells that are adjacent to the cell of the origin is asymptotic to $\frac{3}{\pi\lambda}$ as $\lambda$ tends to zero. Moreover, as can be seen either by looking more carefully at Isokawa’s computations or by reading some of our arguments below, it can be shown that most neighbours of the origin are at distance close to $r:=2\ln(1/\lambda)$. Note that $r$ goes to infinity as $\lambda\searrow 0$. Now suppose we take $p=\mu\cdot(\pi/3)\cdot\lambda$ with $\mu$ a constant and $\lambda$ small, so that the expected number of black cells neighbouring the cell of the origin is close to $\mu$. If we follow an exploration process analogous to the one described above for the Euclidean Gilbert model, the black cluster will have the property that most pairs of points at graph distance $k$ have distance close to $2kr$ in the hyperbolic metric.

For the upper bound, we will show that if $p=(1+\varepsilon)\cdot(\pi/3)\cdot\lambda$ and $\lambda$ is sufficiently small (and $\varepsilon>0$ is a fixed constant) then the size of the black cluster of the origin stochastically dominates the size of a supercritical Galton-Watson tree. We will use an exploration procedure similar to what we described above for the high-dimensional Gilbert model. During the exploration, when we consider some point $z$ that has already been added to the tree, we make sure to only add those black neighbours of $z$ whose distance to $z$ is within some large constant of $r$. We also make sure to select a subset $\{z_{1},\dots,z_{k}\}$ of these neighbours with the property that all angles $\angle z_{i}zz_{j}$ are larger than some small constant, and moreover for each $z_{i}$ there is a ball of radius some large (but fixed) constant that contains no other Poisson points. Essentially because of the geometric phenomena described earlier, it will turn out that in this version of the exploration procedure, for sufficiently small $\lambda$, the subgraph of the cluster of the origin we obtain follows the distribution of a certain supercritical Galton-Watson process exactly. In contrast, in the high-dimensional Gilbert model the correspondence between the exploration process and a supercritical Galton-Watson process will eventually break down, after a (large) number of exploration steps that depends on the dimension, so that additional techniques and arguments were needed by Penrose [36].

For hyperbolic Poisson-Voronoi percolation the lower bound is technically more involved than the upper bound. This is probably the most novel contribution in our paper, and we believe it might inspire similar arguments applicable to other problems in percolation, notably for high-dimensional models. For percolation on $\mathbb{Z}^{d}$ and the Gilbert model, a trivial (and “sharp” up to lower order corrections when $d\to\infty$) lower bound is given by a comparison to branching processes : in the former model, the cluster of the origin is stochastically dominated by a Galton-Watson distribution with mean offspring $p\cdot(2d-1)$ and in the latter with mean offspring $\mu\cdot\pi_{d}$. So the critical probability satisfies $p_{c}\geq 1/(2d-1)$, respectively the critical intensity satisfies $\lambda_{c}\geq 1/\pi_{d}$. (For percolation on $\mathbb{Z}^{d}$ this was in fact already observed by Broadbent and Hammersley [12] and for the Gilbert model by Gilbert [18].) In our case a similar argument does not seem feasible. In the Gilbert model, imagine we have explored part of the cluster of the origin and in doing so have revealed the status of the Poisson process in some region. We now wish to add those neighbours that are not yet part of the cluster of a point that we have previously added to in the cluster. The number of new points added is stochastically dominated by the number of new points we add at the very start of the exploration, when add the neighbours of the origin. In the Poisson-Voronoi percolation model there is no obvious monotonicity of this kind. Once we have revealed the status of the Poisson point process in some region this can make new edges both more and less likely. As a side remark, let us mention that using the methods in our paper it ought to be possible to show that when $p=(1-\varepsilon)\cdot(\pi/3)\cdot\lambda$ then, as $\lambda\to 0$, the size of black cluster of the origin will converge in distribution to the size of a Galton-Watson tree with Poisson$(1-\varepsilon)$ offspring distribution. We do not pursue this here however as it does not appear useful for bounding $p_{c}(\lambda)$ : it will not exclude the possibility that – for any fixed, small $\lambda>0$ – there is an extremely small, but positive probability that the origin is in an infinite component.

A naive approach that one might try is to compute the expected number of black paths of length $k$ starting at the origin (for $\lambda$ small and $p=(1-\varepsilon)\cdot(\pi/3)\cdot\lambda$), and hope to show that this expectation tends to zero as $k\to\infty$. Unfortunately this approach does not seem feasible either. Long paths might revisit the same area many times which introduces dependencies that are difficult to deal with.

In order to circumvent this issue, we introduce what we call linked sequences of chunks. As we wish to show percolation does not occur, it suffices to show no infinite black cluster exists with a more generous notion of adjacency, in the form of what we call pseudo-edges, that makes the analysis simpler. With each pseudo-edge we associate a “certificate”, being the region of the hyperbolic plane that needs to be examined to verify it is indeed a pseudo-edge. We’ll say a pseudo-edge on a path $P$ is good if it has length close to $r$ and does not make a small angle with the previous pseudo-edge. Otherwise it is bad. A linked sequence of chunks is a sequence of paths $P_{1},\dots,P_{n}$ such that: 1) on each path, every pseudo-edge except the last is good and the last is bad, and 2) for each $i\geq 2$, either the first point of $P_{i}$ is close to the certificate of some pseudo-edge of $P_{i-1}$ or the certificate of the first pseudo-edge of $P_{i}$ intersects one of the certificates of $P_{i-1}$, and for every other pseudo-edge of $P_{i}$ its certificate is disjoint from all certificates of all pseudo-edges on $P_{1},\dots,P_{i-1}$. We’ll first show (Proposition 31 below) that if the cluster of the origin is infinite, then either there exists an infinite path all of whose edges are good, or there exists an infinite linked sequence of chunks starting from the origin. Unlike paths in general, it is technically feasible to give decent bounds on the expected number of good paths, respectively the number of linked sequences of chunks, of some given length $n$. We are able to obtain bounds that tend to zero with $n$, which implies no percolation occurs a.s.

Structure of the paper. In the next section, we collect some notations, definitions, facts and tools that we will need in our proofs. Section 3.1 contains some preparatory geometric observations needed in later sections. Section 3.2 contains the proof that $p_{c}(\lambda)\leq(1+\varepsilon)\cdot(\pi/3)\cdot\lambda$ for small enough $\lambda$ (and $\varepsilon>0$ fixed), and Section 3.3 contains the proof that $p_{c}(\lambda)\geq(1-\varepsilon)\cdot(\pi/3)\cdot\lambda$ for small enough $\lambda$. We end the paper by suggesting some directions for further work in Section 4.