Fluctuations of the connectivity threshold and largest nearest-neighbour link

Abstract

Consider a random uniform sample χ_n of n points in a compact region A of Euclidean d-space, d ≥ 2, with a smooth or (when d = 2) polygonal boundary. Fix k ∈ N. Let M_k (χ_n) be the threshold r at which the geometric graph on these n vertices with distance parameter r becomes k-connected. We show that if d = 2 then n (π/|A)M₁(χ_n² − log n is asymptotically standard Gumbel. For (d,k) ≠ (2,1), it is n(θ_d/|A|)M<sub>k<.sub>(χ_n)^d − (2 − 2/d) log n − (4 − 2_k −2/d) log log n that converges in distribution to a nondegenerate limit, where θ_d is the volume of the unit ball. The limit is Gumbel with scale parameter 2 except when (d,k) = (2,2) where the limit is two component extreme value distributed. The different cases reflect the fact that boundary effects are more important in some cases than others. We also give similar results for the largest k-nearest neighbour link L_k(χ_n) in the sample, and show M_k(χ_n) = L_k(χ_n) with high probability. We provide estimates on rates of convergence and give similar results for Poisson samples in A. Finally, we give similar results even for nonuniform samples, with a less explicit sequence of centring constants.