Fluctuations of the connectivity threshold and largest nearest-neighbour link

Consider a random uniform sample of n points in a compact region A of Euclidean d-space, d \geq 2, with a smooth or (when d=2) polygonal boundary. Fix k \in {\bf N}. Let T_{n,k} 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 (\pi/|A|) T_{n,1}^2 - \log n is asymptotically standard Gumbel. For (d,k) \neq (2,1), it is n (\theta_d/|A|) T_{n,k}^d - (2-2/d) \log n - (4-2k-2/d) \log \log n that converges in distribution to a nondegenerate limit, where \theta_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 more important in some cases than others. We also give similar results for the largest k-nearest neighbour link U_{n,k} in the sample, and show T_{n,k}=U_{n,k} 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 non-uniform samples, with a less explicit sequence of centring constants.