Scaling Limits of Random Graphs from Subcritical Classes

Abstract

We study the uniform random graph ${\mathsf{C}}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph ${\mathsf{C}}_n/\sqrt{n}$ converges to the Brownian Continuum Random Tree ${\mathcal{T}}_{\mathsf{e}}$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter $\text{D}({\mathsf{C}}_n)$ and height $\text{H}({\mathsf{C}}_n^{\bullet })$ of the rooted random graph ${\mathsf{C}}_n^{\bullet }$. We give analytic expressions for the scaling factor of several classes, including for example the prominent class of outerplanar graphs. Our methods also enable us to study first passage percolation on ${\mathsf{C}}_n$, where we show the convergence to ${\mathcal{T}}_{\mathsf{e}}$ under an appropriate rescaling.