REVIEW 4 major objections 4 minor 40 references
On breadth-first constructions of scaling limits of random graphs and random unicellular maps
T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Uniform connected graphs with a fixed surplus admit a breadth-first scaling limit built from a tilted Brownian tree by gluing leaves at random heights.
desk verdict A genuinely new breadth-first construction with two load-bearing technical gaps that deserve a careful referee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing machinery pairs a discrete exploration with a continuum convergence statement. On the discrete side, the breadth-first exploration of a uniformly random map with fixed surplus produces a uniform plane tree together with admissible corner pairs, counted by the breadth-first weight $B(f)=\sum_i B(f;i)$, where $B(f;i)$ is the number of later corners at height equal to or one below the current height. The continuum limit of this weight is $2\int_0^\infty \eta(e;1,y)^2\,dy$, exactly the tilt used in Construction 2.2. The passage to the limit rests on Proposition 5.5, the joint convergence in $C([0,1]\times\mathbb{R})$ of the rescaled contour process $(2n)^{-1/2}C_n(2nt)$ and the two-parameter local-time field $(2n)^{-1/2}L_n(2nt,y\sqrt{2n})$ to $(e,\eta(e;\cdot,\cdot))$, together with Gaussian tail bounds that make the tilted discrete weights uniformly integrable. Jeulin's local-time identity $\int_0^\infty \eta(e;1,y)^2\,dy \stackrel{d}{=} 2\int_0^1 e(t)\,dt$ connects this breadth-first tilt to the area tilt of the depth-first Construction 2.1, which is why the two constructions can describe the same space.
What would settle it
Compute the joint limit in $C([0,1]\times\mathbb{R})$ of $((2n)^{-1/2}C_n(2nt), (2n)^{-1/2}L_n(2nt,y\sqrt{2n}))$ for uniform plane trees; if this pair fails to converge to $(e,\eta(e;\cdot,\cdot))$ along some subsequence, Proposition 5.5—and with it the convergence of the gluing heights and times—is false. A simpler check: simulate large critical Erdős-Rényi components, measure the distance profile around a uniformly chosen vertex, and compare with the claimed limit $\tfrac12\eta(e^{\mathrm{BF}}_{(s)};1,r/2)$; a systematic mismatch would refute Corollary 3.2(iii) and Theorem 3.4.
Extended reading notes
Core claim
Theorem 3.1 asserts that for every $s \ge 0$, the scaling limit $H(s)$ of uniform connected labeled graphs with $s$ surplus edges has the same distribution as a space $H^{\mathrm{BF}}_{(s)}$ built as follows: sample a Brownian excursion $e^{\mathrm{BF}}_{(s)}$ tilted by the $s$-th power of $\int_0^\infty \eta(e;1,y)^2\,dy$, sample heights $H_1,\dots,H_s$ with density proportional to squared local time, and at each sampled height identify two independent leaves of the encoded tree, then double all distances. Theorem 3.5 proves the analogous statement for the continuum random unicellular map $\mathrm{CRUM}(g)$: it equals the space obtained by gluing together $4g$ leaves in pairs dictated by a random transposition structure. The breadth-first spanning tree of the limiting space is then simply the tilted Brownian tree itself. Consequently the radius of $H(s)$ is $2\|e^{\mathrm{BF}}_{(s)}\|_\infty$, the two-point distance is $2e^{\mathrm{BF}}_{(s)}(U)$ for an independent uniform $U$, and the distance profile is half the local time of the tilted excursion.
Load-bearing premise
The whole argument rests on the joint convergence of the rescaled contour process and the two-parameter local-time field of uniform plane trees to the Brownian excursion and its local time (Proposition 5.5), a convergence the paper only sketches; if it fails in the required topology, the heights and times of the identifications in Construction 2.2 need not converge to the claimed limit, and the existence of the $\mathrm{CRUM}(g)$ limit is assumed as a separate input.
Editorial extensions
If this is right
- If Theorem 3.1 is correct, the scaling limit of critical Erdős-Rényi random graphs—and the wider family of mean-field random graph models it governs—admits a breadth-first construction, answering the question posed in the paper's introduction.
- The radius of $H(s)$ has the law of $2\|e^{\mathrm{BF}}_{(s)}\|_\infty$; for $s \ge 1$ this also equals $\int_0^1 dt/e^{\mathrm{DF}}_{(s)}(t)$, extending the classical height identity for the Brownian continuum random tree.
- The two-point function of $H(s)$ is $2e^{\mathrm{BF}}_{(s)}(U)$ with $U$ uniform and independent, and the distance profile around the root is $\tfrac12\eta(e^{\mathrm{BF}}_{(s)};1,r/2)$.
- The rescaled number of vertices at distance $\lfloor r\sqrt{n}\rfloor$ from the root of $H_{n,s}$ converges in Skorokhod $J_1$ topology to that local-time profile, extending the known height-profile convergence for random trees to graphs with surplus.
- The same radius, two-point, and distance-profile formulas hold for $\mathrm{CRUM}(g)$ with the tilted excursion $e^{\mathrm{UM}}_{(g)}$ replacing $2e^{\mathrm{BF}}_{(s)}$.
Reading between the lines
- Beyond the paper, the equality $H(s) \stackrel{d}{=} H^{\mathrm{BF}}_{(s)}$ suggests a continuum self-duality between depth-first and breadth-first explorations of the same random metric space; comparing the two codings could yield new identities for Brownian excursion functionals.
- Because the construction glues only leaves at equal heights, the diameter of $H(s)$ should be expressible as twice the largest height at which two independent local-time samples lie in different branches of the tilted excursion, a quantity the paper does not compute.
- The assumed convergence (2.9) defining $\mathrm{CRUM}(g)$ is an input to Theorem 3.5; if an independent proof of that convergence appeared, the breadth-first description of $\mathrm{CRUM}(g)$ would follow without further work.
- The same gluing scheme could be attempted for the $\alpha$-stable analogues of random graphs discussed in the paper's final section, provided a two-parameter local-time convergence of the kind conjectured there holds.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes continuum 'breadth-first' constructions for two families of random measured R-graphs: the scaling limits H(s) of uniform connected graphs with fixed surplus s, which include the critical Erdős-Rényi scaling limit, and the continuum random unicellular maps CRUM(g) of fixed genus. In Construction 2.2, a tilted Brownian excursion e^BF_(s) is sampled, s heights are drawn from the squared total local time, and pairs of leaves at those heights are identified using the local-time measure; in Construction 2.3 an analogous procedure is carried out with a random permutation in S(g). The main theorems assert H(s) = H^BF_(s) and CRUM(g) = CRUM^BF_(g). The proof proceeds through discrete breadth-first and depth-first explorations of uniform maps (Section 5.1), the discrete approximations in Propositions 5.1 and 5.2, and a joint convergence of the rescaled contour process with its two-parameter local-time field (Proposition 5.5, with proof outlined in Appendix A). The paper also derives corollaries for the radius, the two-point function, and the distance profile, together with a result on convergence of distance profiles (Theorem 3.4).
Significance. If the main theorems are valid, the paper gives the first breadth-first construction of the critical Erdős-Rényi scaling limit, answering a question raised in [2], and provides explicit descriptions of the radius, two-point function, and distance profile of H(s) and CRUM(g) that are not immediate from the depth-first or core-decomposition constructions. The combinatorial encodings in Section 5.1, the tilted discrete models (5.7)-(5.8), and the uniform-integrability arguments around (5.18)-(5.19) are careful and plausible. The main analytic input, namely the joint convergence of contour process and local-time field, is, however, only sketched, and the convergence (2.9) defining CRUM(g) is assumed without a written proof; consequently the theorems as stated are conditional on completing these parts.
major comments (4)
- [Appendix A, Eq. (A.11) and the Vervaat step] Proposition 5.5 is load-bearing for Proposition 5.1: equations (5.18), (5.21), (5.22), and (5.24) all use the joint convergence (Cbar_n, Lbar_n) to (e, eta(e;.,.)) to identify the limiting heights and times of the identifications in Construction 2.2. The proof in Appendix A is an outline: after (A.9), the passage to the full bridge is deferred to (A.11), which is asserted as immediate from time reversal without proof, and the Vervaat transform step says only that (A.1) follows from (A.10). Please supply a complete proof of (A.11), including control of sup_y (ellbar^br_n(1,y)-ellbar^br_n(1-epsilon,y)), and of the joint convergence of the argmin with the path and the local-time field under the Vervaat transform, or cite a published result containing the full statement.
- [Section 2.2 and Theorem 3.5, Eq. (2.9)] The convergence (2.9) that defines CRUM(g) is not proved in the manuscript; the text states that a proof 'seems' not to be in the literature and 'can be deduced' by following [1] or [2]. Since Theorem 3.5 is a statement about this space, the equality CRUM(g) = CRUM^BF(g) is conditional on an unproved existence and identification result. Please either prove (2.9) or restate Theorem 3.5 and Corollary 3.6 explicitly as conditional on (2.9).
- [Section 5.7, after (5.71)-(5.72)] The completion of the proof of Theorem 3.5 is omitted with 'We omit the details as no new idea is involved here.' The convergences in (5.71)-(5.72) concern the tilted contour process, the permutation, the heights, and the times, but the theorem is about pointed GHP convergence of the glued metric measure spaces. Please provide the quotient-space convergence argument, including an analogue of the correspondence argument after (5.25) and control of the measure under the identifications.
- [Section 5.3, Eq. (5.27)] In the proof of Lemma 5.3, the claim that the pointed GHP distance between (2n)^{-1/2} G^o_{n,s} and Gbar_{n,s} tends to 0 is declared routine and the details are omitted. This step converts the line-measure quotient convergence into the convergence of the vertex-measure graph spaces, and it is part of the proof of Proposition 5.1; please spell it out or refer to an existing lemma that covers it.
minor comments (4)
- [Section 5.6] The display 'We set bf(G)=t and bf(G)=bar{t}' uses the same symbol bf for both the breadth-first tree and its symmetrization; please use distinct notation, for example overline{bf}(G), throughout that argument.
- [Section 2.2, Eq. (2.11)] The normalization constant in (2.11) is derived only later in (5.70); a forward reference would help the reader understand why the expression defines a probability measure.
- [Section 5.5, Eq. (5.49)] In the use of Jeulin's identity, the equality in distribution in (5.50) and the statement 'jointly with' (5.51) should specify the coupling used; the current wording is slightly ambiguous about whether the two identities hold jointly with the same e.
- [Section 5.2] In the sentence after (5.4), the symbol M_{n,s} is used both for the uniform map and for the rooted metric measure space with the non-root vertices carrying mass 1/n; please make the passage to the metric measure space explicit, for instance by writing (M_{n,s}, d, root, mu).
Circularity Check
No circularity: H(s)=H^BF(s) and CRUM(g)=CRUM^BF(g) are proved via independent discrete bijections and external convergence results, not by fitting the target into the construction.
full rationale
The derivation chain is not circular. The spaces H(s) and CRUM(g) are defined by independent GHP limits (2.3) and (2.9), while H^BF(s) and CRUM^BF(g) are defined by explicit tilted Brownian excursion and local-time sampling constructions (Constructions 2.2 and 2.3). Theorem 3.1 proves equality in distribution by passing through two discrete models: the breadth-first and depth-first explorations of uniform maps are bijections (5.4), Proposition 5.1 sends the breadth-first discrete model to H^BF(s), and Proposition 5.2 sends the depth-first discrete model to H(s). The limiting target spaces are not used as parameters in the approximations, and no equation defining one object assumes the equality being proved. Jeulin's local-time identity (5.49)-(5.50) is used as an external classical tool to evaluate constants, not to define either space. The paper is transparent that two convergence inputs are not fully written out: Proposition 5.5's joint contour/local-time convergence is only outlined in Appendix A, and the existence of the CRUM limit in (2.9) is explicitly noted as not proved in the literature. These are completeness and correctness risks, not circularity: the claimed reductions are genuine consequences of the stated convergences and bijections, and filling the gaps would not turn the argument into a definitional identity. There is no self-citation chain invoked to rule out alternative constructions, and the external benchmarks [2,3] provide independent targets rather than assumed conclusions.
Assumptions & free parameters
assumptions (4)
- domain assumption The scaling limits H(s) and CRUM(g) exist and converge as in (2.3) and (2.9), based on [2], [15], [6], and a deduction from [1] or [2].
- domain assumption Proposition 5.5 (equation (5.14)): the joint convergence of the rescaled contour process and local time field of uniform plane trees to a Brownian excursion and its local time holds in C([0,1]×R).
- standard math Standard enumeration asymptotics for plane trees and maps, e.g., #Mn,0 ~ ... and #UMn,g ~ ... in (5.62)-(5.63), from [18], [27], [37], [38].
- standard math Sub-Gaussian tail bounds for heights and widths of Galton-Watson trees (Theorem 5.6, from [5]).
Cite this review
Pith. "Pith review of On breadth-first constructions of scaling limits of random graphs and random unicellular maps." pith.science (2026). https://pith.science/paper/DILITEI3
@misc{pith2026190804403,
author = {Pith},
title = {Pith review of: On breadth-first constructions of scaling limits of random graphs and random unicellular maps},
year = {2026},
howpublished = {\url{https://pith.science/paper/DILITEI3}},
note = {Machine review of arXiv:1908.04403}
}
read the original 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\H{o}s-R\'enyi 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.
Reference graph
Works this paper leans on
-
[2]
L. Addario-Berry, N. Broutin, and C. Goldschmidt, The continuum limit of critical random graphs , Probab. Theory Related Fields 152 (2012), no. 3-4, 367–406. MR2892951
work page 2012
-
[1]
L. Addario-Berry, N. Broutin, and C. Goldschmidt, Critical random graphs: limiting constructions and distributional properties, Electron. J. Probab. 15 (2010), no. 25, 741–775. MR2650781 (2011d:60025)
work page 2010
-
[3]
L. Addario-Berry, O. Angel, G. Chapuy, É. Fusy, and C. Goldschmidt,Voronoi tessellations in the CRT and continuum random maps of finite excess , Proceedings of the Twenty-Ninth Annual ACM-SIAM Sympo- sium on Discrete Algorithms, 2018, pp. 933–946
work page 2018
-
[4]
L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont,The scaling limit of the minimum span- ning tree of the complete graph, The Annals of Probability 45 (2017), no. 5, 3075–3144
work page 2017
-
[5]
L. Addario-Berry, L. Devroye, and S. Janson, Sub-gaussian tail bounds for the width and height of con- ditioned galton–watson trees, The Annals of Probability 41 (2013), no. 2, 1072–1087
work page 2013
-
[6]
Geometry of the minimal spanning tree of a random $3$-regular graph
L. Addario-Berry and S. Sen, Geometry of the minimal spanning tree of a random 3-regular graph, arXiv preprint arXiv:1810.03802 (2018)
work page Pith review arXiv 2018
-
[7]
Aldous, The continuum random tree
D. Aldous, The continuum random tree. I, Ann. Probab. 19 (1991), 1–28
work page 1991
-
[8]
Aldous, The continuum random tree III, Ann
D. Aldous, The continuum random tree III, Ann. Probab. 21 (1993), 248–289
work page 1993
Show all 40 references
-
[9]
Aldous, The continuum random tree II: an overview, Stochastic analysis 167 (1991), 23–70
D. Aldous, The continuum random tree II: an overview, Stochastic analysis 167 (1991), 23–70
1991
-
[10]
Aldous, G
D. Aldous, G. Miermont, and J. Pitman, The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identity , Probab. Theory Related Fields 129 (2004), no. 2, 182–218. MR2063375 (2005f:60023)
2004
-
[11]
F Bass and D
R. F Bass and D. Khoshnevisan, Rates of convergence to Brownian local time , Stochastic processes and their applications 47 (1993), no. 2, 197–213
1993
-
[12]
Bhamidi, N
S. Bhamidi, N. Broutin, S. Sen, and X. Wang, Scaling limits of random graph models at criticality: Uni- versality and the basin of attraction of the Erd˝ os-Rényi random graph, arXiv preprint arXiv:1411.3417 (2014)
2014 arXiv
-
[13]
Bhamidi, S
S. Bhamidi, S. Dhara, R. van der Hofstad, and S. Sen, Universality for critical heavy-tailed network mod- els: metric structure of maximal components, arXiv preprint arXiv:1703.07145 (2017)
2017 arXiv
-
[14]
Bhamidi, R
S. Bhamidi, R. v. d. Hofstad, and S. Sen, The multiplicative coalescent, inhomogeneous continuum ran- dom trees, and new universality classes for critical random graphs, Probability Theory and Related Fields 170 (2018), no. 1-2, 387–474
2018
-
[15]
Bhamidi and S
S. Bhamidi and S. Sen, Geometry of the vacant set left by random walk on random graphs, Wright’s con- stants, and critical random graphs with prescribed degrees , To appear in Random Structures & Algo- rithms (2019+)
2019
-
[16]
Bhamidi, S
S. Bhamidi, S. Sen, and X. Wang,Continuum limit of critical inhomogeneous random graphs, Probability Theory and Related Fields 169 (2017), no. 1-2, 565–641
2017
-
[17]
Biane, J
P . Biane, J. Pitman, and M. Yor, Probability laws related to the jacobi theta and riemann zeta functions, and brownian excursions, Bulletin of the American Mathematical Society 38 (2001), no. 4, 435–465
2001
-
[18]
Chapuy, The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees, Probability Theory and Related Fields 147 (2010), no
G. Chapuy, The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees, Probability Theory and Related Fields 147 (2010), no. 3-4, 415–447
2010
-
[19]
Csáki and P
E. Csáki and P . Révész,Strong invariance for local times, Zeitschrift f˝ or Wahrscheinlichkeitstheorie und Verwandte Gebiete 62 (1983), no. 2, 263–278
1983
-
[20]
Dembo, A
A. Dembo, A. Levit, and S. Vadlamani, Component sizes for large quantum erd˝ os–rényi graph near criti- cality, The Annals of Probability 47 (2019), no. 2, 1185–1219
2019
-
[21]
Dhara, R
S. Dhara, R. v. d. Hofstad, J. v. Leeuwaarden, and S. Sen,Critical configuration models with infinite third- moment degrees, arXiv preprint arXiv:1612.00650 (2016)
2016 arXiv
-
[22]
Drmota and B
M. Drmota and B. Gittenberger, On the profile of random trees , Random Structures & Algorithms 10 (1997), no. 4, 421–451
1997
-
[23]
Duquesne, The coding of compact real trees by real valued functions, arXiv preprint math (2006)
T . Duquesne, The coding of compact real trees by real valued functions, arXiv preprint math (2006). 38 MIERMONT AND SEN
2006
-
[24]
S. N. Evans, Probability and real trees, Lecture Notes in Mathematics, vol. 1920, Springer, Berlin, 2008. Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23, 2005. MR2351587 (2009d:60014)
1920
-
[25]
Flajolet and R
P . Flajolet and R. Sedgewick,Analytic combinatorics, Cambridge University press, 2009
2009
-
[26]
Goldschmidt, B
C. Goldschmidt, B. Haas, and D. Sénizergues, Stable graphs: distributions and line-breaking construc- tion, arXiv preprint arXiv:1811.06940 (2018)
2018 arXiv
-
[27]
Goupil and G
A. Goupil and G. Schaeffer, Factoringn-cycles and counting maps of given genus , European Journal of Combinatorics 19 (1998), no. 7, 819–834
1998
-
[28]
Heydenreich and R
M. Heydenreich and R. v. d. Hofstad, Random graph asymptotics on high-dimensional tori , Comm. Math. Phys. 270 (2007), no. 2, 335–358. MR2276449
2007
-
[29]
Heydenreich and R
M. Heydenreich and R. v. d. Hofstad, Random graph asymptotics on high-dimensional tori II: volume, diameter and mixing time, Probab. Theory Related Fields 149 (2011), no. 3-4, 397–415. MR2776620
2011
-
[30]
R. v. d. Hofstad and A. Nachmias, Hypercube percolation, Preprint (2012). To appear in Journ. Europ. Math. Soc
2012
-
[31]
R. v. d. Hofstad and A. Sapozhnikov, Cycle structure of percolation on high-dimensional tori , Ann. Inst. Henri Poincaré Probab. Stat.50 (2014), no. 3, 999–1027. MR3224297
2014
-
[32]
Janson, Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas, Probab
S. Janson, Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas, Probab. Surv.4 (2007), 80–145. MR2318402
2007
-
[33]
Jeulin and M
Th. Jeulin and M. Yor (eds.), Grossissements de filtrations: exemples et applications , Lecture Notes in Mathematics, vol. 1118, Springer-Verlag, Berlin, 1985. Papers from the seminar on stochastic calculus held at the Université de Paris VI, Paris, 1982/1983. MR884713
1985
-
[34]
Le Gall,Random trees and applications, Probab
J.-F . Le Gall,Random trees and applications, Probab. Surv.2 (2005), 245–311. MR2203728 (2007h:60078)
2005
-
[35]
Marckert and A
J.-F . Marckert and A. Mokkadem, The depth first processes of Galton-Watson trees converge to the same Brownian excursion, Annals of probability (2003), 1655–1678
2003
-
[36]
P Révész, Local time and invariance, Analytical methods in probability theory, 1981, pp. 128–145
1981
-
[37]
Spencer, Enumerating graphs and Brownian motion, Communications on Pure and Applied Mathe- matics 50 (1997), no
J. Spencer, Enumerating graphs and Brownian motion, Communications on Pure and Applied Mathe- matics 50 (1997), no. 3, 291–294
1997
-
[38]
T . R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. I , J. Combinatorial Theory Ser. B 13 (1972), 192–218. MR314686
1972
-
[39]
Wang, Height and diameter of brownian tree, Electronic Communications in Probability 20 (2015)
M. Wang, Height and diameter of brownian tree, Electronic Communications in Probability 20 (2015)
2015
-
[40]
M Wright, The number of connected sparsely edged graphs , Journal of Graph Theory 1 (1977), no
E. M Wright, The number of connected sparsely edged graphs , Journal of Graph Theory 1 (1977), no. 4, 317–330
1977
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.