Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

An $ L^p$ theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions


Authors: Christian Borgs, Jennifer T. Chayes, Henry Cohn and Yufei Zhao
Journal: Trans. Amer. Math. Soc.
MSC (2010): Primary 05C80; Secondary 60C05
DOI: https://doi.org/10.1090/tran/7543
Published electronically: May 30, 2019
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C80, 60C05

Retrieve articles in all journals with MSC (2010): 05C80, 60C05


Additional Information

Christian Borgs
Affiliation: Microsoft Research, One Memorial Drive, Cambridge, Massachusetts 02142
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
Email: cohn@microsoft.com

Yufei Zhao
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: yufeiz@mit.edu

DOI: https://doi.org/10.1090/tran/7543
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.
Article copyright: © Copyright 2019 American Mathematical Society