Sharpness in the k-nearest neighbours random geometric graph model

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

2011-01-16

arxiv.org/abs/1101.3083v1

Mathematics

Probability

22 pages; 1 figure

Scientific paper

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'$ 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(\log n)$, the probability that $S_{n,k(n)+C's\log \log n}$ is $s$-connected tends to one This proves another conjecture of Balister, Bollob\'as, Sarkar and Walters.

Affiliated with

Also associated with

No associations

Rating

Sharpness in the k-nearest neighbours random geometric graph model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharpness in the k-nearest neighbours random geometric graph model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharpness in the k-nearest neighbours random geometric graph model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-626885