Distribution of components in the k-nearest neighbour random geometric graph for k below the connectivity threshold

DOI10.1214/EJP.V18-2465zbMATH Open1288.60128arXiv1211.5918OpenAlexW2151967317MaRDI QIDQ388975FDOQ388975

Authors: Victor Falgas-Ravry 

Publication date: 17 January 2014

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: Let S_{n,k} denote the random geometric graph obtained by placing points inside a square of area n according to a Poisson point process of intensity 1 and joining each such point to the k=k(n) points of the process nearest to it. In this paper we show that if Pr(S_{n,k} connected) > n^{-gamma_1} then the probability that S_{n,k} contains a pair of `small' components `close' to each other is o(n^{-c_1}) (in a precise sense of `small' and 'close'), for some absolute constants gamma_1>0 and c_1 >0. This answers a question of Walters. (A similar result was independently obtained by Balister.) As an application of our result, we show that the distribution of the connected components of S_{n,k} below the connectivity threshold is asymptotically Poisson.

Full work available at URL: https://arxiv.org/abs/1211.5918

Recommendations

• Small components in \(k\)-nearest neighbour graphs
• Connectivity of random k-nearest-neighbour graphs
• Highly connected random geometric graphs
• Sharpness in the \(k\)-nearest-neighbours random geometric graph model
• A critical constant for the k nearest-neighbour model

zbMATH Keywords

Poisson processnearest neighbour, connected componentsRandom geometric graphs

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cited In (7)

• A critical constant for the k nearest-neighbour model
• On the one dimensional Poisson random geometric graph
• Highly connected random geometric graphs
• Small components in \(k\)-nearest neighbour graphs
• The size of components in continuum nearest-neighbor graphs
• Sharpness in the \(k\)-nearest-neighbours random geometric graph model
• On the distribution of typical shortest-path lengths in connected random geometric graphs

This page was built for publication: Distribution of components in the \(k\)-nearest neighbour random geometric graph for \(k\) below the connectivity threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q388975)