Sparse graph limits and scale-free networks

21 January 2014
Yufei Zhao
<p>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.</p> <p>Joint work with Christian Borgs, Jennifer T. Chayes, and Henry Cohn.</p>
  • Combinatorial Theory Seminar