 |
Discrete Mathematics & Theoretical Computer Science |
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
1,2; Kerstin Weller 3
- 1 Ludwig Maximilian University [Munich]
- 2 Ludwig Maximilian University [Munich] = Ludwig Maximilians Universität München
- 3 Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]
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.