Sharpness in the k-Nearest-Neighbours Random Geometric Graph Model

DOI10.1239/AAP/1346955257zbMATH Open1278.60142arXiv1101.3083OpenAlexW2012399955MaRDI QIDQ3167331FDOQ3167331

Mark Walters, Victor Falgas-Ravry

Publication date: 2 November 2012

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Random Geometric Graphs
• Random Plane Networks
• The longest edge of the random minimal spanning tree
• Connectivity of random k-nearest-neighbour graphs
• A critical constant for the k nearest-neighbour model
• Small components in \(k\)-nearest neighbour graphs
• Highly connected random geometric graphs
• A clustering procedure based on the comparison between the \(k\) nearest neighbors graph and the minimal spanning tree.

Cited In (5)

• Randomized near-neighbor graphs, giant components and applications in data science
• Small components in \(k\)-nearest neighbour graphs
• Speed and concentration of the covering time for structured coupon collectors
• Sharpness of KKL on Schreier graphs
• 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)