Random graphs with finite excess appear naturally in at least two different settings: random graphs in the critical window (aka critical percolation on regular and other classes of graphs), and unicellular maps of fixed genus. In the first situation, the scaling limit of such random graphs was obtained by Addario-Berry, Broutin and Goldschmidt based on a depth-first exploration of the graph and on the coding of the resulting forest by random walks. This idea originated in Aldous' work on the critical random graph, using instead a breadth-first search approach that seem less adapted to taking graph scaling limits. We show hat this can be done nevertheless, resulting in some new identities for quantities like the radius and the two-point function of the scaling limit. We also obtain a similar "breadth-first" construction of the scaling limit of unicellular maps of fixed genus. This is based on joint work with Sanchayan Sen.
- Combinatorial Theory Seminar