$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
Best Answer
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.)