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 abstractArticle

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

We study the uniform random graph $\mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_n / \sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_{\mathsf{e}}$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter $\text{D}(\mathsf{C}_n)$ and height $\text{H}(\mathsf{C}_n^\bullet)$ of the rooted random graph $\mathsf{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 $\mathsf{C}_n$, where we show the convergence to $\mathcal{T}_{\mathsf{e}}$ 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 313 times.
This article's PDF has been downloaded 487 times.