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

Understand

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\'as 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.