Sharpness in the k -Nearest-Neighbours Random Geometric Graph Model
Victor Falgas‐Ravry, Mark Walters · Advances in Applied Probability · 2012
Let S n , k denote the random graph obtained by placing points in a square box of area n according to a Poisson process of intensity 1 and joining each point to its k nearest neighbours. Balister, Bollobás, Sarkar and Walters (2005) conjectured that, for every 0 < ε < 1 and all sufficiently large n , there exists C = C (ε) such that, whenever the probability that S n , k is connected is at least ε, then the probability that S n , k + C is connected is at least 1 - ε. In this paper we prove this conjecture. As a corollary, we prove that there exists a constant C ' such that, whenever k ( n ) is a sequence of integers such that the probability S n , k ( n ) is connected tends to 1 as n → ∞, then, for any integer sequence s ( n ) with s ( n ) = o (log n ), the probability S n , k ( n )+⌊ C ' s log log n ⌋ is s -connected (i.e. remains connected after the deletion of any s − 1 vertices) tends to 1 as n → ∞. This proves another conjecture given in Balister, Bollobás, Sarkar and Walters (2009).