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

**Victor Falgas-Ravry**

*(Umeå Universitet)*

#### 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 $\mathbb{P}(S_{n,k} \textrm{ 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 Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-22

Publication Date: September 18, 2013

DOI: 10.1214/EJP.v18-2465

#### References

- Arratia, R.; Goldstein, L.; Gordon, L. Two moments suffice for Poisson approximations: the Chen-Stein
method.
*Ann. Probab.*17 (1989), no. 1, 9--25. MR0972770 - P. Balister and B. Bollobás. Percolation in the k-nearest neighbor graph, 2009.
- Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. Connectivity of random $k$-nearest-neighbour graphs.
*Adv. in Appl. Probab.*37 (2005), no. 1, 1--24. MR2135151 - Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. A critical constant for the $k$-nearest-neighbour model.
*Adv. in Appl. Probab.*41 (2009), no. 1, 1--12. MR2514943 - Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. Highly connected random geometric graphs.
*Discrete Appl. Math.*157 (2009), no. 2, 309--320. MR2479805 - Chen, Louis H. Y. Poisson approximation for dependent trials.
*Ann. Probability*3 (1975), no. 3, 534--545. MR0428387 - V. Falgas-Ravry and M. Walters. Sharpness in the k-nearest neighbour random geometric graph model.
*Advances in Applied Probability*44 (2012), 617--634. - Gilbert, E. N. Random plane networks.
*J. Soc. Indust. Appl. Math.*9 (1961), 533--543. MR0132566 - J.M. González-Barrios and A.J. Quiroz. A clustering procedure based on the comparison between the k-nearest neighbors graph and the minimal spanning tree.
*Statistics and probability letters*62 (2003), no. 1, 23--34. - Penrose, Mathew D. The longest edge of the random minimal spanning tree.
*Ann. Appl. Probab.*7 (1997), no. 2, 340--361. MR1442317 - Stein, Charles. A bound for the error in the normal approximation to the distribution
of a sum of dependent random variables.
*Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. II: Probability theory,*pp. 583--602.*Univ. California Press, Berkeley, Calif.,*1972. MR0402873 - Walters, Mark. Random geometric graphs.
*Surveys in combinatorics 2011,*365--401, London Math. Soc. Lecture Note Ser., 392,*Cambridge Univ. Press, Cambridge,*2011. MR2866737 - Walters, Mark. Small components in $k$-nearest neighbour graphs.
*Discrete Appl. Math.*160 (2012), no. 13-14, 2037--2047. MR2927533 - F. Xue and P.R. Kumar. The number of neighbors needed for connectivity of wireless networks.
*Wireless networks*10 (2004), no. 2, 169--181.

This work is licensed under a Creative Commons Attribution 3.0 License.