Videos

L^p Theory of Sparse Graph Limits

Presenter
May 19, 2015
Keywords:
  • Sparse matrices
MSC:
  • 65F50
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^∞ theory of dense graph limits and its extension by Bollobas 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 a much larger class of graphs, including those with power law degree distributions. This gives the first broadly applicable limit theory for sparse graphs with unbounded average degrees. We also show the equivalence of many nonlocal notions of sparse convergence. This talk assumes no prior knowledge of graphons. Joint work with Christian Borgs, Henry Cohn, and Yufei Zhao.