Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T05:02:05.088Z Has data issue: false hasContentIssue false
  • English
  • Français

Sharpness in the k-Nearest-Neighbours Random Geometric Graph Model

Part of: Special processes Equilibrium statistical mechanics

Published online by Cambridge University Press:  04 January 2016

Victor Falgas-Ravry  and
Mark Walters
Victor Falgas-Ravry*
Affiliation:
Queen Mary, University of London
Mark Walters*
Affiliation:
Queen Mary, University of London
*
∗ Postal address: School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, UK.
∗ Postal address: School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, UK.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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(logn), the probability S n,k(n)+⌊C'slog logn⌋ 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).

Keywords

Random geometric graphconnectivitysharp transition

MSC classification

Primary: 60K35: Interacting random processes; statistical mechanics type models; percolation theory
Secondary: 82B43: Percolation

Information

Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 44 , Issue 3 , September 2012 , pp. 617 - 634
Copyright
© Applied Probability Trust 

References

Balister, P., Bollobás, B., Sarkar, A. and Walters, M. (2005). Connectivity of random k-nearest-neighbour graphs. Adv. Appl. Prob. 37, 1–24.Google Scholar
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.Google Scholar
Balister, P., Bollobás, B., Sarkar, A. and Walters, M. (2009). Highly connected random geometric graphs. Discrete Appl. Math. 157, 309–320.CrossRefGoogle Scholar
Gilbert, E. N. (1961). Random plane networks. J. Soc. Indust. Appl. Math. 9, 533–543.Google Scholar
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.CrossRefGoogle Scholar
Penrose, M. D. (1997). The longest edge of the random minimal spanning tree. Ann. Appl. Prob. 7, 340–361.Google Scholar
Penrose, M. D. (1999). On k-connectivity for a geometric random graph. Random Structures Algorithms 15, 145–164.Google Scholar
Penrose, M. (2003). Random Geometric Graphs (Oxford Stud. Prob. 5). Oxford University Press.Google Scholar
Walters, M. (2012). Small components in k-nearest neighbour graphs. Discrete Appl. Math. 160, 2037–2047.Google Scholar
Xue, F. and Kumar, P. R. (2004). The number of neighbors needed for connectivity of wireless networks. Wireless Networks 10, 169–181.CrossRefGoogle Scholar