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

2019/08/12 by Grégory Miermont, Miermont, Grégory, Sanchayan Sen +1 · 2 citations
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Geometry and complex manifolds #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1908.04403

openalex publication_date 2019/08/12 · openalex created_date 2019/08/22 · openalex updated_date 2026/07/28

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.

Cited by

• Geometry of critical discrete structures: percolation on the hierarchical lattice
• Geometry of the minimal spanning tree of a random 3-regular graph
• Epidemics on critical random graphs with heavy-tailed degree distribution

Related

• Scaling limits of random graphs
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• Continuum limit of critical inhomogeneous random graphs
• Scaling limits and universality: Critical percolation on weighted graphs converging to an L³ graphon
• Critical random graphs: limiting constructions and distributional properties