$N$ points are generated randomly within a unit square, with a uniform distribution. What is the probability that the points form a connected graph, given that two points are connected if the distance between them is less than or equal to $d$? (this should obviously be some function of $N$ and $d$).

If you don't know the answer, but have an idea that may (or may not) lead me a step forward, please let me know as well.

Moreover, if you know for sure that this problem is yet unsolved, that's also good news for me. I can then do it through a Monte-Carlo simulation, but my approach would be justified.

Thanks, Melvin

  • 2
    $\begingroup$ You should look into "random geometric graphs". Mathew Penrose has a monograph with that title. I'll post an answer if I can find the result in his book. $\endgroup$
    – j.c.
    Sep 22 '11 at 19:34
  • $\begingroup$ @Melivn: I wasn't very awake when I wrote this... $\endgroup$ Sep 22 '11 at 20:15
  • $\begingroup$ @Melvin, I think Gjergji Zaimi's answer has the result from Penrose's book whose discussion turned out to be more convoluted than I thought (In chapter 13, Penrose shows that connectivity is asymptotically equivalent to 2-connectivity, for which he showed a threshold in section 7.2...). The bottom line is compute the quantity $\mu$ from $N$ ($n$ in Gjergji Zaimi's notation) and $d$; then up to a constant, the probability of being connected will be asymptotic to $e^{-\mu}$ as $N$ goes to infinity. $\endgroup$
    – j.c.
    Sep 22 '11 at 22:02
  • $\begingroup$ @jc: thanks for the comment. Where is the final result located in Penrose's book please, as I need to reference it? $\endgroup$
    – user18011
    Sep 22 '11 at 23:51
  • 3
    $\begingroup$ Crossposted: math.stackexchange.com/questions/66777/… $\endgroup$
    – user6096
    Sep 23 '11 at 0:56

Just a few more comments to the answers and references already posted. I will denote your graph by $G(n,d(n))$. I'm not sure if this is satisfactory enough, but with fairly standard methods one can prove that if $\mu=ne^{-\pi nd(n)^2}\to 0$ as $n\to \infty$ then the graph is aas connected. In general the probability that $G$ is connected is $\sim e^{-\mu}$. References include the monograph by Penrose mentioned in the comments, the paper by Gupta and Kumar, see also the paper by Penrose "The longest edge of the random minimal spanning tree" The Annals of Applied Probability (1997) 7, 340–361, and M.J. Apple, R.P. Russo "The connectivity of a graph on uniform points on $[0,1]^d$".

Note that the situation in $[0,1]^d$ with metric $\ell_p$ is similar. In fact Goel, Rai, and Krishnamachari proved this for all monotone properties of graphs (like connectivity, non-planarity etc.) "Monotone properties of random geometric graphs have sharp thresholds". (Monotone property here means that it is preserved by addition of edges.)



Clique sizes in a unit disk graph

and references mentioned there... Your graphs are the unit disk graphs of the title.


See http://citeseerx.ist.psu.edu/viewdoc/download?doi=, especially the reference to Gupta/Kumar at the very beginning...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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