Small components in k-nearest neighbour graphs

Abstract

Let $G=G_{n,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.3043\log n$ then the probability that $G$ is connected tends to 0, whereas if $k>0.5139\log 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.4125\log n$.

15 pages, 2 figures

Cited by in corpus (1)

• A strict undirected model for the $k$-nearest neighbour graph