A critical constant for the k nearest neighbour model

Simple item page
dc.creatorBalister, Paul
dc.creatorBollobas, Bela
dc.creatorSarkar, Amites
dc.creatorWalters, Mark
dc.date2007-08-29
dc.date.accessioned2026-07-07T08:26:26Z
dc.date.available2026-07-07T08:26:26Z
dc.descriptionLet P be a Poisson process of intensity one in a square S_n of area n. For a fixed integer k, join every point of P to its k nearest neighbours, creating an undirected random geometric graph G_{n,k}. We prove that there exists a critical constant c such that for c'<c, G_{n,c'log n} is disconnected with probability tending to 1 as n tends to infinity, and for c'>c G_{n,c'\log n} is connected with probability tending to 1 as n tends to infinity. This answers a question previously posed by the authors.
dc.description14 pages; 4 postscript figures
dc.identifierhttps://arxiv.org/abs/0708.4007
dc.identifierhttp://arxiv.org/abs/0708.4007
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/136939
dc.subjectProbability
dc.subjectCombinatorics
dc.subject60K35; 82B43
dc.titleA critical constant for the k nearest neighbour model
dc.typetext

Files

Collections

arXiv