# zbMATH — the first resource for mathematics

Localization in random geometric graphs with too many edges. (English) Zbl 1446.60024
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 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.

##### MSC:
 60F10 Large deviations 05C80 Random graphs (graph-theoretic aspects) 60D05 Geometric probability and stochastic geometry
Full Text:
##### References:
  Alon, N. and Spencer, J. H. (2008). The Probabilistic Method, 3rd ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Hoboken, NJ. · Zbl 1148.05001  Augeri, F. (2018). Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in Erdos-Renyi graphs. Preprint. Available at arXiv:1810.01558.  Avin, C. and Ercal, G. (2007). On the cover time and mixing time of random geometric graphs. Theoret. Comput. Sci. 380 2-22. · Zbl 1115.68167  Azuma, K. (1967). Weighted sums of certain dependent random variables. Tohoku Math. J. (2) 19 357-367. · Zbl 0178.21103  Bhattacharya, B. B., Ganguly, S., Lubetzky, E. and Zhao, Y. (2017). Upper tails and independence polynomials in random graphs. Adv. Math. 319 313-347. · Zbl 1370.05099  Burago, J. D. and Zalgaller, V. A. (1980). Geometric Inequalities. “Nauka” Leningrad. Otdel., Leningrad. · Zbl 0436.52009  Chatterjee, S. (2012). The missing log in large deviations for triangle counts. Random Structures Algorithms 40 437-451. · Zbl 1246.05140  Chatterjee, S. (2016). An introduction to large deviations for random graphs. Bull. Amer. Math. Soc. (N.S.) 53 617-642. · Zbl 1356.60044  Chatterjee, S. (2017). A note about the uniform distribution on the intersection of a simplex and a sphere. J. Topol. Anal. 9 717-738. · Zbl 1379.35288  Chatterjee, S. and Dembo, A. (2016). Nonlinear large deviations. Adv. Math. 299 396-450. · Zbl 1356.60045  Cook, N. A. and Dembo, A. (2018). Large deviations of subgraph counts for sparse Erdos-Renyi graphs. Preprint. Available at arXiv:1809.11148.  DeMarco, B. and Kahn, J. (2012). Upper tails for triangles. Random Structures Algorithms 40 452-459. · Zbl 1246.05142  Dembo, A. and Zeitouni, O. (2010). Large Deviations Techniques and Applications. Stochastic Modelling and Applied Probability 38. Springer, Berlin. · Zbl 1177.60035  Eldan, R. (2018). Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations. Geom. Funct. Anal. 28 1548-1596. · Zbl 1428.60045  Federer, H. (1969). Geometric Measure Theory. Die Grundlehren der Mathematischen Wissenschaften 153. Springer, New York.  Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971). Correlation inequalities on some partially ordered sets. Comm. Math. Phys. 22 89-103. · Zbl 0346.06011  Gilbert, E. N. (1961). Random plane networks. J. Soc. Indust. Appl. Math. 9 533-543. · Zbl 0112.09403  Goel, A., Rai, S. and Krishnamachari, B. (2005). Monotone properties of random geometric graphs have sharp thresholds. Ann. Appl. Probab. 15 2535-2552. · Zbl 1098.60011  Grimmett, G. (1999). Percolation, 2nd ed. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 321. Springer, Berlin. · Zbl 0926.60004  Hafner, R. (1972). The asymptotic distribution of random clumps. Computing (Arch. Elektron. Rechnen) 10 335-351. · Zbl 0258.60012  Harel, M., Mousset, F. and Samotij, W. (2019). Upper tails via high moments and entropic stability. Preprint. Available at arXiv:1904.08212.  Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13-30. · Zbl 0127.10602  Janson, S. (1984). Bounds on the distributions of extremal values of a scanning process. Stochastic Process. Appl. 18 313-328. · Zbl 0549.60066  Janson, S. (2004). Large deviations for sums of partly dependent random variables. Random Structures Algorithms 24 234-248. · Zbl 1044.60021  Janson, S., Oleszkiewicz, K. and Ruciński, A. (2004). Upper tails for subgraph counts in random graphs. Israel J. Math. 142 61-92. · Zbl 1055.05136  Janson, S. and Ruciński, A. (2002). The infamous upper tail 20 317-342. · Zbl 0996.60023  Kim, J. H. and Vu, V. H. (2000). Concentration of multivariate polynomials and its applications. Combinatorica 20 417-434. · Zbl 0969.60013  Klain, D. A. and Rota, G.-C. (1997). Introduction to Geometric Probability. Lezioni Lincee. [Lincei Lectures]. Cambridge Univ. Press, Cambridge.  Lubetzky, E. and Zhao, Y. (2017). On the variational problem for upper tails in sparse random graphs. Random Structures Algorithms 50 420-436. · Zbl 1364.05063  Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge Tracts in Mathematics 119. Cambridge Univ. Press, Cambridge.  Müller, T. (2008). Two-point concentration in random geometric graphs. Combinatorica 28 529-545. · Zbl 1175.05118  Nagaev, S. V. (1979). Large deviations of sums of independent random variables. Ann. Probab. 7 745-789. · Zbl 0418.60033  Penrose, M. (2003). Random Geometric Graphs. Oxford Studies in Probability 5. Oxford Univ. Press, Oxford.  Penrose, M. D. (2002). Focusing of the scan statistic and geometric clique number. Adv. in Appl. Probab. 34 739-753. · Zbl 1031.60046  Penrose, M. D. and Yukich, J. E. (2005). Normal approximation in geometric probability. In Stein’s Method and Applications. Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. 5 37-58. Singapore Univ. Press, Singapore.  Petersen, P. (2006). Riemannian Geometry, 2nd ed. Graduate Texts in Mathematics 171. Springer, New York. · Zbl 1220.53002  Schreiber, T. and Yukich, J. E. (2005). Large deviations for functionals of spatial point processes with applications to random packing and spatial graphs. Stochastic Process. Appl. 115 1332-1356. · Zbl 1073.60022  Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 73-205. · Zbl 0864.60013  Talagrand, M. (2003). Spin Glasses: A Challenge for Mathematicians. Cavity and Mean Field Models. Ergebnisse der Mathematik und Ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics] 46. Springer, Berlin.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.