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

  • 7
    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 difficult2011-09-22
  • 0
    These references are far from answering the question but might be of interest: http://www.ima.umn.edu/preprints/Jan83Dec83/34.pdf http://www.scipress.org/e-library/rpf/pdf/chap4/0197.PDF2011-09-22
  • 0
    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.2011-09-22
  • 0
    An exact probability is almost certainly impossible. The first spot I'd check would probably be the classic random graph papers, Erdős (http://www.renyi.hu/~p_erdos/1959-11.pdf) and possibly Flajolet-Knuth-Pittel, "The First Cycles In An Evolving Graph" (to get a better sense for some of the analytical tools). Obviously this problem has some structural correlation that pure random-graph problems don't, but that would at least be a starting point.2011-09-22
  • 1
    @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$.2011-09-22
  • 0
    @Steven: Ah, you're right.2011-09-22
  • 0
    @leonbloy: Such processes are often called *mosaic processes* and the study of such questions is part of the field. Usually $N$ (in the notation of the OP) is not fixed, but rather the outcome of a Poisson random variable.2011-09-23
  • 4
    Crossposted: http://mathoverflow.net/questions/76153/probability-of-generating-a-connected-graph2011-09-23
  • 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