On breadth‐first constructions of scaling limits of random graphs and random unicellular maps. Issue 4 (7th January 2022)

• Record Type: Journal Article
• Authors: Miermont, Grégory; Sen, Sanchayan
• Is Part Of: Random structures & algorithms. Volume 61:Issue 4(2022)
• Page Start: 803
• Page End: 843
• Publication Date: 2022-01-07
• Subjects: breadth‐first construction -- continuum random trees -- critical random graphs -- depth‐first construction -- Erdős–Rényi random graph -- Gromov–Hausdorff distance -- scaling limit -- unicellular maps; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21076
• Languages: English
• ISSNs: 1042-9832

Abstract

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 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 by Addario‐Berry, Broutin, and Goldschmidt. 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.