Almost optimal sparsification of random geometric graphs
Résumé
A random geometric irrigation graph $\Gamma_n(r_n,\xi)$ has $n$ vertices identified by $n$ independent uniformly distributed points $X_1,\ldots,X_n$ in the unit square $[0,1]^2$. Each point $X_i$ selects $\xi_i$ neighbors at random, without replacement, among those points $X_j$ ($j\neq i$) for which $\|X_i-X_j\| < r_n$, and the selected vertices are connected to $X_i$ by an edge. The number $\xi_i$ of the neighbors is an integer-valued random variable, chosen independently with identical distribution for each $X_i$ such that $\xi_i$ satisfies $1\le \xi_i \le \kappa$ for a constant $\kappa>1$. We prove that when $r_n = \gamma_n \sqrt{\log n/n}$ for $\gamma_n \to \infty$ with $\gamma_n =o(n^{1/6}/\log^{5/6}n)$, then the random geometric irrigation graph experiences explosive percolation in the sense that when $\mathbf E \xi_i=1$, then the largest connected component has size $o(n)$ but if $\mathbf E \xi_i >1$, then the size of the largest connected component is with high probability $n-o(n)$. This offers a natural non-centralized sparsification of a random geometric graph that is mostly connected.