An $L^p$ theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
HTML articles powered by AMS MathViewer
- by Christian Borgs, Jennifer T. Chayes, Henry Cohn and Yufei Zhao PDF
- Trans. Amer. Math. Soc. 372 (2019), 3019-3062 Request permission
Abstract:
We introduce and develop a theory of limits for sequences of sparse graphs based on $L^p$ graphons, which generalizes both the existing $L^\infty$ theory of dense graph limits and its extension by Bollobás and Riordan to sparse graphs without dense spots. In doing so, we replace the no dense spots hypothesis with weaker assumptions, which allow us to analyze graphs with power law degree distributions. This gives the first broadly applicable limit theory for sparse graphs with unbounded average degrees. In this paper, we lay the foundations of the $L^p$ theory of graphons, characterize convergence, and develop corresponding random graph models, while we prove the equivalence of several alternative metrics in a companion paper.References
- David Aldous and Russell Lyons, Processes on unimodular random networks, Electron. J. Probab. 12 (2007), no. 54, 1454–1508. MR 2354165, DOI 10.1214/EJP.v12-463
- David Aldous and J. Michael Steele, The objective method: probabilistic combinatorial optimization and local weak convergence, Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 1–72. MR 2023650, DOI 10.1007/978-3-662-09444-0_{1}
- Noga Alon and Joel H. Spencer, The probabilistic method, 3rd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2008. With an appendix on the life and work of Paul Erdős. MR 2437651, DOI 10.1002/9780470277331
- Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13. MR 1873300, DOI 10.1214/EJP.v6-96
- P. J. Bickel and A. Chen, A nonparametric view of network models and Newman–Girvan and other modularities, Proc. Natl. Acad. Sci. USA 106 (2009), 21068–21073. 10.1073/pnas.0907096106.
- Béla Bollobás and Oliver Riordan, Metrics for sparse graphs, Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., vol. 365, Cambridge Univ. Press, Cambridge, 2009, pp. 211–287. MR 2588543
- Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Yufei Zhao, An $L^p$ theory of sparse graph convergence II: LD convergence, quotients and right convergence, Ann. Probab. 46 (2018), no. 1, 337–396. MR 3758733, DOI 10.1214/17-AOP1187
- C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), no. 6, 1801–1851. MR 2455626, DOI 10.1016/j.aim.2008.07.008
- C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs II. Multiway cuts and statistical physics, Ann. of Math. (2) 176 (2012), no. 1, 151–219. MR 2925382, DOI 10.4007/annals.2012.176.1.2
- Sourav Chatterjee and S. R. S. Varadhan, The large deviation principle for the Erdős-Rényi random graph, European J. Combin. 32 (2011), no. 7, 1000–1017. MR 2825532, DOI 10.1016/j.ejc.2011.03.014
- Aaron Clauset, Cosma Rohilla Shalizi, and M. E. J. Newman, Power-law distributions in empirical data, SIAM Rev. 51 (2009), no. 4, 661–703. MR 2563829, DOI 10.1137/070710111
- Amin Coja-Oghlan, Colin Cooper, and Alan Frieze, An efficient sparse regularity concept, SIAM J. Discrete Math. 23 (2009/10), no. 4, 2000–2034. MR 2594968, DOI 10.1137/080730160
- David Conlon and Jacob Fox, Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), no. 5, 1191–1256. MR 2989432, DOI 10.1007/s00039-012-0171-x
- David Conlon, Jacob Fox, and Yufei Zhao, Extremal results in sparse pseudorandom graphs, Adv. Math. 256 (2014), 206–290. MR 3177293, DOI 10.1016/j.aim.2013.12.004
- David Conlon, Jacob Fox, and Yufei Zhao, A relative Szemerédi theorem, Geom. Funct. Anal. 25 (2015), no. 3, 733–762. MR 3361771, DOI 10.1007/s00039-015-0324-9
- Rick Durrett, Probability: theory and examples, 4th ed., Cambridge Series in Statistical and Probabilistic Mathematics, vol. 31, Cambridge University Press, Cambridge, 2010. MR 2722836, DOI 10.1017/CBO9780511779398
- Helmut Finner, A generalization of Hölder’s inequality and some probability inequalities, Ann. Probab. 20 (1992), no. 4, 1893–1901. MR 1188047
- Péter E. Frenkel, Convergence of graphs with intermediate density, Trans. Amer. Math. Soc. 370 (2018), no. 5, 3363–3404. MR 3766852, DOI 10.1090/tran/7036
- Alan Frieze and Ravi Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, 175–220. MR 1723039, DOI 10.1007/s004930050052
- Ben Green and Terence Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481–547. MR 2415379, DOI 10.4007/annals.2008.167.481
- W. Hoeffding, The strong law of large numbers for $U$-statistics, North Carolina State University, Institute of Statistics Mimeograph Series No. 302, 1961. http://repository.lib.ncsu.edu/dr/handle/1840.4/2128
- Svante Janson, Graphons, cut norm and distance, couplings and rearrangements, New York Journal of Mathematics. NYJM Monographs, vol. 4, State University of New York, University at Albany, Albany, NY, 2013. MR 3043217
- Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997) Springer, Berlin, 1997, pp. 216–230. MR 1661982
- Y. Kohayakawa and V. Rödl, Szemerédi’s regularity lemma and quasi-randomness, Recent advances in algorithms and combinatorics, CMS Books Math./Ouvrages Math. SMC, vol. 11, Springer, New York, 2003, pp. 289–351. MR 1952989, DOI 10.1007/0-387-22444-0_{9}
- D. Kunszenti-Kovács, L. Lovász, and B. Szegedy, Multigraph limits, unbounded kernels, and Banach space decorated graphs, preprint, 2014. arXiv:1406.7846
- László Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR 3012035, DOI 10.1090/coll/060
- László Lovász and Balázs Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933–957. MR 2274085, DOI 10.1016/j.jctb.2006.05.002
- László Lovász and Balázs Szegedy, Szemerédi’s lemma for the analyst, Geom. Funct. Anal. 17 (2007), no. 1, 252–270. MR 2306658, DOI 10.1007/s00039-007-0599-6
- Eyal Lubetzky and Yufei Zhao, On replica symmetry of large deviations in random graphs, Random Structures Algorithms 47 (2015), no. 1, 109–146. MR 3366814, DOI 10.1002/rsa.20536
- Russell Lyons, Asymptotic enumeration of spanning trees, Combin. Probab. Comput. 14 (2005), no. 4, 491–522. MR 2160416, DOI 10.1017/S096354830500684X
- Michael Mitzenmacher, A brief history of generative models for power law and lognormal distributions, Internet Math. 1 (2004), no. 2, 226–251. MR 2077227
- Jaroslav Ne et il and Patrice Ossona de Mendez, Sparsity, Algorithms and Combinatorics, vol. 28, Springer, Heidelberg, 2012. Graphs, structures, and algorithms. MR 2920058, DOI 10.1007/978-3-642-27875-4
- Jaroslav Ne et il and Patrice Ossona de Mendez, A model theory approach to structural limits, Comment. Math. Univ. Carolin. 53 (2012), no. 4, 581–603. MR 3016428
- J. Nešetřil and P. Ossona de Mendez, A unified approach to structural limits and limits of graphs with bounded tree-depth, preprint, 2013. arXiv:1303.6471
- Jaroslav Ne et il and Patrice Ossona de Mendez, Modeling limits in hereditary classes: reduction and application to trees, Electron. J. Combin. 23 (2016), no. 2, Paper 2.52, 33. MR 3522136
- Alexander Scott, Szemerédi’s regularity lemma for matrices and sparse graphs, Combin. Probab. Comput. 20 (2011), no. 3, 455–466. MR 2784637, DOI 10.1017/S0963548310000490
- Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
- P. J. Wolfe and S. C. Olhede, Nonparametric graphon estimation, preprint, 2013. arXiv:1309.5936
Additional Information
- Christian Borgs
- Affiliation: Microsoft Research, One Memorial Drive, Cambridge, Massachusetts 02142
- MR Author ID: 39645
- Email: borgs@microsoft.com
- Jennifer T. Chayes
- Affiliation: Microsoft Research, One Memorial Drive, Cambridge, Massachusetts 02142
- Email: jchayes@microsoft.com
- Henry Cohn
- Affiliation: Microsoft Research, One Memorial Drive, Cambridge, Massachusetts 02142
- MR Author ID: 606578
- ORCID: 0000-0001-9261-4656
- Email: cohn@microsoft.com
- Yufei Zhao
- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- MR Author ID: 864404
- Email: yufeiz@mit.edu
- Received by editor(s): July 9, 2017
- Received by editor(s) in revised form: January 27, 2018
- Published electronically: May 30, 2019
- Additional Notes: The fourth author was supported by a Microsoft Research Ph.D. Fellowship and internships at Microsoft Research New England.
- © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 372 (2019), 3019-3062
- MSC (2010): Primary 05C80; Secondary 60C05
- DOI: https://doi.org/10.1090/tran/7543
- MathSciNet review: 3988601