Almost optimal sparsification of random geometric graphs

Abstract

A random geometric irrigation graph ${\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\ne i$) for which $\Vert X_i-X_j\Vert <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.