Almost optimal sparsification of random geometric graphs

A random geometric irrigation graph Γn(rn, ξ) has n vertices identified by n independent uniformly distributed points X1,..., Xn in the unit square [0, 1]2. Each point Xi selects ξi neighbors at random, without replacement, among those points Xj (j 6 = i) for which ‖Xi − Xj ‖ < rn, and the selected vertices are connected to Xi by an edge. The number ξi of the neighbors is an integer-valued random variable, chosen independently with identical distribution for each Xi such that ξi satisfies 1 ≤ ξi ≤ κ for a constant κ> 1. We prove that when rn = γn log n/n for γn → ∞ with γn = o(n1/6 / log5/6 n), then the random geometric irrigation graph experiences explosive percolation in the sense that when Eξi = 1, then the largest connected component has size o(n) but if Eξ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.