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
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(C∙n) of the rooted random graph C∙n. 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.
Marie Albenque;Christina Goldschmidt, 2015, The Brownian continuum random tree as the unique solution to a fixed point equation, Electronic Communications in Probability, 20, none, 10.1214/ecp.v20-4250, https://doi.org/10.1214/ecp.v20-4250.