When does a random geometric graph become connected?

94 Views Asked by At

Fix $n\in \mathbb N$ and let $X_1,\dots,X_n$ be i.i.d uniform random points in $[0,1]^2$. For $r\in \mathbb R$ consider the (random) geometric graph $\mathcal G _r(X)$ with vertices $X=\{X_i\}$ and edges $X_i\sim X_j\iff \vert X_i - X_j \vert^2 \leq r$. Define a new random variable $\nu$ by setting $$ \nu = min\{r\in\mathbb R\,\vert\, \mathcal G_r(X) \text{ is connected} \}. $$ Now what is $\mathbb E[\nu]$? Is there an explicit formula?

I am aware of the classical results in 'Random Geometric Graphs' (Penrose) on the phase transition of connectivity. However, they only describe asymptotic behavior for a sequence of growing sample sizes and I dont know if that can help for the above question.

Thoughts so far:

For the asymptotic version of the question, it turns out that the existence of isolated points is the only 'real' obstruction to being connected; In the sense that the graph is connected with high probability if there exist no isolated points. So let us look at that first.

Consider the random variables $\iota_j = min_{k\neq j} \vert X_i-X_j\vert^2$ and \begin{align} \iota &= max\{\iota_k\}_k\\ &=max\{r\in\mathbb R\,\vert\,\mathcal G_r(X) \text{ contains an isolated vertex}\}. \end{align} Then $\iota\leq\nu$ and (ignoring boundary effects) we can compute $$ P(\iota_0 > \delta)=P(X_0 \text{ is $\delta$-isolated})=(1-\pi \delta^2)^{n-1} $$ and further by just assuming that the $\iota_k$'s are independent (How bad is this approximation?) we would get $$ P(\iota < \delta) = P(\iota_k < \delta \,\forall k) \approx P(\iota_0 < \delta)^n $$ and finally $$ \mathbb E[\iota] = \int_0^\infty 1-P(\iota <\delta) \,d \delta=\int_0^\infty 1- (1-(\pi \delta^2)^{n-1})^n\,d\delta. $$