LOCALIZATION IN RANDOM GEOMETRIC GRAPHS WITH TOO MANY EDGES

• 成果类型: Article
• 署名作者: Chatterjee, Sourav; Harel, Matan
• 署名单位: Stanford University; Tel Aviv University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/19-AOP1387
• 发表日期: 2020
• 页码: 574-621
• 关键词: large deviations; upper tails; inequalities; sums; POLYNOMIALS

摘要

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 d-dimensional 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, vertical bar E vertical bar, is greater than (1 + delta)E(vertical bar E vertical bar), for some fixed delta > 0. This article proves that upon conditioning, with high probability there exists a ball of diameter rn which contains a clique of at least root 2 delta E(vertical bar E vertical bar)(1 - epsilon) vertices, for any given epsilon > 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 nonconvex.