Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Take a random configuration of $n$ non-overlapping discs of radius $r$ in the unit square $[0,1]^2$. (You could think of this as taking $n$ points uniform randomly in $[r,1-r]^2$ and then restricting attention to the case that every pair of points $\{ x,y \}$ satisfies $d(x,y) \ge 2r$.)

From the point of view of statistical mechanics, the interesting case is when $r^2 n \to C$ for some constant $C > 0 $ as $n \to \infty$, and various kinds of phase transitions have been studied experimentally, but little seems known mathematically.

What I am wondering about is whether anyone has studied the following kind of percolation. Set $\lambda >1$ to be a fixed parameter to measure proximity. Define a graph by considering the centers of the $n$ discs to be the vertices, and connecting a pair $\{ x,y \}$ by an edge whenever $d(x,y) < 2 \lambda$.

My question is: given some choice of $\lambda$ does there exist a critical threshold $C_t$ (depending on $\lambda$) such that whenever $C > < C_t$ all the connected components of this graph are likely to be small, of order $O(\log n)$ or even $o(n)$, and whenever $C > C_t$ there is a giant component, of order $\Omega(n)$?

What I know about is that for geometric random graphs on i.i.d. random points, percolation is known to occur for fairly general distibutions, and that this is closely related to bond percolation on a lattice. But in the hard spheres distibution points are far from being independent.

I would also be interested to hear about percolation on other kinds of repulsive point processes -- Matern, Strauss, etc.

share|improve this question
What's typically known as "continuum percolation" is an overlapping disc model. This isn't quite what you're asking about, but it might be a good place to start. See the book Continuum Percolation by Meester and Roy, or the continuum percolation chapter in Grimmett's Percolation. –  Tom LaGatta Oct 1 '10 at 15:56
Thanks Tom, I'll look into it. –  Matthew Kahle Oct 1 '10 at 17:19
This paper arxiv.org/abs/1110.0527 reports on simulations on a related but different model. Instead of hard disks, they consider 2D disks with a short range harmonic repulsion, and this allows them to consider only the case $\lambda=r$ in your notation. Interestingly, they find a percolation threshold at $\phi_P\approx0.558$, well below the onset of rigidity (jamming) at $\phi_J\approx0.84$, and they seem to find some exponents which agree with continuum percolation. –  j.c. Oct 5 '11 at 9:32
add comment

2 Answers

This kind of question is an active area of research. I don't think the answer to your question is known, but here are the two most closely-related bits of research I'm aware of.

(1) A Poisson hard-sphere process in $\mathbb{R}^d$ is a set $S$ of spheres with non-overlapping interiors whose centres form a homogeneous Poisson process in $\mathbb{R}^d$. (The spheres are allowed to have differing diameters.) It is invariant if $S+z$ and $S$ have the same distribution for all $z \in \mathbb{R}^d$. Cotar, Holroyd and Revelle show that for all $d \geq 45$, there exists a translation-invariant Poisson hard-sphere process $\Lambda$ which percolates (contains an infinite connected component) almost surely. If you look at their proof, it seems that in fact they show the existence of such a process with the additional property that no sphere has radius larger than $K$ for some non-random $K=K(d)$.

(2) The lilypond model consists in simultaneously growing balls at unit speed around each point, with each ball ceasing to expand when it touches another ball. Häggström and Meester showed that the lilypond model on a homogeneous Poisson point process doesn't percolate. More recently, Last and Penrose showed that in $d \geq 2$, there exists a critical constant $\lambda_c(d)$ such that if you enlarge all balls by a proportion at least $\lambda > \lambda_c(d)$ then there is percolation with probability one, and below $\lambda_c(d)$ there is no percolation with probability one.

share|improve this answer
@Louigi: your links are mismatched and the Last and Penrose one points to the https and not the http. –  Ori Gurel-Gurevich Oct 2 '10 at 5:33
Thanks Ori! Fixed. –  Louigi Addario-Berry Oct 2 '10 at 10:29
add comment

Perhaps you are already aware of asymptotics for component sizes in the continuum percolation model. It is there in the book of M. Penrose.

Since you asked about percolation on repulsive point processes, here is a compressed version of our results of non-trivial phase transition on sub-Poisson point processes , point processes that are less clustered than a Poisson in a certain sense. Our main example is a perturbed lattice. We also show that stationary determinantal point processes have a non-zero critical intensity as regards percolation. I think these point processes can be considered as repulsive point processes.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.