# 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/… – user940 Sep 23 '11 at 0:57

Histogram[Table[Max[With[{pts = RandomReal[{0,1},{30,2}]},