Localization in random geometric graphs with too many edges (Q2179590): Difference between revisions

A random geometric graph comprises a set of vertices that are distributed randomly over some metric space \(X\). Here two vertices are joined by an edge if the distance between them is sufficiently small. This formation suggests a canonical substitute to the classical Erdős-Rényi random graph model, where the presence of each edge is an independent event. The probe on random geometric graphs is comparatively a new venture and it is widely acknowledged that a \textit{M. Penrose}]'s monograph is the authority [Random geometric graphs. Oxford: Oxford University Press (2003; Zbl 1029.60007). Other than the theoretical interest, random geometric graphs also have several applications, for instance in wireless communication networks. The authors in this paper study one type of random geometric graph \(G(\chi_n, r_n)\). These graphs are formed by joining two given nodes of a Poisson point process \(\chi_n\) of intensity \(n\) on the \(d\)-dimensional unit torus, whenever the distance among them is less than the parameter \(r_n\). Normally, research work on random geometric graphs focuses either on how such a graph behaves for a given \(r\) as \(n\) goes to infinity. Else, the other type is the one that deviates from the said behavior, namely, the central limit theorems. The authors in this work, fix their attention on the behavior of the model conditioned on having many more edges than is expected by inheriting the properties from the geometry of \(\mathbb R^d\) to evaluate the upper tail large deviation rate function. They demonstrate that such a model exhibits localization. This feature is explained as a situation in which a limited number of nodes approximately account for all the extra edges that one would require the graph to exhibit, by not affecting the edge count in some weak sense and the geometry of the localized region has the shape of a ball in the given norm. The authors employ techniques from large deviations, concentration inequalities, convex analysis and geometric measure theory. They also genuinely acknowledged that a key component in their proof is a technique for proving localization, which is not new and has appeared in one of their previous work. A notable feature in their two main theorems in the paper (Theorem 2.1 and Theorem 3.1 and their equivalence) is that both describe models in which the number of edges significantly exceeds its mean. The lower tail of the edge count more likely satisfies Poisson-like statistics. Also, its large deviation principle holds with speed \(\mu_n\) on expected grounds with no appearance of a ``giant clique'' mentioned in Theorem 2.1. Further, they carry out all their discussion done on discrete set up to continuum platform by proving several estimates that show the discrete setting of the \(s\)-graded model approximates the continuous geometry of \(T^d\). The results are deep and well written. My special praise goes to Lemmas 6.2 and 6.3 and Proposition 7.1. To sum up, the authors have done a massive work and it is no doubt a very noteworthy contribution.