Convergence of sparse graphs as a problem at the intersection of graph theory, statistical physics and probability

ACO Seminar
Tuesday, November 26, 2013 - 2:05pm
1 hour (actually 50 minutes)
Skiles 005
Microsoft Research (New England), Cambridge, MA
  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.