On breadth-first constructions of scaling limits of random graphs and random unicellular maps

Abstract

We give alternate constructions of (i) the scaling limit of the uniform connected graphs with given fixed surplus, and (ii) the continuum random unicellular map (CRUM) of a given genus that start with a suitably tilted Brownian continuum random tree and make `horizontal' point identifications, at random heights, using the local time measures. Consequently, this can be seen as a continuum analogue of the breadth-first construction of a finite connected graph. In particular, this yields a breadth-first construction of the scaling limit of the critical Erdős-Rényi random graph which answers a question posed in [2]. As a consequence of this breadth-first construction we obtain descriptions of the radii, the distance profiles, and the two point functions of these spaces in terms of functionals of tilted Brownian excursions.

arXiv comment39 pages, 7 figures; to appear in Random Structures & Algorithms

References in corpus (8)

• Random trees and applications
• The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity
• Random graph asymptotics on high-dimensional tori. II. Volume, diameter and mixing time
• Heavy-tailed configuration models at criticality
• The coding of compact real trees by real valued functions
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Geometry of the minimal spanning tree of a random $3$-regular graph

Cited by in corpus (3)

• Global lower mass-bound for critical configuration models in the heavy-tailed regime
• Geometry of the minimal spanning tree of a random $3$-regular graph
• Epidemics on critical random graphs with heavy-tailed degree distribution