Connectivity of random k-nearest-neighbour graphs

Let P be a Poisson process of intensity one in a square S-n of area n. We construct a random geometric graph G(n,k) by joining each point of P to its k equivalent to k(n) nearest neighbours. Recently, Xue and Kumar proved that if k <= 0.074 log n then the probability that Gn,k is connected tends to 0 as n -> infinity while, if k >= 5.1774 log n, then the probability that G(n,k) is connected tends to 0 as n -> infinity. They conjectured that the threshold for connectivity is k = (1 + o(1)) log n. In this paper we improve these lower and upper bounds to 0.3043 log n and 0.5139 log n, respectively, disproving this conjecture. We also establish lower and upper bounds of 0.7209 log n and 0.9967 log n for the directed version of this problem. A related question concerns coverage. With G(n,k) as above, we surround each vertex by the smallest (closed) disc containing its k nearest neighbours. We prove that if k <= 0.7209 log n then the probability that these discs cover S-n tends to 0 as n -> infinity while, if k >= 0.9967 log n, then the probability that the discs cover S-n tends to I as n -> infinity.