Scaling limits of random graphs from subcritical classes

Panagiotou, Konstantinos; Stufler, Benedikt; Weller, Kerstin (2016): Scaling limits of random graphs from subcritical classes. In: Annals of Probability, Vol. 44, No. 5: pp. 3291-3334

Abstract

We study the uniform random graph C-n with n vertices drawn from a subcritical class of connected graphs. Our main result is that the resealed graph C-n / root n converges to the Brownian continuum random tree T-e multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide sub-Gaussian tail bounds for the diameter D (C-n) and height H(C-n(center dot)) of the rooted random graph C-n(center dot) We give analytic expressions for the scaling factor in several cases, including for example the class of outerplanar graphs. Our methods also enable us to study first passage percolation on C-n, where we also show the convergence to T-e under an appropriate rescaling.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics
• Subjects: 500 Science > 510 Mathematics
• ISSN: 0091-1798
• Language: English