Random enriched trees with applications to random graphs

Benedikt Stufler

Published 2015-04-08Version 1

We study a model of random $\mathcal{R}$-enriched trees that is based on weights on the $\mathcal{R}$-structures and allows for a unified treatment of a large variety of random trees, graphs and tree-like structures. As their size tends to infinity, these random structures converge locally to an infinite enriched tree and we give applications of this convergence to random graphs. We consider random metrics on random labelled and unlabelled enriched trees patched together from independently drawn metrics on the $\mathcal{R}$-structures. Under certain conditions we show convergence in the Gromov-Hausdorff sense towards the Brownian continuum random tree and sharp tail bounds for their diameter. We apply our results to models of random graphs and trees, in particular to first passage percolation on random unlabelled graphs drawn from a subcritical block-class, random P\'olya trees drawn according to weights on the vertex outdegrees, and loop-trees of critical Galton-Watson trees conditioned to be large.