Small components in kk-nearest neighbour graphs

Let G=Gn,kG=Gn,k denote the graph formed by placing points in a square of area nn according to a Poisson process of density 1 and joining each point to its kk nearest neighbours. In Balister et al. (2005) [2] Balister et al. proved that if k<0.3043lognk<0.3043logn then the probability that GG is connected tends to 0, whereas if k>0.5139lognk>0.5139logn then the probability that GG 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 GG do not need to consider ‘boundary’ effects.We also improve the upper bound for the threshold for connectivity of GG to 0.4125logn0.4125logn.