2024/06/02 by Mathew D. Penrose, Penrose, Mathew D., Xiaochuan Yang +1
Physics and Astronomy · #60D05 #Complex Network Analysis Techniques #FOS: Mathematics #Opinion Dynamics and Social Influence #Probability (math.PR) #Quantum optics and atomic interactions
paper · pdf · doi:10.48550/arxiv.2406.00647
openalex publication_date 2024/06/02 · openalex created_date 2024/06/06 · openalex updated_date 2026/07/28
Consider a random uniform sample 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 ∈ \bf N. Let Tn,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 (π/|A|) Tn,12 - log n is asymptotically standard Gumbel. For (d,k) ≠ (2,1), it is n (θd/|A|) Tn,kd - (2-2/d) log n - (4-2k-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 more important in some cases than others. We also give similar results for the largest k-nearest neighbour link Un,k in the sample, and show Tn,k=Un,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.