Welcome to MathOverflow

Question

7

$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. I'm will try anything sensible.

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

edited Sep 22 2011 at 21:13

Gjergji Zaimi
37.5k●2●72●149

asked Sep 22 2011 at 19:32

Melvin Gauci
73●3

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. – jc Sep 22 2011 at 19:34

@Melivn: I wasn't very awake when I wrote this... – Thierry Zell Sep 22 2011 at 20:15

@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. – jc Sep 22 2011 at 22:02

2

Crossposted: math.stackexchange.com/questions/66777/… – Byron Schmuland Sep 23 2011 at 0:56

Gjergji Zaimi · Accepted Answer · 2011-09-22 21:12:28Z UTC

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.)

Igor Rivin · Answer 2 · 2011-09-22 19:56:22Z UTC

See

http://mathoverflow.net/questions/75030/clique-sizes-in-a-unit-disk-graph

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

EDIT

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

unknown (google) · Answer 3 · 2011-09-22 23:51:03Z UTC

0

@jc: thanks for the comment. Where is the final result located in Penrose's book please, as I need to reference it?

answered Sep 22 2011 at 23:51

unknown (google)
93●3

	As I described, it's kind of spread out over several chapters of the book, so your question is a bit hard to answer. Penrose never explicitly states the threshold for connectedness, he just relates it in chapter 13 to another threshold (for connectivity) that he found in chapter 7. In any case, I suggest you take a look at the book and see what you can get out of it. Alternatively, you might look at the sources that Gjergji Zaimi mentioned to see if they might be easier to follow. – jc Sep 23 2011 at 0:48
	On another note, assuming you are Melvin Gauci, if you register a MathOverflow account and ask the moderators to merge your accounts, you will be able to add comments to your question, which is a more appropriate place to discuss this. – jc Sep 23 2011 at 0:49

Probability of Generating a Connected Graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.