Sharpness in the k-nearest-neighbours random geometric graph model

DOI10.1239/AAP/1346955257MaRDI QIDQ3167331zbMATHOpenAlexFDO

Authors Victor Falgas-Ravry, Mark Walters

Publication date 2 November 2012

Published in Advances in Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

connectivityrandom geometric graphsharp transition

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43)

Abstract: Let $S_{n,k}$ denote the random geometric 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'as, Sarkar and Walters conjectured that for every $0<epsilon<1$ and all $n$ sufficiently large there exists $C=C(epsilon)$ such that whenever the probability $S_{n,k}$ is connected is at least $epsilon$ then the probability $S_{n,k+C}$ is connected is at least $1-epsilon$. In this paper we prove this conjecture. As a corollary we prove that there is a constant $C^{\prime }$ such that whenever $k=k(n)$ is a sequence of integers such that the probability $S_{n,k(n)}$ is connected tends to one as $n$ tends to infinity, then for any $s(n)$ with $s(n)=o(logn)$, the probability that $S_{n,k(n)+C^{\prime }sloglogn}$ is $s$-connected tends to one This proves another conjecture of Balister, Bollob'as, Sarkar and Walters.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1340281 (Why is no real title available?)
• A clustering procedure based on the comparison between the \(k\) nearest neighbors graph and the minimal spanning tree.
• A critical constant for the k nearest-neighbour model
• Connectivity of random k-nearest-neighbour graphs
• Highly connected random geometric graphs
• Random Geometric Graphs
• Random Plane Networks
• Small components in \(k\)-nearest neighbour graphs
• The longest edge of the random minimal spanning tree

Cited in

(8)

• Highly connected random geometric graphs
• Small components in \(k\)-nearest neighbour graphs
• A critical constant for the k nearest-neighbour model
• Sharpness of KKL on Schreier graphs
• Randomized near-neighbor graphs, giant components and applications in data science
• Distribution of components in the \(k\)-nearest neighbour random geometric graph for \(k\) below the connectivity threshold
• Speed and concentration of the covering time for structured coupon collectors
• Bootstrap percolation in random geometric graphs

This page was built for publication: Sharpness in the \(k\)-nearest-neighbours random geometric graph model

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