Probability of Generating a Connected Graph on the Unit Square

probability graph-theory

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


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:

maximal Kruskal distance on 10, 20, 30 points

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.

Related

Understanding a proof of Komlós's theorem
Is the composition of blowing-up a blowing-up?
Multivariable calculus: hard problems with solutions
Prove that if $2^n-1$ is prime, then $n$ divides $2^n-2$
Equivalent categories yet not isomorphic
Reference request: Abel or Ruffini's proof of the Abel-Ruffini theorem
solution to $ 7^{a}+1 =3^{b}+5^{c} $ for natural $a$,$b$ and $c$
Show that if f is analytic in $|z|\leq 1$, there must be some positive integer n such that $f(\frac{1}{n})\neq \frac{1}{n+1}$
$f$ continuous iff $\operatorname{graph}(f)$ is compact
Words of Length $n$ over the Alphabet $\{1,2,3\}$ with Certain Restrictions
Explicit computation of the Hodge codifferential
Tropical Machinery