Fluctuations of the connectivity threshold and largest nearest-neighbour link

This paper is concerned with the threshold at which the random geometric graph becomes connected. This graph is defined as follows. Let $d\in\mathbb{N}$. Given a finite set $\mathcal{X}\subset\mathbb{R}^{d}$, and $r>0$, the geometric graph $G(\mathcal{X},r)$ has vertex set $\mathcal{X}$, with an edge drawn between any two vertices at Euclidean distance at most $r$ from each other. We say $G(\mathcal{X},r)$ is $k$-connected if it is not possible to disconnect the graph by removing $k-1$ or fewer vertices. (in particular, 1-connectivity is the same as connectivity). The $k$-connectivity threshold of $\mathcal{X}$ is the number

An alternative characterisation of $M_{1}(\mathcal{X})$ is in terms of minimal spanning tree (MST). A MST on $\mathcal{X}$ is a tree spanning $\mathcal{X}$ that minimises the total (Euclidean) length of the edges. It is not hard to see that $M_{1}(\mathcal{X})$ equals the longest edge length of a MST on $\mathcal{X}$.

For the random geometric graph, the vertex set $\mathcal{X}$ is given by the set of points of a Poisson point process $\mathcal{P}_{n}$ in $\mathbb{R}^{d}$ with intensity measure $n\nu$, where $\nu$ is a probability measure on $\mathbb{R}^{d}$ with probability density function $f:\mathbb{R}^{d}\to[0,\infty)$, and $n\in(0,\infty)$ is the mean number of vertices. Alternatively, for $n\in\mathbb{N}$ we can take $\mathcal{X}=\mathcal{X}_{n}$, where $\mathcal{X}_{n}$ denotes a binomial point process whose points are $n$ independent random $d$-vectors with common density $f$. Since the vertices are placed randomly in $\mathbb{R}^{d}$, the thresholds $M_{k}(\mathcal{X}_{n})$ and

are random variables.

In this paper we investigate the limiting behaviour of the connectivity threshold $M_{n,k}$ and $M_{k}(\mathcal{X}_{n})$ for large $n$ and fixed $k\in\mathbb{N}$. We assume throughout that $d\geq 2$. We consider a broad class of measures $\nu$, subject to the working assumption that $\nu$ has compact support $A\subset\mathbb{R}^{d}$, and its density $f$ is continuous and bounded away from zero on $A$. As $n$ grows, the spacing between vertices becomes smaller, so one expects to have $M_{n,k}\to 0$ as $n\to\infty$. A simple consideration by computing typical spacing of vertices leads to the belief that $M_{n,k}$ should decay more slowly than $n^{-1/d}$, in the sense that $nM_{n,k}^{d}$ should tend to infinity in probability. In the special case where $\nu$ is the uniform distribution on $[0,1]^{d}$, it is known [9, 11, 8], that there is an explicit sequence of centring constants $(a_{n})_{n\geq 1}$ satisfying $a_{n}\to\infty$ as $n\to\infty$ such that

where $X$ is an explicit non-degenerate random variable. Clearly (1.2) is what is needed to determine $\lim_{n\to\infty}\mathbb{P}[M_{n,k}\leq r_{n}]$ for any sequence $(r_{n})_{n\geq 1}$ such that the limit exists.

In the present paper, we show that (1.2) holds for suitable $a_{n}$ and $X$, for a broad class of measures $\nu$. While one might perhaps anticipate that the limiting behaviour of the form (1.2) would carry over from the uniform distribution on $[0,1]^{d}$ to more general $\nu$ satisfying our working assumption, proving this seems to be considerably harder that one might naively expect, and in the last 20 years or so there has been limited progress in proving such results. It turns out that even in the uniform case where $f$ is constant on $A$, boundary effects are important because the ‘most isolated’ vertex is likely to lie near the boundary when $d\geq 3$. Thus the formula for $a_{n}$, even when $\nu$ is uniform on $[0,1]^{d}$, is quite complicated (see (1.9) below) due to having to consider all of the different kinds of faces making up the boundary, and does not necessarily provide much insight into the appropriate choice of centring constants for other $A$. In the non-uniform case, determining appropriate constants $a_{n}$ is even harder because they depend in a delicate way on how $f$ approaches its minimum, both in the interior and on the boundary of $A$.

In this work we chiefly consider the case where $\partial A$ is smooth. In the uniform case we determine an explicit sequence of centring constants $a_{n}$ such that (1.2) holds for suitable $X$. In the non-uniform case we are still (in most cases) able to derive (1.2) on taking $a_{n}$ to be the median of the distribution of $nM_{n,k}^{d}$. Part of our proof involves approximating $A$ with a polyhedral set $A_{n}$ with the spacing between vertices of $A_{n}$ decreasing slowly as $n$ becomes large. This technique was developed recently for certain random coverage problems in [15, 4], and its availability is one reason why this problem is more tractable now than it was before.

We also address the case where $d=2$ and $A$ is polygonal; this case could be of importance for some applications, and it turns out that the effects of corners are asymptotically negligible for $d=2$. We hope to deal with the case of polytopal $A$ in dimension $d\geq 3$ in future work.

Understanding the connectivity threshold is important for a variety of applications. In telecommunications, the vertices could represent mobile transceivers and one might be interested in whether the network of transceivers is connected; see e.g. [3]. In topological data analysis (TDA), detecting connectivity is a fundamental step for inspecting all other higher dimensional topological features (here the dimension of the ambient space may be very high). See also applications in machine learning (clustering), statistical tests (e.g. for outliers), spatial epidemics or forest fires (see the description in [9])

Note that (1.2) implies the weaker statement that the sequence $(nM_{n,k}^{d}-a_{n})_{n\geq 1}$ is tight as $n\to\infty$, and even in the (rather exceptional) cases where we cannot prove (1.2), we shall prove this weaker statement. Tightness in turn implies $nM_{n,k}^{d}/a^{\prime}_{n}\to 1$ in probability as $n\to\infty$, for any sequence $(a^{\prime}_{n})_{n\geq 1}$ satisfying $a^{\prime}_{n}/a_{n}\to 1$ as $n\to\infty$. Another direction of research (not followed in the present paper) is to improve this to almost sure convergence, i.e. a strong law of large numbers (SLLN), under the natural coupling of $(\mathcal{X}_{n},n\geq 1)$:

or to establish (1.3) for some $a^{\prime}_{n}$ even in cases when (1.2) is not known; see (1.7), (1.8) below.

Given $x\in\mathbb{R}^{d}$ and $r>0$, we denote the closed Euclidean ball of radius $r$, centred at $x$, by either $B_{r}(x)$ or $B(x,r)$. Given finite $\mathcal{X}\subset\mathbb{R}^{d}$ we define the largest $k$-nearest-neighbour link $L_{k}(\mathcal{X})$ of $\mathcal{X}$, by

where $|\mathcal{X}|$ denotes the number of elements of $\mathcal{X}$ and $\mathcal{X}(\cdot):=|\mathcal{X}\cap\cdot|$ denotes the counting measure associated with $\mathcal{X}$. Note that if $|\mathcal{X}|\geq k+1$ and $x\in\mathcal{X}$, then $\inf\{r>0:\mathcal{X}(B_{r}(x))>k\}$ is the distance from $x$ to its $k$-nearest neighbour in $\mathcal{X}$. Note also that $L_{k}(\mathcal{X})\leq M_{k}(\mathcal{X})$ since if $r<L_{k}(\mathcal{X})$ and $|\mathcal{X}|\geq k+1$, then $G(\mathcal{X},r)$ has at least one vertex with degree less than $k$ and therefore is not $k$-connected, so $r\leq M_{k}(\mathcal{X})$.

Our analysis of $M_{n,k}$ and $M_{k}(\mathcal{X}_{n})$ will involve first investigating $L_{n,k}:=L_{k}(\mathcal{P}_{n})$ and $L_{k}(\mathcal{X}_{n})$. A priori, it is not obvious that $L_{k}(\mathcal{X}_{n})$ is a sharp lower bound for $M_{k}(\mathcal{X}_{n})$; nevertheless, it is known in some cases (see Section 1.3) that $M_{k}(\mathcal{X}_{n})$ enjoys the same limiting behaviour as $L_{k}(\mathcal{X}_{n})$, and even sometimes that

Equation (1.5), when true, says that with probability tending to 1 as $n\to\infty$ the point set $\mathcal{X}_{n}$ has the following property: If we start with no edges between the vertices of $\mathcal{X}_{n}$, and then add edges one by one in order of increasing Euclidean length until we arrive at a $k$-connected graph, then just before the addition of the last edge we still have a vertex of degree less than $k$; if $k=1$ then just before the addition of the last edge we have exactly two components, one of which is a singleton.

The largest $k$-nearest neighbour link $L_{k}(\mathcal{X}_{n})$ (or $L_{k}(\mathcal{P}_{n})$) is of interest in its own right. To quote [1], it ‘comes up in almost all discussions of computational complexity involving nearest neighbours’. See e.g. [9] for further motivation. As with $M_{n,k}$, its limiting behaviour has previously been studied on the torus, and the unit cube, and only at the level of a SLLN for regions with smooth or polytopal boundary. By providing a limiting distribution for $L_{k}(\mathcal{X}_{n})$ for regions with smooth or polygonal boundary, we here add significantly to this body of work, too.

Before stating our main results, let us give a literature review on this topic. Under our working assumption (WA), we use throughout the notation

Note that $0<f_{0}\leq f_{1}\leq f_{\rm max}<\infty$ under our WA. Let $\theta_{d}$ denote the volume of a $d$-dimensional unit ball. i.e. $\theta_{d}:=\pi^{d/2}/\Gamma(1+d/2)$,

In the case where $A$ is the flat torus $\mathbb{T}^{d}$ of any dimension, it is known [8, Theorem 13.6] that under the natural coupling of $(\mathcal{X}_{n},n\geq 1)$ we have

The dimensionality and the density play a crucial role when one considers compact sets with boundaries. More precisely, if $A$ has a smooth boundary, it is proved for $k=1$ in [12, 13], and for general $k$ in [8], that

When $A$ is a convex polytope, it is proved in [17] that

where $\Phi^{*}$ denotes the collection of all faces of $\varphi$ of all dimensions (including $A$ itself, considered as a face of dimension $d$), and where $D(\varphi)$ is the dimension of face $\varphi$, and where $f_{\varphi}$ denotes the infimum of $f$ over face $\varphi$ and $\rho_{\varphi}$ is the angular volume of face $\varphi$.

Less is known about the fluctuations of $nM_{k}(\mathcal{X}_{n})^{d}-a_{n}$. Weak limit results of the type (1.2) are proved for two cases in [9, 11]. The first case is when $f$ is uniform on $\mathbb{T}^{d}$ for any $d\geq 2$. In this case, by [8, Corollary 13.20], one has

where ${\mathsf{Gu}}$ denotes a standard Gumbel random variable, i.e. one with cumulative distribution function $F(x)=\exp(-e^{-x}),x\in\mathbb{R}$. (For $a\in\mathbb{R},b>0$ the random variable $b{\mathsf{Gu}}+a$ is said to be Gumbel distributed with scale parameter $b$ and location parameter $a$.)

The second case is when $f$ is uniform on $[0,1]^{d}$. For this case, we describe only the results for $k=1$ from [8] but the case of general $k$ is also treated there. When $f$ is uniform on $[0,1]^{d}$, one has by [8, Corollary 13.21] that

Similar results hold for $L_{k}(\mathcal{X}_{n})$; see [8, Theorems 8.3 and 8.4]. Moreover it is known that (1.5) holds. Also these results hold for $\mathcal{P}_{n}$ instead of $\mathcal{X}_{n}$.

So far as we know, there is no weak limit result for other shaped boundaries or for non-uniform distributions (until now). In the special case where $d=2$ and $f$ is uniformly distributed in a disk, [3] gives a partial result in the direction of a weak limit.

The main results of this paper considerably generalise previous findings and deepen the understanding of the connectivity threshold in terms of the geometry of $A$. In the uniform case, we also provide a bound on the rate of convergence that is new for all shapes under the WA.

We end this section by mentioning some related results. It is natural to ask what happens if we drop the working assumption and take the support of $f$ to be unbounded. Penrose [10] found that the scaling is completely different in the case of standard Gaussian density in $\mathbb{R}^{d}$; see also Hsing and Rootzén [5] for a significant extension in dimension two, where a class of elliptically contoured distributions are included, e.g. Gaussian densities with correlated coordinates. Gupta and Iyer [2] give a limiting distribution and SLLN for $L_{n,1}$ for a class of radially symmetric densities with unbounded support, including cases where $L_{n,1}$ (and hence also $M_{n,1}$) does not even tend to zero.

Throughout this paper, $c$ and $c^{\prime}$ denote positive finite constants whose values may vary from line to line and do not depend on $n$. Also if $n_{0}\in(0,\infty)$ and $f(n),g(n)$ are two functions, defined for all $n\geq n_{0}$ with $g(n)>0$ for all $n\geq n_{0}$, the notation $f(n)=O(g(n))$ as $n\to\infty$ means that $\limsup_{n\to\infty}(|f(n)|/g(n))<\infty$. If also $f(n)>0$ for all $n\geq n_{0}$, we use notation $f(n)=\Theta(g(n))$ to mean that both $f(n)=O(g(n))$ and $g(n)=O(f(n))$.

Given $d,k\in\mathbb{N}$, define the constant

In this paper, given $A\subset\mathbb{R}^{d}$, we say that $A$ has $C^{2}$ boundary (or for short: $\partial A\in C^{2}$) if for each $x\in\partial A$, the topological boundary of $A$, there exists a rigid motion $\rho_{x}$ of $\mathbb{R}^{d}$, an open set $U_{x}\subset\mathbb{R}^{d-1}$ and a $C^{2}$ function $f_{x}:\mathbb{R}^{d-1}\to\mathbb{R}$ such that $\rho_{x}(A\cap U)=\rho_{x}(U)\cap\mathrm{epi}(f_{x})$, where $\mathrm{epi}(f_{x}):=\{(u,z)\in\mathbb{R}^{d-1}\times\mathbb{R}:z\geq f_{x}(u)\}$, the closed epigraph of $f_{x}$.

For compact $A\subset\mathbb{R}^{d}$ with $C^{2}$ or polytopal boundary, let $|A|$ denote the volume (Lebesgue measure) of $A$, and $|\partial A|$ the perimeter of $A$, i.e. the $(d-1)$-dimensional Hausdorff measure of $\partial A$. Also define

Note that $\sigma_{A}^{d}$ is sometimes called the isoperimetric ratio of $A$, and is at least $d^{d}\theta_{d}$ by the isoperimetric inequality.

We now give a result for the general non-uniform case; that is, we still use our WA on $f$, but drop the stronger assumption that $f$ is constant on $A$. Recall $f_{0},f_{1}$ defined at (1.6). In this more general case, subject to the condition $f_{1}\neq f_{0}(2-2/d)$, we still provide a result along the lines of (1.2), but now, instead of using the explicit centring constants $a_{n}=(2-2/d)\log n-(4-2k-2/d){\bf 1}\{d\geq 3\leavevmode\nobreak\ {\rm or}\leavevmode\nobreak\ k\geq 2\}\log\log n$ as in Theorem 1.1, we take $a_{n}$ to be the median of the distribution $nM_{n}^{d}$. In the case $f_{1}=f_{0}(2-2/d)$ we prove only the weaker result that our sequence of centred random variables is tight.

Given a random variable $X$, let $\mu(X):=\inf\{x\in\mathbb{R}:\mathbb{P}[X\leq x]\geq 1/2\}$, the median of the distribution of $X$. Note that $\mu({\mathsf{Gu}})=-\log(\log 2)$, so for $\alpha>0$, the random variable $\alpha({\mathsf{Gu}}+\log(\log 2))$ has a Gumbel distribution with median 0 and with scale parameter $\alpha$.

Before proceeding to proofs, we give a rough calculation indicating why, in the uniform case with $f\equiv f_{0}{\bf 1}_{A}$, we might expect to see qualitative differences between the cases with $d=2$ and $k=1$ or $k=2$, and other cases, as seen in Theorem 1.1. Suppose we take a sequence of distance parameters $r_{n}$ with $nf_{0}\theta_{d}r_{n}^{d}=\log n+(k-1)\log\log n+c$ for some constant $c$. Given $r_{n}$, let $F^{o}_{n}$, $F_{n}^{\partial}$ be the number of vertices of degree less than $k$ in the interior of $A$, respectively near the boundary of $A$. We give a rough calculation suggesting that for $d\geq 3$ we have $\mathbb{E}[F_{n}^{\partial}]\gg\mathbb{E}[F_{n}^{o}]$ so the boundary region dominates, while for $d=2$, it depends on the value of $k$ whether the interior or boundary region dominates. Firstly,

For $F_{n}^{\partial}$, note that for small positive $s$ the volume of the intersection of $A$ with a ball of radius $r_{n}$ centred at distance $sr_{n}$ from $\partial A$ is about $(\theta_{d}/2)r_{n}^{d}+\theta_{d-1}sr_{n}^{d}$, suggesting

If $d\geq 3$ this tends to infinity (regardless of $k$). Thus the boundary effects dominate in this case; we should choose a slightly bigger $r_{n}$ to make $\mathbb{E}[F_{n}^{\partial}]$ tend to a constant, and then $\mathbb{E}[F_{n}^{o}]$ will tend to zero.

If $d=2$, the last expression for $\mathbb{E}[F_{n}^{\partial}]$ tends to zero if $k=1$ and to infinity if $k\geq 3$, so the interior contribution dominates when $k=1$ but the boundary contribution dominates when $k\geq 3$. When $k=2$ the interior and boundary effects are of comparable size.

Having chosen $r_{n}$ so that $\mathbb{E}[F_{n}^{o}+F_{n}^{\partial}]$ tends to a constant, we shall use Poisson approximation to show that $\mathbb{P}[L_{n}^{o}\leq r_{n}]$ tends to a non-trivial constant, and then some percolation arguments to show the same limit holds for $\mathbb{P}[M_{n,1}\leq r_{n}]$.

The rest of the paper is organised as follows. After the preparation of geometrical ingredients in Section 2, we prove Poisson approximation for the number of $k$-isolated vertices in Section 3, asymptotic equivalence of $L_{n,k}$ and $M_{n,k}$ in Section 4, the weak law in the nonuniform case (Theorem 1.3) in Section 5 and finally the weak law in the uniform case (Theorem 1.1) in Section 6.