Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-05T04:34:49.374Z Has data issue: false hasContentIssue false
  • English
  • Français

A critical constant for the k nearest-neighbour model

Part of: Equilibrium statistical mechanics Graph theory

Published online by Cambridge University Press:  01 July 2016

Paul Balister ,
Béla Bollobás ,
Amites Sarkar  and
Mark Walters
Paul Balister*
Affiliation:
University of Memphis
Béla Bollobás*
Affiliation:
University of Memphis
Amites Sarkar*
Affiliation:
University of Memphis
Mark Walters*
Affiliation:
University of Cambridge
*
∗ Postal address: University of Memphis, Department of Mathematics, 3725 Norriswood, Memphis, TN 38152, USA.
∗∗ Current address: Trinity College, University of Cambridge, Cambridge, CB2 1TQ, UK.
∗∗∗ Current address: Department of Mathematics, Western Washington University, 516 High Street, Bellingham, WA 98225, USA. Email address: [email protected]
∗∗∗∗ Current address: School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, 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 𝒫 be a Poisson process of intensity 1 in a square Sn of area n. For a fixed integer k, join every point of 𝒫 to its k nearest neighbours, creating an undirected random geometric graph Gn,k. We prove that there exists a critical constant ccrit such that, for c < ccrit, Gn,⌊c log n⌋ is disconnected with probability tending to 1 as n → ∞ and, for c > ccrit, Gn,⌊c log n⌋ is connected with probability tending to 1 as n → ∞. This answers a question posed in Balister et al. (2005).

Keywords

Random geometric graphconnectivityPoisson process

MSC classification

Primary: 05C80: Random graphs
Secondary: 82B43: Percolation
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 41 , Issue 1 , March 2009 , pp. 1 - 12
Copyright
Copyright © Applied Probability Trust 2009 

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.CrossRefGoogle 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