Rare event probabilities in random geometric graphs

Abstract

Abstract We study rare events in spherical and Gaussian random geometric graphs in high dimensions. In these models, the vertices correspond to points sampled uniformly at random on the d -dimensional unit sphere or correspond to d -dimensional standard Gaussian vectors, and edges are added between two vertices if the inner product between their corresponding points is greater than a threshold t Subscript p t p $t_{p}$ , chosen such that the probability of having an edge is equal to p . We focus on two problems: (a) the probability that the random geometric graph is a complete graph and (b) the probability of observing an atypically large number of edges. We obtain asymptotically exponential decay rates depending on n and d of the probabilities of these rare events through a combination of geometric and probabilistic arguments.