# Probability of Generating a Connected Graph on the Unit Square

$N$ points are generated randomly on the unit square, with a uniform distribution. What is the probability that they form a connected graph, given that two points are connected iff the distance between them is less than or equal to $d\in(0,\sqrt{2})$?

This should obviously be some function of $N$ and $d$.

-
Instead of a graph, one can think of this as generating discs of diameter $d$ with center in the unit square, and asking if the union forms a connected figure. Sounds difficult – leonbloy Sep 22 '11 at 21:05
These references are far from answering the question but might be of interest: ima.umn.edu/preprints/Jan83Dec83/34.pdf scipress.org/e-library/rpf/pdf/chap4/0197.PDF – leonbloy Sep 22 '11 at 21:10
I agree with leonbloy that this is likely to be a difficult question. I think it's a great one, though, and would love to know the answer, too. – Mike Spivey Sep 22 '11 at 23:12
@anon: The problem is that those random variables are not IID - for small $d$, if $p_1$ and $p_2$ are close enough to each other, then the probability that $p_n$ is 'close enough' to $p_2$ is highly correlated with the probability that it's 'close enough' to $p_1$. – Steven Stadnicki Sep 22 '11 at 23:29
Crossposted: mathoverflow.net/questions/76153/… – Byron Schmuland Sep 23 '11 at 0:57

## 1 Answer

Let's brute force it. Start with code for Kruskal's algorithm, and then select a number of points (like 10), and find the maximal distance required by Kruskal over 10000 trials. With 10 points, 20 points, and 30 points, I got figures like the following:

Here's code for the 30 point image.

Histogram[Table[Max[With[{pts = RandomReal[{0,1},{30,2}]},
EuclideanDistance[pts[[#]][[1]],pts[[#]][[2]]]&/@List@@@Kruskal[pts]]],{10000}]]


Looks like you could fit a distribution curve to those pretty easily. But that's beyond the duties of a brute forcer, so I'll stop there.

-