Scaling Limits of Random Graphs from Subcritical Classes

2014/11/07 by Konstantinos Panagiotou, Benedikt Stufler, Panagiotou, Konstantinos +3
Mathematics · #05C80 #60C05 #60F17 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C80 #msc:60C05 #msc:60F17

paper · pdf · doi:10.48550/arxiv.1411.1865

arxiv created 2014/11/14 · arxiv updated 2014/11/17

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 rescaled graph C_n / √(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 subgaussian tail bounds for the diameter D(C_n) and height H(C_n^\bullet) of the rooted random graph 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 C_n, where we show the convergence to T_e under an appropriate rescaling.

Related

• Scaling limits and universality: Critical percolation on weighted graphs converging to an L³ graphon
• On breadth-first constructions of scaling limits of random graphs and random unicellular maps
• Scaling limits of random graphs
• The GHP scaling limit of uniform spanning trees in high dimensions
• Scaling limit of critical percolation clusters on hyperbolic random half-planar triangulations and the associated random walks