Campuses:

L^p Theory of Sparse Graph Limits

Tuesday, May 19, 2015 - 10:20am - 11:10am
Keller 3-180
Jennifer Chayes (Microsoft Research)
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.
MSC Code: 
65F50
Keywords: