10
$\begingroup$

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

  • 0
    **Related**: P. Hall (1986): [Clump counts in a mosaic](http://projecteuclid.org/euclid.aop/1176992525), *Ann. Prob.*, vol. 14, no. 2, 424-458.2011-09-23

1 Answers 1

3

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.