Disorder models for random graphs, Erdos’s leader problem, and power of limited choice models for network evolution

Shankar Bhamidi, UNC
Fine Hall 224

First passage percolation, and more generally the study of diffusion of material through disordered systems is a fundamental area in probabilistic combinatorics with a vast body of work especially in the context of spatial systems.  The goal of this talk is to survey a slightly different setting for such questions namely the more “mean-field” setting of random graph models. We will describe the state of the art of this field, with the final goal of describing one of the main conjectures in this area namely the conjectured scaling limit of the minimal spanning tree and its dependence on the degree exponent of the corresponding network model. We will describe recent progress in this area, its connection to questions in dynamic network models, in particular Erdos’s leader problem for the identity of the maximal component for critical random graphs, and the intuition for understanding the evolution of maximal components through the critical scaling window from a different area of probabilistic combinatorics, namely the study of limited choice models for network evolution.