Scaling limits of random graphs from subcritical classes

Konstantinos Panagiotou ^[2] ; Benedikt Stufler ^[2] ; Kerstin Weller ^[1]
1. [1] Swiss Federal Institute of Technology in Zurich
  
  Swiss Federal Institute of Technology in Zurich
  
  Zürich, Suiza
2. [2] University of Munich
Localización: Annals of probability: An official journal of the Institute of Mathematical Statistics, ISSN 0091-1798, Vol. 44, Nº. 5, 2016, págs. 3291-3334
Idioma: inglés
DOI: 10.1214/15-AOP1048
Enlaces
- Texto completo
Resumen
- We study the uniform random graph CnCn with nn vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph Cn/n−−√Cn/n converges to the Brownian continuum random tree TeTe 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(Cn)D(Cn) and height H(C∙n)H(Cn∙) of the rooted random graph C∙nCn∙. 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 CnCn, where we also show the convergence to TeTe under an appropriate rescaling.