Convergence of sparse graphs as a problem at the intersection of graph theory, statistical physics and probility
| Speaker: | Christan Borgs |
|---|---|
| Affiliation: | Microsoft Research New England |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Many real-world graphs are large and growing. This naturally raises the question of a suitable concept of graph convergence. For graphs with average degree proportional to the number of vertices (dense graphs), this question is by now quite well-studied. But real world graphs tend to be sparse, in the sense that the average or even the maximal degree is bounded by some reasonably small constant. In this talk, I study several notions of convergence for graphs of bounded degree and show that, in contrast to dense graphs, where various a priori different notions of convergence are equivalent, the corresponding notions are not equivalent for sparse graphs. I then describe a notion of convergence formulated in terms of a large deviation principle which implies all previous notions of convergence. No prior knowledge of graph convergence or large deviation theory is needed.