Sharpness in the \(k\)-nearest-neighbours random geometric graph model. (English) Zbl 1278.60142

Falgas-Ravry, Victor; Walters, Mark

Adv. Appl. Probab. 44, No. 3, 617-634 (2012).

Summary: Let \(S_{n,k}\) denote the random 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. P. Balister et al. [Adv. Appl. Probab. 37, No. 1, 1–24 (2005; Zbl 1079.05086)] conjectured that, for every \(0 < \varepsilon < 1\) and all sufficiently large \(n\), there exists \(C = C(\varepsilon )\) such that, whenever the probability that \(S_{n,k}\) is connected is at least \(\varepsilon \), then the probability that \(S_{n,k+C}\) is connected is at least \(1 - \varepsilon \).
In this paper, we prove this conjecture. As a corollary, we prove that there exists a constant \(C^{\prime}\) such that, whenever \(k(n)\) is a sequence of integers such that the probability \(S_{n,k(n)}\) is connected tends to 1 as \(n \rightarrow \infty\); then, for any integer sequence \(s(n)\) with \(s(n) = o(\log n)\), the probability \(S_{n,k(n)+\lfloor C's \log \log n\rfloor }\) is \(s\)-connected (i.e., remains connected after the deletion of any \(s - 1\) vertices) tends to 1 as \(n \rightarrow \infty \). This proves another conjecture given in [Paul Balister et al., Discrete Appl. Math. 157, No. 2, 309–320 (2009; Zbl 1156.05054)].

MSC:

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

Keywords:

random geometric graph; connectivity; sharp transition

Citations:

Zbl 1079.05086; Zbl 1156.05054

References:

[1]	Balister, P., Bollobás, B., Sarkar, A. and Walters, M. (2005). Connectivity of random \(k\)-nearest-neighbour graphs. Adv. Appl. Prob. 37 , 1-24. · Zbl 1079.05086
[2]	Balister, P., Bollobás, B., Sarkar, A. and Walters, M. (2009). A critical constant for the \(k\)-nearest-neighbour model. Adv. Appl. Prob. 41 , 1-12. · Zbl 1160.05333
[3]	Balister, P., Bollobás, B., Sarkar, A. and Walters, M. (2009). Highly connected random geometric graphs. Discrete Appl. Math. 157 , 309-320. · Zbl 1156.05054
[4]	Gilbert, E. N. (1961). Random plane networks. J. Soc. Indust. Appl. Math. 9 , 533-543. · Zbl 0112.09403
[5]	González-Barrios, J. M. and Quiroz, A. J. (2003). A clustering procedure based on the comparison between the \(k\) nearest neighbors graph and the minimal spanning tree. Statist. Prob. Lett. 62 , 23-34. · Zbl 1101.62351
[6]	Penrose, M. D. (1997). The longest edge of the random minimal spanning tree. Ann. Appl. Prob. 7 , 340-361. · Zbl 0884.60042
[7]	Penrose, M. D. (1999). On \(k\)-connectivity for a geometric random graph. Random Structures Algorithms 15 , 145-164. · Zbl 0932.05083
[8]	Penrose, M. (2003). Random Geometric Graphs (Oxford Stud. Prob. 5 ). Oxford University Press. · Zbl 1029.60007
[9]	Walters, M. (2012). Small components in k-nearest neighbour graphs. Discrete Appl. Math. 160 , 2037-2047. · Zbl 1246.05143
[10]	Xue, F. and Kumar, P. R. (2004). The number of neighbors needed for connectivity of wireless networks. Wireless Networks 10 , 169-181.