Probability of Generating a Connected Graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T18:35:07Z http://mathoverflow.net/feeds/question/76153 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76153/probability-of-generating-a-connected-graph Probability of Generating a Connected Graph Melvin Gauci 2011-09-22T19:32:08Z 2011-09-22T23:51:03Z <p>$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$).</p> <p>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.</p> <p>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.</p> <p>Thanks, Melvin</p> http://mathoverflow.net/questions/76153/probability-of-generating-a-connected-graph/76155#76155 Answer by Igor Rivin for Probability of Generating a Connected Graph Igor Rivin 2011-09-22T19:36:49Z 2011-09-22T19:56:22Z <p>See </p> <p><a href="http://mathoverflow.net/questions/75030/clique-sizes-in-a-unit-disk-graph" rel="nofollow">http://mathoverflow.net/questions/75030/clique-sizes-in-a-unit-disk-graph</a></p> <p>and references mentioned there... Your graphs are the unit disk graphs of the title.</p> <p><strong>EDIT</strong></p> <p>See <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.4866&amp;rep=rep1&amp;type=pdf" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.4866&amp;rep=rep1&amp;type=pdf</a>, especially the reference to Gupta/Kumar at the very beginning...</p> http://mathoverflow.net/questions/76153/probability-of-generating-a-connected-graph/76164#76164 Answer by Gjergji Zaimi for Probability of Generating a Connected Graph Gjergji Zaimi 2011-09-22T21:12:28Z 2011-09-22T21:12:28Z <p>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 <a href="http://www.sciencedirect.com/science/article/pii/S016771520200233X" rel="nofollow">"The connectivity of a graph on uniform points on $[0,1]^d$"</a>.</p> <p>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.) <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aoap/1133965771" rel="nofollow">"Monotone properties of random geometric graphs have sharp thresholds"</a>. (Monotone property here means that it is preserved by addition of edges.)</p> http://mathoverflow.net/questions/76153/probability-of-generating-a-connected-graph/76170#76170 Answer by unknown (google) for Probability of Generating a Connected Graph unknown (google) 2011-09-22T23:51:03Z 2011-09-22T23:51:03Z <p>@jc: thanks for the comment. Where is the final result located in Penrose's book please, as I need to reference it?</p>