Probability Seminar

Sanchayan SenCourant Institute at New York University
The structure of critical inhomogeneous random graphs

Monday, March 10, 2014 - 4:00pm
Malott 406

Since the work of Bollobas, Janson and Riordan (2007, Random Struct. Alg.), there has been increasing interest in the study of inhomogeneous random graphs. Consider the random graph on $n$ vertices constructed from i.i.d. positive random variables $w_1, \ldots,w_n$ by placing an edge between vertex $i$ and vertex $j$ with probability $1-\exp(-w_i w_j / \sum_{k=1}^n w_k)$ independently for each $i\neq j$. This model corresponds to the rank-1 case of the general inhomogeneous random graphs. The random graph is critical if $E(w_1)=E(w_1^2)$. The study of the critical behavior for this model was initiated by van der Hofstad (2012, Random Struct. Alg.).

In the present work, we show that after assigning mass $w_i/n^{2/3}$ to vertex $i$ and scaling the graph distance by $n^{1/3}$, the components of this graph (at criticality) viewed as measured metric spaces converge in Gromov-Hausdorff-Prokhorov topology to some limiting (random) compact, measured metric spaces if $w_1$ satisfies appropriate conditions. This result also addresses the question of universality of the continuum limit of the components (viewed as measured metric spaces) of critical Erdos-Renyi random graphs.

Joint work with Shankar Bhamidi, Amarjit Budhiraja and Xuan Wang.