Konstantinos Panagiotou ; Benedikt Stufler ; Kerstin Weller - Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract

dmtcs:2461 - Discrete Mathematics & Theoretical Computer Science, January 1, 2015, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015) - https://doi.org/10.46298/dmtcs.2461
Scaling Limits of Random Graphs from Subcritical Classes: Extended abstractConference paper

Authors: Konstantinos Panagiotou 1,2; Benedikt Stufler ORCID1,2; Kerstin Weller 3

We study the uniform random graph Cn with n vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph Cn/n converges to the Brownian Continuum Random Tree Te multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter D(Cn) and height H(Cn) of the rooted random graph Cn. 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 Cn, where we show the convergence to Te under an appropriate rescaling.


Volume: DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Section: Proceedings
Published on: January 1, 2015
Imported on: November 21, 2016
Keywords: Scaling Limits,Random Graphs,Continuum Random Trees,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 388 times.
This article's PDF has been downloaded 568 times.