Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-14T10:13:14.484Z Has data issue: false hasContentIssue false
  • English
  • Français

A critical constant for the k nearest-neighbour model

Part of:Equilibrium statistical mechanicsGraph 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: amites.sarkar@wwu.edu
∗∗∗∗ 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 S n of area n. For a fixed integer k, join every point of 𝒫 to its k nearest neighbours, creating an undirected random geometric graph G n,k . We prove that there exists a critical constant c crit such that, for c < c crit, G n,⌊c log n⌋ is disconnected with probability tending to 1 as n → ∞ and, for c > c crit, G n,⌊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

Information

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