2011/01/13 by Mark Walters, Walters, Mark · 1 citation
Computer Science · Mathematics · #60K35 #82B43 #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1101.2619
openalex publication_date 2011/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=Gn,k denote the graph formed by placing points in a square of area n according to a Poisson process of density 1 and joining each point to its k nearest neighbours. Balister, Bollobás, Sarkar and Walters proved that if k<0.3043log n then the probability that G is connected tends to 0, whereas if k>0.5139log n then the probability that G is connected tends to 1. We prove that, around the threshold for connectivity, all vertices near the boundary of the square are part of the (unique) giant component. This shows that arguments about the connectivity of G do not need to consider `boundary' effects. We also improve the upper bound for the threshold for connectivity of G to k=0.4125log n.