A critical constant for the k nearest-neighbour model

Let 𝒫 be a Poisson process of intensity 1 in a square S n of area n . For a fixed integer k , join every point of 𝒫 to its k nearest neighbours, creating an undirected random geometric graph G n,k . We prove that there exists a critical constant c crit such that, for c < c crit , G n ,⌊ c log n ⌋ is disconnected with probability tending to 1 as n → ∞ and, for c > c crit , G n ,⌊ c log n ⌋ is connected with probability tending to 1 as n → ∞. This answers a question posed in Balister et al . (2005).