Localization in random geometric graphs with too many edges

We consider a random geometric graph $G({\chi }_n,r_n)$, given by connecting two vertices of a Poisson point process ${\chi }_n$ of intensity $n$ on the unit torus whenever their distance is smaller than the parameter $r_n$. The model is conditioned on the rare event that the number of edges observed, $\mathrm{\mid }E\mathrm{\mid }$, is greater than $(1+\delta )\mathbb{E}(\mathrm{\mid }E\mathrm{\mid })$, for some fixed $\delta >0$. This article proves that upon conditioning, with high probability there exists a ball of diameter $r_n$ which contains a clique of at least $\sqrt{2 \delta $\mathbb{E}$(|E|)}(1 - \varepsilon)$vertices,foranygiven$\varepsilon >0$. Intuitively, this region contains all the “excess” edges the graph is forced to contain by the conditioning event, up to lower order corrections. As a consequence of this result, we prove a large deviations principle for the upper tail of the edge count of the random geometric graph. The rate function of this large deviation principle turns out to be non-convex.