Sharpness in the \(k\)-nearest-neighbours random geometric graph model. (English) Zbl 1278.60142

Summary: 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. P. Balister et al. [Adv. Appl. Probab. 37, No. 1, 1–24 (2005; Zbl 1079.05086)] conjectured that, for every \(0 < \varepsilon < 1\) and all sufficiently large \(n\), there exists \(C = C(\varepsilon )\) such that, whenever the probability that \(S_{n,k}\) is connected is at least \(\varepsilon \), then the probability that \(S_{n,k+C}\) is connected is at least \(1 - \varepsilon \).
In this paper, we prove this conjecture. As a corollary, we prove that there exists a constant \(C^{\prime}\) 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 \rightarrow \infty\); then, for any integer sequence \(s(n)\) with \(s(n) = o(\log n)\), the probability \(S_{n,k(n)+\lfloor C's \log \log n\rfloor }\) is \(s\)-connected (i.e., remains connected after the deletion of any \(s - 1\) vertices) tends to 1 as \(n \rightarrow \infty \). This proves another conjecture given in [Paul Balister et al., Discrete Appl. Math. 157, No. 2, 309–320 (2009; Zbl 1156.05054)].


60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation
Full Text: DOI arXiv Euclid


[1] Balister, P., Bollobás, B., Sarkar, A. and Walters, M. (2005). Connectivity of random \(k\)-nearest-neighbour graphs. Adv. Appl. Prob. 37 , 1-24. · Zbl 1079.05086
[2] Balister, P., Bollobás, B., Sarkar, A. and Walters, M. (2009). A critical constant for the \(k\)-nearest-neighbour model. Adv. Appl. Prob. 41 , 1-12. · Zbl 1160.05333
[3] Balister, P., Bollobás, B., Sarkar, A. and Walters, M. (2009). Highly connected random geometric graphs. Discrete Appl. Math. 157 , 309-320. · Zbl 1156.05054
[4] Gilbert, E. N. (1961). Random plane networks. J. Soc. Indust. Appl. Math. 9 , 533-543. · Zbl 0112.09403
[5] González-Barrios, J. M. and Quiroz, A. J. (2003). A clustering procedure based on the comparison between the \(k\) nearest neighbors graph and the minimal spanning tree. Statist. Prob. Lett. 62 , 23-34. · Zbl 1101.62351
[6] Penrose, M. D. (1997). The longest edge of the random minimal spanning tree. Ann. Appl. Prob. 7 , 340-361. · Zbl 0884.60042
[7] Penrose, M. D. (1999). On \(k\)-connectivity for a geometric random graph. Random Structures Algorithms 15 , 145-164. · Zbl 0932.05083
[8] Penrose, M. (2003). Random Geometric Graphs (Oxford Stud. Prob. 5 ). Oxford University Press. · Zbl 1029.60007
[9] Walters, M. (2012). Small components in k-nearest neighbour graphs. Discrete Appl. Math. 160 , 2037-2047. · Zbl 1246.05143
[10] Xue, F. and Kumar, P. R. (2004). The number of neighbors needed for connectivity of wireless networks. Wireless Networks 10 , 169-181.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.