×

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
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] 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
[2] 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.
[3] 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
[4] Azuma, K. (1967). Weighted sums of certain dependent random variables. Tohoku Math. J. (2) 19 357-367. · Zbl 0178.21103
[5] 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
[6] Burago, J. D. and Zalgaller, V. A. (1980). Geometric Inequalities. “Nauka” Leningrad. Otdel., Leningrad. · Zbl 0436.52009
[7] Chatterjee, S. (2012). The missing log in large deviations for triangle counts. Random Structures Algorithms 40 437-451. · Zbl 1246.05140
[8] Chatterjee, S. (2016). An introduction to large deviations for random graphs. Bull. Amer. Math. Soc. (N.S.) 53 617-642. · Zbl 1356.60044
[9] 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
[10] Chatterjee, S. and Dembo, A. (2016). Nonlinear large deviations. Adv. Math. 299 396-450. · Zbl 1356.60045
[11] Cook, N. A. and Dembo, A. (2018). Large deviations of subgraph counts for sparse Erdos-Renyi graphs. Preprint. Available at arXiv:1809.11148.
[12] DeMarco, B. and Kahn, J. (2012). Upper tails for triangles. Random Structures Algorithms 40 452-459. · Zbl 1246.05142
[13] Dembo, A. and Zeitouni, O. (2010). Large Deviations Techniques and Applications. Stochastic Modelling and Applied Probability 38. Springer, Berlin. · Zbl 1177.60035
[14] Eldan, R. (2018). Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations. Geom. Funct. Anal. 28 1548-1596. · Zbl 1428.60045
[15] Federer, H. (1969). Geometric Measure Theory. Die Grundlehren der Mathematischen Wissenschaften 153. Springer, New York.
[16] 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
[17] Gilbert, E. N. (1961). Random plane networks. J. Soc. Indust. Appl. Math. 9 533-543. · Zbl 0112.09403
[18] 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
[19] Grimmett, G. (1999). Percolation, 2nd ed. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 321. Springer, Berlin. · Zbl 0926.60004
[20] Hafner, R. (1972). The asymptotic distribution of random clumps. Computing (Arch. Elektron. Rechnen) 10 335-351. · Zbl 0258.60012
[21] Harel, M., Mousset, F. and Samotij, W. (2019). Upper tails via high moments and entropic stability. Preprint. Available at arXiv:1904.08212.
[22] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13-30. · Zbl 0127.10602
[23] Janson, S. (1984). Bounds on the distributions of extremal values of a scanning process. Stochastic Process. Appl. 18 313-328. · Zbl 0549.60066
[24] Janson, S. (2004). Large deviations for sums of partly dependent random variables. Random Structures Algorithms 24 234-248. · Zbl 1044.60021
[25] 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
[26] Janson, S. and Ruciński, A. (2002). The infamous upper tail 20 317-342. · Zbl 0996.60023
[27] Kim, J. H. and Vu, V. H. (2000). Concentration of multivariate polynomials and its applications. Combinatorica 20 417-434. · Zbl 0969.60013
[28] Klain, D. A. and Rota, G.-C. (1997). Introduction to Geometric Probability. Lezioni Lincee. [Lincei Lectures]. Cambridge Univ. Press, Cambridge.
[29] 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
[30] Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge Tracts in Mathematics 119. Cambridge Univ. Press, Cambridge.
[31] Müller, T. (2008). Two-point concentration in random geometric graphs. Combinatorica 28 529-545. · Zbl 1175.05118
[32] Nagaev, S. V. (1979). Large deviations of sums of independent random variables. Ann. Probab. 7 745-789. · Zbl 0418.60033
[33] Penrose, M. (2003). Random Geometric Graphs. Oxford Studies in Probability 5. Oxford Univ. Press, Oxford.
[34] Penrose, M. D. (2002). Focusing of the scan statistic and geometric clique number. Adv. in Appl. Probab. 34 739-753. · Zbl 1031.60046
[35] 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.
[36] Petersen, P. (2006). Riemannian Geometry, 2nd ed. Graduate Texts in Mathematics 171. Springer, New York. · Zbl 1220.53002
[37] 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
[38] Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 73-205. · Zbl 0864.60013
[39] 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.