Almost optimal sparsification of random geometric graphs

A random geometric irrigation graph ${\mathrm{\Gamma }}_n(r_n,\xi )$ has $n$ vertices identified by $n$ independent uniformly distributed points $X_1,\dots ,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\mathrm{\ne }i$) for which $\mathrm{\parallel }{X}_i-X_j\mathrm{\parallel }<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\mathrm{/}n}$ for ${\gamma }_n\to \mathrm{\infty }$ with ${\gamma }_n=o(n^{1\mathrm{/}6}\mathrm{/}{\log }^{5\mathrm{/}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$,thenthesizeofthelargestconnectedcomponentiswithhighprobability$n-o(n)$. This offers a natural non-centralized sparsification of a random geometric graph that is mostly connected.