Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

A random walk among random graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read These master lecture notes contend that a handful of probabilistic tools—random-walk encodings, moment methods, exploration processes, and continuous-time embeddings—gives a unified route through random graphs, branching trees, and random…

desk verdict Lecture notes, not research: solid pedagogical value, but the Wiener–Hopf sign inconsistency and unresolved placeholders need fixing before publication. read the letter →

arxiv 2412.19752 v1 pith:JPLPOMBF submitted 2024-12-27 math.PR math.CO

Nicolas Curien This is my paper · ORCID
classification math.PRmath.CO MSC 60G5060J8005C8060K3560F17
keywords randomgraphswalksbranchingprocessesErdős–RényigraphgiantcomponentŁukasiewiczwalkcontinuumtreepreferentialattachment
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is a set of lecture notes from a master course, so its central claim is pedagogical: the main models of random graph theory can be learned through a small family of probabilistic tools rather than as isolated facts. It argues that the same ideas—first and second moments, the cycle lemma, Łukasiewicz encodings, Markov exploration with fluid limits, and continuous-time embedding—recur across percolation, Bienaymé–Galton–Watson trees, Erdős–Rényi graphs, random recursive trees, and Barabási–Albert networks. A sympathetic reader comes away with working derivations of several deep results, including the sharp threshold for connectedness, the emergence of the giant component, Catalan and Cayley tree counts, and the power-law degree distribution of preferential attachment.

What carries the argument

The central object is the Łukasiewicz walk: for a plane tree, list vertices in breadth-first order and take steps equal to (#children − 1). This turns a tree into a skip-free random walk, so the cycle lemma, Kemperman's formula, and ballot theorems compute tree counts, hitting times, and extinction probabilities. For G(n,p), the corresponding tool is the exploration process (stack, untouched, and explored vertices), a Markov chain with Binomial increments that converges, via the differential-equation method, to the fluid limit f_c. Continuous-time Yule trees and spinal decomposition play the same unifying role for random recursive and preferential-attachment trees.

What would settle it

Simulate the exploration of G(n,c/n) for c=0.8, 1, and 1.2 with n=$10^{5}$, and compare the empirical largest-component fraction and the number of components with the predicted values 1−α(c) and n·α(c)(2−cα(c))/2; if they do not converge to these quantities, the fluid-limit derivation of Chapter 7 is wrong.

Watch

Extended reading notes

Core claim

The paper's central claim is didactic: a reader who masters a compact set of probabilistic techniques can derive the main theorems of random graph theory rather than taking them on faith. The key reduction is the Łukasiewicz walk, which encodes a plane tree as a skip-free random walk, making Feller's cycle lemma and Kemperman's formula available for enumeration and hitting-time problems. The same walk appears as the exploration process of the Erdős–Rényi graph G(n,p), whose increments are Binomial; a fluid-limit argument shows the rescaled exploration converges to a deterministic function f_c, from which the giant-component phase transition at c=1 and the logarithmic bounds on smaller components follow. The notes extend the method to random permutations through Feller coupling, to random recursive trees through the Chinese restaurant process and Pólya urns, and to Barabási–Albert trees through Yule-process embedding and spinal decomposition.

Load-bearing premise

The course presupposes a reader already comfortable with measure-theoretic probability, martingales, and Fourier analysis, and it imports deep external theorems without proof, such as the local central limit theorem and the Aldous–Le Gall convergence to the Brownian continuum random tree; if any of those external results is misstated or the reader lacks the background, the self-contained pedagogical promise collapses.

Editorial extensions

If this is right

  • For G(n,c/n) with c<1, all connected components have size O(log n) with high probability; for c>1, a unique giant component carries fraction 1−α(c) of the vertices and the second-largest component has size O(log n).
  • The number of connected components of G(n,c/n) divided by n converges to α(c)(2−cα(c))/2, where α(c) solves α=e^{-c(1−α)}.
  • Plane trees with prescribed out-degrees are counted by (n−1)!/∏ d_i!, and the Catalan numbers count plane trees; both follow from the Łukasiewicz walk and the cycle lemma.
  • A uniform plane tree's typical height, after normalization by √n, converges to a Rayleigh law, and the same limit holds for uniform Cayley trees.
  • The random recursive tree has height of order e log n and maximal degree of order log n/log log n, while the Barabási–Albert tree has a power-law degree distribution with exponent 3.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exploration–fluid-limit scheme shown for G(n,p) is generic: for stochastic block models or configuration models, the same Markov exploration with different increment distributions should yield coupled ODE limits and giant-component thresholds, a route the notes only gesture at.
  • The cycle-lemma/Kemperman-formula engine that produces parking-function probabilities and tree counts is likely to give distributional results for cluster sizes in the critical Erdős–Rényi window by conditioning the same random walks.
  • The three proofs of the giant component form a hierarchy: the ε-cut proof establishes the density but not the logarithmic bounds, the exploration proof refines it, and the Poissonized version smooths the critical window; this hierarchy is a transferable template for proving phase transitions in other random graph models.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The manuscript is a set of lecture notes from a master course, covering one-dimensional random walks and skip-free walks, the cycle lemma and Wiener–Hopf factorization, Bienaymé–Galton–Watson trees and their Łukasiewicz encodings, local properties of Erdős–Rényi graphs, three proofs of the giant-component phase transition, random permutations, random recursive trees, continuous-time embeddings, spine decompositions, and the Barabási–Albert preferential attachment tree. The stated goal in the introduction is to give a glimpse of several random-graph models together with the probabilistic tools used to study them, at the master/PhD level, rather than to provide an authoritative reference. The notes contain many worked examples, exercises, historical remarks, and explicit pointers to the literature.

Significance. If corrected, the notes would fulfill their stated pedagogical goal: they present a coherent selection of standard material with several detailed proofs, including the Łukasiewicz encoding, Kemperman's formula, and the exploration-process proof of the giant component. The multiple proofs of the emergence of the giant component and the explicit computations of Borel–Tanner and Catalan laws are notable strengths. No new research theorem is claimed, so the natural standard of assessment is internal correctness and pedagogical clarity. By that standard the manuscript is not yet ready, because one load-bearing tool section contains an unresolved sign inconsistency and the draft contains unresolved placeholders; these issues can be fixed locally, and the rest of the exposition is largely sound.

major comments (2)
  1. [§3.4.2, Theorem 3.12 and Remark 3.4] The sign conventions in the Wiener–Hopf factorization are inconsistent. The second display of Theorem 3.12 asserts 1 − E[r^{T_1^≤} e^{μ H_1^≤}] = exp(−Σ_n r^n/n E[e^{μ S_n} 1_{S_n≤0}]), while Remark 3.4 defines ω_r^≤(μ) with e^{−μ S_n} on the same event and then states the factorization ω_r^>(it) ω_r^≤(it) = 1 − r E[e^{−it X_1}] in (3.7). With the theorem's displayed factors, setting μ = it gives e^{−it S_n} on {S_n > 0} and e^{+it S_n} on {S_n ≤ 0}, so the product is not 1 − r E[e^{−it X_1}]. Because the proof derives only the first display and says the second is “similar”, a reader cannot resolve the discrepancy from the text. This is load-bearing for a central tool in Part I and needs correction: either the second display, the definition in Remark 3.4, or the identity (3.7) must be changed consistently.
  2. [§3.4.2, proof of Theorem 3.12] The statement “the calculation is similar for the second one” is not sufficient once the displayed signs disagree with the surrounding definitions. Even if the intended version is the standard Spitzer–Baxter formula, the manuscript should either prove the second display with the exact conventions used, or state both factors through a common convention and verify the product identity (3.7) explicitly. As written, the gap is not merely cosmetic: it prevents the reader from using the theorem to reproduce the factorization in Remark 3.4.
minor comments (4)
  1. [Notations] In the definition of [z^n] f(z), the text writes f(z) = Σ_{i≥0} f_i z^i ∈ C[[X]]; the ring should be C[[z]], since the indeterminate is z rather than X.
  2. [Corollary 3.2] In the proof of Corollary 3.2, the text says “whereas since (S) drifts towards −∞” but the assumption of the corollary is that (S) drifts towards +∞. The intended statement is that the running infimum S_n converges to the finite limit S_∞, so the wording should be corrected.
  3. [§2.4, Bibliographical notes] The line “Theorem ?? can be found in [102]” is an unresolved cross-reference placeholder and should be completed before submission.
  4. [Chapter 3, Bibliographical notes] The heading “Biliographical notes” is a typo for “Bibliographical notes”.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lecture notes are self-contained pedagogical derivations from stated definitions and standard external results; only minor editorial defects (unresolved citation and a sign-convention mismatch) were found, neither of which is circular.

full rationale

I found no circular derivation chain in these lecture notes. The paper does not claim to prove a new theorem whose output coincides with an input by construction; it is an expository survey presenting standard material (random walks, BGW trees, Erdős–Rényi graphs, random recursive trees) with proofs of classical results such as the cycle lemma, Kemperman's formula, the fluid limit of the exploration process, and the giant-component phase transition. The derivations are carried out from explicitly stated definitions and from external, standard results (e.g. Gnedenko's local CLT, the Aldous–Le Gall scaling limit), not from the author's own prior work, and no fitted parameter is later renamed as a prediction. There is no self-citation that is load-bearing, no imported uniqueness theorem from the author's papers, and no ansatz smuggled in via citation. The only flagged items are non-circular editorial defects: the bibliographic note in Section 2.4.1 contains the unresolved placeholder 'Theorem ?? can be found in [102]', and Theorem 3.12's second display appears to use a sign convention for exp(mu H_1^le) that is inconsistent with the definition of omega_r^le in Remark 3.4 and the product identity (3.7). These are correctness/completeness concerns that could mislead a master's-level reader, but they do not make the derivation circular. The paper is self-contained as lecture notes against standard external benchmarks, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

As an exposition, the paper introduces no free parameters and no invented entities. Its axioms are the standard tools of probability theory that are explicitly stated or cited.

assumptions (5)
  • standard math Hewitt–Savage exchangeable 0-1 law (Theorem 2.3)
    Used to show events invariant under finite permutations have probability 0 or 1.
  • standard math Strong Markov property for random walks (Proposition 2.2)
    Used repeatedly for hitting times and ladder epochs.
  • standard math Gnedenko local central limit theorem (Theorem 2.10)
    Cited as a black box to deduce asymptotic probabilities of hitting times.
  • domain assumption Aldous–Le Gall convergence to Brownian continuum random tree (Theorem 4.14)
    Invoked to justify scaling limits of conditioned BGW trees.
  • domain assumption Kahn–Kalai expectation threshold theorem (Chapter 5)
    Mentioned as a deep external result; not proved in the notes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A random walk among random graphs." pith.science (2026). https://pith.science/paper/JPLPOMBF

@misc{pith2026241219752,
  author       = {Pith},
  title        = {Pith review of: A random walk among random graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JPLPOMBF}},
  note         = {Machine review of arXiv:2412.19752}
}
read the original abstract

Lecture notes of a master course given at Orsay between 2019-2024. Topics covered include Part I: One-dimensional random walks, cycle lemma and Bienaym\'e--Galton--Watson random trees. Part II: Erd\"os--R\'enyi random graphs, three proofs of the emergence of the giant component. Part III: Random recursive tree, random permutations and continuous time embedding techniques. Intended for publication.

Figures

Figures reproduced from arXiv: 2412.19752 by the authors.

Figure 1.1
Figure 1.1. Increasing Bernoulli percolation on a complete binary tree up to level 10 with parameters p = 0.2, 0.4, 0.5 and p = 0.6 from left to right. 1.1 Basics on graphs A graph1 𝔤 is a pair 𝔤 = (V(𝔤),E(𝔤)), where V = V(𝔤) is the set of vertices of 𝔤 and E = E(𝔤) is the set of edges of 𝔤 which is a multiset ( i.e. where repetitions are allowed) over the set {V 2 } of all unordered pairs of elements of V . The graph is simple… view at source ↗
Figure 1.2
Figure 1.2. Increasing Bernoulli percolation on a 50 × 50 grid with parameters p = 0.35, p = 0.45, p = 0.55 and p = 0.65. Notice the appearance of an ubiquitous cluster between the second and the third picture. 1 2 3 4 5 2 3 5 2 3 4 5 4 g g ′ g[{2, 3, 4, 5}] [PITH_FULL_IMAGE:figures/full_fig_p012_1_2.png] view at source ↗
Figure 1.3
Figure 1.3. (Left) An example of a graph 𝔤 = (V,E) with vertex set V = {1,2,3,4,5} and edge set E = {{{1,1}, {1,2}, {1,2}, {1,3}, {3,2}, {2,5}, {3,5}}}. The vertex degrees of 1,2,3,4 in 𝔤 are respectively 5,3,2,0. (Center) An example of a subgraph 𝔤 ′ ⊏ 𝔤 and (Right) the subgraph induced on the vertices 2,3,4,5. no ambiguity) is the number of half-edges adjacent to x, otherwise said it is the number of edges adjacent to x where… view at source ↗
Figures from the paper (56 more)
Figure 1.4
Figure 1.4. Figure 1.4: If the cluster of the origin is finite, then it is surrounded by a blocking dual self-avoiding cycle of length at least 4. Since the dual graph of 𝔷2 is 𝔷2 itself, there are at most 4 · 3 n−1 dual cycles of length n starting from the origin, and at most n · 4 · 3 n−1…
Figure 1.5
Figure 1.5. Figure 1.5: A large critical Bienaym´e–Galton–Watson tree with finite variance 20 [PITH_FULL_IMAGE:figures/full_fig_p021_1_5.png]
Figure 2.1
Figure 2.1. Figure 2.1: Two samples of one-dimensional random walks with different step distributions. The first one seems continuous at large scales whereas the second one displays macroscopic jumps. Notice that we restrict (for simplicity) to the lattice case by demanding that the support…
Figure 3.1
Figure 3.1. Figure 3.1: Geometric interpretation of the duality: the rotation by an angle 𝜋 of the first n steps of the walk (S ) leaves its distribution invariant. Beware, the duality lemma can only be applied for n fixed and not for all n simultaneously, yet it can be useful to deduce asy…
Figure 3.2
Figure 3.2. Figure 3.2: Duality shows that P(TZ<0 > n) = P(n is a weak ascending record time). Exercise 3.1. Let (S ) be a centered skip-free random walk. Show using duality that for any k ⩾ 1 we have P(STZ>0 = k) = 1 𝜇−1 ∑︁ i⩾k 𝜇i . 3.1.2 A proof of the law of large numbers To illustrate t…
Figure 3.3
Figure 3.3. Figure 3.3: Re-rooting the walk at the hitting time of the minimum gives a walk reaching its minimum at time n. We can thus suppose without loss of generality that time n is the hitting time of −k by the walk. It is now clear (again see [PITH_FULL_IMAGE:figures/full_fig_p043_3_3.png]
Figure 3.4
Figure 3.4. Figure 3.4: The only possible cycle shifts (starting points in blue) for which the walk first hit −k at time n correspond to the hitting times of 0,−1,−2,. . . ,−k + 1. 3.2.1 Kemperman’s formula and applications Notice that Lemma 3.1 does not require that the random walk has i.i…
Figure 3.5
Figure 3.5. Figure 3.5: The arcsine distribution Remark 3.3. The name arcsine comes from the cumulative distribution function of the right￾hand side which is 2 𝜋 arcsin( √ x). Quoting Feller “Contrary to intuition, the maximum accu￾mulated gain is much more likely to occur towards the very …
Figure 3.6
Figure 3.6. Figure 3.6: Illustration of the parking of 6 cars on a line with 6 spots. Notice that car number 6 did not manage to find a spot and exited the parking lot. Below, the encoding of that the parking configuration by a skip-free ascending walk. An Abelian property shows that the un…
Figure 3.7
Figure 3.7. Figure 3.7: Illustration of the definition of the ladder heights and epochs. When 𝜇 has no atoms, the walk S does not take twice the same value a.s. so the weak and strict ladder variables are the same. In the following we write H and T generically for one of the four couples (T…
Figure 4.1
Figure 4.1. Figure 4.1: A large Bienaym´e–Galton–Watson tree and its contour function 4.1 Plane trees and Bienaym´e–Galton–Watson processes 4.1.1 Plane trees Throughout this chapter we will use the standard formalism for plane trees as found in [94]. Let U = Ø∞ n=0 (Z>0) n 55 [PITH_FULL_IM…
Figure 4.2
Figure 4.2. Figure 4.2: A (representation of a) finite plane tree. Since every u ∈ 𝜏\{∅} has a unique parent, we deduce that for finite plane trees 𝜏 we have #𝜏 − 1 = ∑︁ u∈𝜏 ku (𝜏). (4.1) A plane tree can be seen as a graph, in which an edge links two vertices u,v such that u is the parent …
Figure 4.3
Figure 4.3. Figure 4.3: Left: a finite plane tree and its vertices listed in breadth-first order. Right: its associated Lukasiewicz walk. • the Łukasiewicz walk starts at 0, i.e. W0(𝜏) = 0, • it stays non-negative as long as all vertices have not been explored, i.e. Wi (𝜏) ⩾ 0 for 0 ⩽ i ⩽ #…
Figure 4.4
Figure 4.4. Figure 4.4: Fixing the first n vertices explored (in red) during the breadth first exploration of a BGW tree. The black vertices and their subtrees (in gray) have not been explored yet. Extinction probability. As a direct application of the previous proposition let us give a ran…
Figure 4.5
Figure 4.5. Figure 4.5: Illustration of the “standard” proof Theorem 4.3. The extinction probability is computed as the limit of the recursive system defined by u0 = 0 and un+1 = g (un). Exercise 4.1 (A theorem of Dekking [42] and a discontinuous phase transition). We say that an infinite t…
Figure 4.6
Figure 4.6. Figure 4.6: Plot of the function g (z) + (1 − z)g ′ (z) against the first bissector (in blue) where g (z) = (1 − p)z + pz 3 for the values p = 1 2 , 2 3 , 4 5 in (yellow, green, red), the critical case p = 8 9 in purple and p = 1 in brown. 4.2.3 Lagrange inversion formula The La…
Figure 4.7
Figure 4.7. Figure 4.7: Interpretation of [z 4 ]𝜙(z) in diagrammatic form. Similarly for k ⩾ 1, the coefficient of z n in 𝜙 k is the total weight of forests of k trees having n vertices in total. Now, using the Łukasiewicz encoding, such a forest can be encoded by a skip-free descending pat…
Figure 4.8
Figure 4.8. Figure 4.8: A Cayley tree over {1,2,3,4,. . . ,11}. Let T be a BGW (plane) tree with Poisson offspring distribution of parameter 1 (in particular, the mean number of children is 1 and we are in the critical case). As in the previous subsection (but with vertices instead of edges…
Figure 4.9
Figure 4.9. Figure 4.9: Illustration of the graph of the mapping 1 → 6,2 → 9,3 → 4,4 → 6,5 → 10,6 → 3,7 → 7,8 → 7,9 → 1,10 → 13,11 → 1,12 → 8,13 → 5. 1. Prove that #Cn has the same law as Dn in Corollary 4.11. 2. Show that P(the (unoriented) graph of Mn is connected) = 1 n n−2 ∑︁n k=1  n k…
Figure 4.10
Figure 4.10. Figure 4.10: The corners are ordered clockwise cyclically around the tree in the so-called contour order. If 𝜏 has n ⩾ 2 vertices we index the corners by letting (c0,c1 ,c2,. . . ,c2n−3) be the sequence of corners visited during the contour process of 𝜏, starting from the corner…
Figure 4.11
Figure 4.11. Figure 4.11: Illustration of the Gromov–Hausdorff distance: to compare two metric spaces, first embed them in a common metric space and use the Hausdorff distance. Theorem 4.13 The space (K,d) is a Polish metric space (i.e. separable and complete). We refer the reader to [28, Ch…
Figure 2
Figure 2. Figure 2: De gauche à droite : un arbre avec 6 sommets, sa fonction de contour associée, puis la fonction de contour (convenablement renormalisée en temps et en espace) d’un grand arbre de Bienaymé–Galton–Watson (de loi de repro￾duction critique et de variance finie), qui conver…
Figure 4.13
Figure 4.13. Figure 4.13: A list of the 1044 simple graphs on 7 vertices up to isomorphism. 79 [PITH_FULL_IMAGE:figures/full_fig_p080_4_13.png]
Figure 5.1
Figure 5.1. Figure 5.1: Illustration of the sharp threshold transition for an increasing graph property: the functions x ↦→ P(G (n,x ·pn) ∈ An) converge pointwise on [0,∞)\{1} towards the step function 1x<1 . Exercise 5.2. Let An be a non-empty increasing graph property. Show that there exi…
Figure 5.2
Figure 5.2. Figure 5.2: A graph having the core property: a single component (in red in the figure) together with isolated vertices (in blue). This property is however not stable by addition of edges. 83 [PITH_FULL_IMAGE:figures/full_fig_p084_5_2.png]
Figure 5.3
Figure 5.3. Figure 5.3: The possibilities for the induced subgraph on two pairs of vertices (here in red and blue) so that the distance between elements of each pair is at least 3. The contribution of this case to the sum is then asymptotic to n 4 4 e −2np2 n ∼ E[Dn] 2 . 87 [PITH_FULL_IMAG…
Figure 5.4
Figure 5.4. Figure 5.4: A plot of limn→∞ P(G (n, c n ) has no simple cycle) for c ∈ [0,1]. In particular the appearance of a simple cycle has no sharp threshold, but such a cycle should appear before c = 1. Recalling the first section of this chapter, although the presence of isolated verti…
Figure 5.5
Figure 5.5. Figure 5.5: Simulations of Λ (n) c for c = 2 and c = 10. where (∗) and (∗∗) are the expected measures which are deterministic probability measures on R. The convergence in probability of the random measure Λ (n) c is obtained by further establishing concentration of the empirica…
Figure 5.6
Figure 5.6. Figure 5.6: Expanding the expectation using a sum over Feynman diagrams. The only non zero asymptotic contribution comes from the trees with possibly several edges. this case k = 2ℓ must be even and those objects are finite (non plane) trees with e ⩽ ℓ edges together with an ima…
Figure 6.1
Figure 6.1. Figure 6.1: A large G (n, c n ) graph with n = 1000 and c equals (from left to right) to 0.1 0.5 1 1.1 log n 2 2 log n. We see the emergence of a giant component around c ≈ 1 and that the graph becomes connected around c ≈ log n (see Theorem 5.2). 97 [PITH_FULL_IMAGE:figures/fu…
Figure 7.1
Figure 7.1. Figure 7.1: The Lukasiewicz exploration of a random graph. The edges revealed during the exploration are in thick lines, they form spanning trees of each compo￾nents. The concatenation (ordered by the minimal label of their component) of the Lukasiewicz paths associated to those…
Figure 7.2
Figure 7.2. Figure 7.2: Plot of the function f2: it follows the orange curve from 0 to 1−𝛼(2) ≈ 0.797 and then the blue curve from 1 − 𝛼(2) to 1. In particular, the function is not smooth at t = 1 − 𝛼(2). The above heuristic is indeed correct and we have: 107 [PITH_FULL_IMAGE:figures/full_…
Figure 7.3
Figure 7.3. Figure 7.3: Plot of c ↦→ c 𝛼(c) displaying the criticality in the remaining graph when the giant has been removed. We can thus prove point (ii) in Theorem 6.1: Fix c > 1 and 𝛼(c)/2 > 𝜀 > 0. By Theorem 6.2, the event {|C max 1 − (1 − 𝛼(c))n| ⩽ 𝜀n} ∩ {C max 2 < 𝜀n} has a probabili…
Figure 8.1
Figure 8.1. Figure 8.1: Ordralfab´etix (© Goscinny et Uderzo). We introduce a variant of the Erdos–Rényi random graph where in ˝ finitely “stack” ver￾tices are added on the side. A very simple Markov property of the model entails that the Łukasiewicz exploration is made of simple increments…
Figure 8.2
Figure 8.2. Figure 8.2: A stacked Erd˝os–R´enyi random graph and one step of exploration. The stack is made of the white vertices on the left part while the core is represented by the gray part. After one step of exploration, the explored vertex (in red) is deleted as well as the edges link…
Figure 8.3
Figure 8.3. Figure 8.3: Lukasiewicz exploration of the graph G stack (n, p): the numbering reflects the order in which the vertices have been explored. The thick edges are kept whereas the thin red edges are discarded in the exploration. The thick (and very thick) edges form F stack (n, p) …
Figure 8.4
Figure 8.4. Figure 8.4: Graphs of the functions (1 − e −c t − t)t⩾0 for different of values of c: in blue c = 1/2, in orange c = 1, in green c = 2 and in red c = 3. Notice the root 1 − 𝛼(c) and compare with [PITH_FULL_IMAGE:figures/full_fig_p122_8_4.png]
Figure 8.5
Figure 8.5. Figure 8.5: A random recursive tree at stages 10,100 and 10000. 126 [PITH_FULL_IMAGE:figures/full_fig_p127_8_5.png]
Figure 9.1
Figure 9.1. Figure 9.1: Foata correspondence: on the left a description of a permutation via its images, on the right the description of a permutation by exploration of its cycles ranked in increasing order of their minimal element. This bijection transforms the number of cycles into the nu…
Figure 9.2
Figure 9.2. Figure 9.2: Constructing the law of the length of the cycles (in orange above) in a random permutation via the spacings in Bernoulli trials with parameters 1/(n −i) for i ∈ {0,1,2,. . . ,n − 1}. The red dots correspond to successes. Notice that we start with a space of length 1 …
Figure 9.3
Figure 9.3. Figure 9.3: Five simulations of the Poisson–Dirichlet (unranked) partition. A corollary of Theorem 9.1 is the following: Theorem 9.3 (Poisson–Dirichlet as limit of cycle length) For n ⩾ 0 we denote by K1(𝝈n),K2(𝝈n),. . . the cycle lengths appearing in the Foata encoding of a uni…
Figure 9.4
Figure 9.4. Figure 9.4: Dickman’s function Proof. We use the notation P(X ↓ 1 ⩽ x) = 𝜌(1/x) extended to 𝜌(u) = 1 for u ∈ [0,1]. In the unranked version (Xi : i ⩾ 1) of the Poisson–Dirichlet partition we can write after conditioning on the first uniform variable U1 P(X ↓ 1 ⩽ x) = P({X1 ⩽ x} …
Figure 10.1
Figure 10.1. Figure 10.1: A simulation of T10000 where the root vertex ⃝0 is placed at the top. Clearly, the random recursive tree seems “short and fat”. Obviously there are n! possible values for Tn: these are all increasing labeled trees with n + 1 vertices i.e. unoriented trees labeled fr…
Figure 10.2
Figure 10.2. Figure 10.2: Illustration of the coupling between growing permutations (𝝈 cr n : n ⩾ 1) on the left, the Chinese restaurant process in the middle and the random recursive tree (Tn : n ⩾ 1) starting with initial state 0 on the right. Proposition 10.2 (Convergence of proportions).…
Figure 10.3
Figure 10.3. Figure 10.3: Mecanism of the standard Polya urn: a ball is drawn uniformly at random and is replaced together with a ball of the same color (reinforcement). On the right, the transitions for the number of balls of each color over the first steps of the process. [0,1]. An easy in…
Figure 10.4
Figure 10.4. Figure 10.4: Simulation of T100 where the size and color of vertices illustrate their degrees. The first 20 vertices have their labels displayed. 10.2.1 Degree of fixed vertices By construction, for any i ⩾ 0 fixed, we have  deg+ Tn (⃝i ) : n ⩾ 0  = ∑︁n k=i+1 Bk : n ⩾ 0 ! , (1…
Figure 10.5
Figure 10.5. Figure 10.5: Plot of a simulation of the successive heights (Hi : 0 ⩽ i ⩽ 1000) against the log function (in red). 147 [PITH_FULL_IMAGE:figures/full_fig_p148_10_5.png]
Figure 11.1
Figure 11.1. Figure 11.1: Illustration of the construction of the random tree T starting from a single blue individual (the colors represent types of particles): each particle of type i lives for an exponential time of expectation 1/𝛼i , then dies and gives birth to new particles according t…
Figure 11.2
Figure 11.2. Figure 11.2: Illustration of the encoding of (a restriction of) the Yule tree as a (finite) plane k-ary tree whose vertices carry positive numbers (in pink on the right). We denote by #𝜕[T]t the number of leaves of [T]t and use Y (k) t ≡ #𝜕[T]t , as a short-hand notation. In thi…
Figure 11.3
Figure 11.3. Figure 11.3: Illustration of the proof: the two independent lineages of particles of types n → n − 1 → · · · → 2 → 1. The type of the particle still standing at the death of the other lineage (here 4) is studied through Rn. We therefore know that the remaining life time of the l…
Figure 11.4
Figure 11.4. Figure 11.4: Constructing the random recursive tree (Right) from a standard Yule process (Left): each particle gives rise to a particle of a new type at an exponential rate and this is interpreted as an attachment in the RRT. 11.4.2 Degree statistics Let us use Proposition 11.12…
Figure 12.1
Figure 12.1. Figure 12.1: The law of the pointed tree [T • ]t under Q is the same as that of the Yule tree started with a mutant particle. In particular, when k = 2 the ancestral line (Right on the figure) from the distinguished point to the root in [T • ]t under Q is obtained by superimposi…
Figure 13.1
Figure 13.1. Figure 13.1: A sampling of the process Tn for n = 1,2,3,4,8,16,32,. . . ,2 14. The colors and sizes of the vertices indicate their degrees. 179 [PITH_FULL_IMAGE:figures/full_fig_p180_13_1.png]
Figure 13.2
Figure 13.2. Figure 13.2: Illustration of the construction of (T plan n : n ⩾ 1). The corners are represented by dots and the one selected for the grafting at the next step is in red. 1 Albert-László Barabási (1967–), and Réka Albert (1972–), Romanian 180 [PITH_FULL_IMAGE:figures/full_fig_p…
Figure 13.3
Figure 13.3. Figure 13.3: Constructing the increasing labeled tree {{F}}t by contracting all “sub Yule trees of order 2” obtained by forgetting the right-most particle at each branch point. 13.2 Degrees We denote by deg{{F}}t (⃝i ) the degree of the ith vertex in the contraction of [F]t so t…
Figure 13.4
Figure 13.4. Figure 13.4: Degree’s race in the evolution of [PITH_FULL_IMAGE:figures/full_fig_p185_13_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Random punctured hyperbolic surfaces & the Brownian sphere

    math.PR 2025-08 conditional novelty 8.0 of 10

    Random Weil-Petersson punctured spheres converge, after fourth-root rescaling, to the Brownian sphere.

  2. Parking on the Random Recursive Tree

    math.PR 2025-01 conditional novelty 7.0 of 10

    On a random recursive tree with n vertices, parking is supercritical at every positive density, and the first outward flux for binary car arrivals appears when the mean number of cars per vertex is about (log n)^{-2+o(1)}.

Reference graph

Works this paper leans on

120 extracted references · 75 canonical work pages · cited by 2 Pith papers

  1. [2]

    An introduction to Galton-Watson trees and their local limits

    R. Abraham and J.-F. Delmas, An introduction to galton-watson trees and their local limits, arXiv preprint arXiv:1506.05571, (2015)

    work page Pith review arXiv 2015

  2. [3]

    Addario-Berry, N

    L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont, The scaling limit of the minimum spanning tree of the complete graph , The Annals of Probability, 45 (2017), pp. 3075–3144

    2017

  3. [4]

    Addario-Berry and L

    L. Addario-Berry and L. Eslava, High degrees in random recursive trees , Random Struc- tures & Algorithms, 52 (2018), pp. 560–575

    2018

  4. [5]

    Addario-Berry and K

    L. Addario-Berry and K. Ford, Poisson–dirichlet branching random walks, (2013)

    2013

  5. [6]

    Addario-Berry and B

    L. Addario-Berry and B. A. Reed, Ballot theorems, old and new, in Horizons of combi- natorics, vol. 17 of Bolyai Soc. Math. Stud., Springer, Berlin, 2008, pp. 9–35

    2008

  6. [7]

    Aldous, Asymptotic fringe distributions for general families of random trees, Ann

    D. Aldous, Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab., 1 (1991), pp. 228–266

    1991

  7. [8]

    , The continuum random tree. I, Ann. Probab., 19 (1991), pp. 1–28

    1991

  8. [9]

    , The continuum random tree. II. An overview, in Stochastic analysis (Durham, 1990), vol. 167 of London Math. Soc. Lecture Note Ser., Cambridge Univ. Press, Cambridge, 1991, pp. 23–70

    1990

Show all 120 references
  1. [10]

    Probab., (1997), pp

    , Brownian excursions, critical random graphs and the multiplicative coalescent , Ann. Probab., (1997), pp. 812–854

    1997

  2. [11]

    Aldous and R

    D. Aldous and R. Lyons, Processes on unimodular random networks, Electron. J. Probab., 12 (2007), pp. no. 54, 1454–1508 (electronic)

    2007

  3. [12]

    Alili, L

    L. Alili, L. Chaumont, and R. Doney, On a fluctuation identity for random walks and lévy processes, Bulletin of the London Mathematical Society, 37 (2005), pp. 141–148. 190

    2005

  4. [13]

    Alon and J

    N. Alon and J. H. Spencer, The probabilistic method, John Wiley & Sons, 2016

    2016

  5. [14]

    Arratia, A

    R. Arratia, A. D. Barbour, and S. Tavaré, Logarithmic combinatorial structures: a proba- bilistic approach, vol. 1, European Mathematical Society, 2003

    2003

  6. [15]

    K. B. Athreya and S. Karlin, Embedding of urn schemes into continuous time markov branching processes and related limit theorems, The Annals of Mathematical Statistics, 39 (1968), pp. 1801–1817

    1968

  7. [16]

    K. B. Athreya and P. E. Ney, Branching processes , vol. 196 of Die Grundlehren der mathematischen Wissenschaften, Springer-Verlag, 1972

    1972

  8. [17]

    Barabási and R

    A.-L. Barabási and R. Albert, Emergence of scaling in random networks , Science, 286 (1999), pp. 509–512

    1999

  9. [18]

    Baur and J

    E. Baur and J. Bertoin, Cutting edges at random in large recursive trees , in Stochastic Analysis and Applications 2014, Springer, 2014, pp. 51–76

    2014

  10. [19]

    Benjamini and N

    I. Benjamini and N. Curien, Ergodic theory on stationary random graphs , Electron. J. Probab., 17 (2012), pp. no. 93, 20

    2012

  11. [20]

    Benjamini and O

    I. Benjamini and O. Schramm, Percolation beyond Zs, many questions and a few answers, Electron. Commun. Probab., 1 (1996), pp. 71–82

    1996

  12. [21]

    , Recurrence of distributional limits of finite planar graphs , Electron. J. Probab., 6 (2001), pp. no. 23, 13 pp. (electronic)

    2001

  13. [22]

    Bertoin and C

    J. Bertoin and C. Goldschmidt, Dual random fragmentation and coagulation and an application to the genealogy of yule processes , in Mathematics and Computer Science III, Springer, 2004, pp. 295–308

    2004

  14. [23]

    Błaszczyszyn, Lecture notes on random geometric models—random graphs, point processes and stochastic geometry, (2017)

    B. Błaszczyszyn, Lecture notes on random geometric models—random graphs, point processes and stochastic geometry, (2017)

    2017

  15. [24]

    Bollobás and B

    B. Bollobás and B. Béla, Random graphs, no. 73, Cambridge university press, 2001

    2001

  16. [25]

    Bollobás and A

    B. Bollobás and A. G. Thomason, Threshold functions, Combinatorica, 7 (1987), pp. 35– 38

    1987

  17. [26]

    Bordenave, Notes on random graphs and combinatorial optimization , http://www.math.univ-toulouse.fr/ bordenave/coursRG.pdf

    C. Bordenave, Notes on random graphs and combinatorial optimization , http://www.math.univ-toulouse.fr/ bordenave/coursRG.pdf

  18. [27]

    Broutin and J.-F

    N. Broutin and J.-F. Marckert, A new encoding of coalescent processes: applications to the additive and multiplicative cases, Probab. Theory Related Fields, 166 (2016), pp. 515–552. 191

    2016

  19. [28]

    Burago, Y

    D. Burago, Y. Burago, and S. Ivanov, A course in metric geometry , vol. 33 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 2001

    2001

  20. [29]

    Bureaux, Méthodes probabilistes pour l’étude asymptotique des partitions entières et de la géométrie convexe discrète, PhD thesis, Paris 10, 2015

    J. Bureaux, Méthodes probabilistes pour l’étude asymptotique des partitions entières et de la géométrie convexe discrète, PhD thesis, Paris 10, 2015

    2015

  21. [30]

    Chamayou, A probabilistic approach to a differential-difference equation arising in analytic number theory, Mathematics of Computation, 27 (1973), pp

    J.-M.-F. Chamayou, A probabilistic approach to a differential-difference equation arising in analytic number theory, Mathematics of Computation, 27 (1973), pp. 197–203

    1973

  22. [31]

    Chauvin and A

    B. Chauvin and A. Rouault, Kpp equation and supercritical branching brownian motion in the subcritical speed area. application to spatial trees , Probability theory and related fields, 80 (1988), pp. 299–314

    1988

  23. [32]

    A. Chin, G. Gordon, K. MacPhee, and C. Vincent, Pick a tree–any tree, The American Mathematical Monthly, 122 (2015), pp. 424–432

    2015

  24. [33]

    C. W. Chin, Deriving the central limit theorem from the de moivre-laplace theorem , arXiv:2109.09258, (2021)

    2021 arXiv

  25. [34]

    K. L. Chung, A course in probability theory , Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, second ed., 1974. Probability and Mathematical Statistics, Vol. 21

    1974

  26. [35]

    Cooper, A

    C. Cooper, A. Frieze, and W. Pegden,On the rank of a random binary matrix, in Proceed- ings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2019, pp. 946–955

    2019

  27. [36]

    Curien, Peeling random planar maps, Saint-Flour course 2019 , https://www.imo.universite-paris-saclay.fr/∼curien/

    N. Curien, Peeling random planar maps, Saint-Flour course 2019 , https://www.imo.universite-paris-saclay.fr/∼curien/

    2019

  28. [37]

    , Y et another proof of the law of large numbers , arXiv preprint arXiv:2109.04315, (2021)

    2021 arXiv

  29. [38]

    , Erdös-Rényi Poissonized, C. R. Acad. Sci. Paris Sér. I Math. (to appear), (2023)

    2023

  30. [39]

    Darling, Fluid limits of pure jump markov processes: a practical guide , arXiv preprint math/0210109, (2002)

    R. Darling, Fluid limits of pure jump markov processes: a practical guide , arXiv preprint math/0210109, (2002)

    2002 arXiv

  31. [40]

    R. W. Darling and J. R. Norris, Differential equation approximations for markov chains , (2008)

    2008

  32. [41]

    Davis and D

    B. Davis and D. McDonald, An elementary proof of the local central limit theorem, Journal of Theoretical Probability, 8 (1995), pp. 693–702. 192

    1995

  33. [42]

    F. M. Dekking, Branching processes that grow faster than binary splitting , Amer. Math. Monthly, 98 (1991), pp. 728–731

    1991

  34. [43]

    Devroye and J

    L. Devroye and J. Lu, The strong convergence of maximal degrees in uniform random recursive trees and dags, Random Structures & Algorithms, 7 (1995), pp. 1–14

    1995

  35. [44]

    Diaconis and A

    P. Diaconis and A. Hicks, Probabilizing parking functions, Advances in Applied Mathe- matics, 89 (2017), pp. 125–155

    2017

  36. [45]

    Diaconis, E

    P. Diaconis, E. Mayer-Wolf, O. Zeitouni, and M. P. W. Zerner,The Poisson–Dirichlet law is the unique invariant distribution for uniform split-merge transformations, Ann. Probab., 32 (2004), pp. 915–938

    2004

  37. [46]

    Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Arkiv for matematik, astronomi och fysik, 22 (1930), pp

    K. Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Arkiv for matematik, astronomi och fysik, 22 (1930), pp. A–10

    1930

  38. [47]

    Drmota, Random trees: an interplay between combinatorics and probability , Springer Science & Business Media, 2009

    M. Drmota, Random trees: an interplay between combinatorics and probability , Springer Science & Business Media, 2009

    2009

  39. [48]

    Duminil-Copin, Sixty years of percolation, arXiv preprint arXiv:1712.04651, (2017)

    H. Duminil-Copin, Sixty years of percolation, arXiv preprint arXiv:1712.04651, (2017)

    2017 arXiv

  40. [49]

    Duquesne and J.-F

    T. Duquesne and J.-F. Le Gall, Probabilistic and fractal aspects of Lévy trees , Probab. Theory Related Fields, 131 (2005), pp. 553–603

    2005

  41. [50]

    Durrett, Random graph dynamics, vol

    R. Durrett, Random graph dynamics, vol. 20, Cambridge university press, 2010

    2010

  42. [51]

    D. A. Edwards, The structure of superspace, in Studies in topology, Elsevier, 1975, pp. 121– 133

    1975

  43. [52]

    Erd˝os and A

    P. Erd˝os and A. Rényi, On random graphs i, Publ. math. debrecen, 6 (1959), p. 18

    1959

  44. [53]

    Erd˝os and A

    P. Erd˝os and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci, 5 (1960), pp. 17–60

    1960

  45. [54]

    Erdos and A

    P. Erdos and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar, 14 (1963), p. 3

    1963

  46. [55]

    S. N. Evans, Probability and real trees , vol. 1920 of Lecture Notes in Mathematics, Springer, Berlin, 2008. Lectures from the 35th Summer School on Probability The- ory held in Saint-Flour, July 6–23, 2005

    1920

  47. [56]

    Feller, The fundamental limit theorems in probability, Bulletin of the American Math- ematical Society, 51 (1945), pp

    W. Feller, The fundamental limit theorems in probability, Bulletin of the American Math- ematical Society, 51 (1945), pp. 800–832. 193

    1945

  48. [57]

    , An introduction to probability theory and its applications. Vol. II. , Second edition, John Wiley & Sons, Inc., New York-London-Sydney, 1971

    1971

  49. [58]

    Féray, Random combinatorial structures, (2019)

    V. Féray, Random combinatorial structures, (2019)

    2019

  50. [59]

    Flajolet and R

    P. Flajolet and R. Sedgewick, Analytic combinatorics, Cambridge University Press, 2009

    2009

  51. [60]

    Gerin, Mini-course: Random uniform permutations

    L. Gerin, Mini-course: Random uniform permutations

  52. [61]

    Goldschmidt and J

    C. Goldschmidt and J. Martin, Random recursive trees and the bolthausen-sznitman coale- sent, Electron. J. Probab., 10 (2005), pp. 718–745

    2005

  53. [62]

    Grimmett, Percolation and disordered systems, in Lectures on probability theory and statistics, Springer, 1997, pp

    G. Grimmett, Percolation and disordered systems, in Lectures on probability theory and statistics, Springer, 1997, pp. 153–300

    1997

  54. [63]

    Gromov, Metric structures for Riemannian and non-Riemannian spaces , Modern Birkhäuser Classics, Birkhäuser Boston Inc., Boston, MA, english ed., 2007

    M. Gromov, Metric structures for Riemannian and non-Riemannian spaces , Modern Birkhäuser Classics, Birkhäuser Boston Inc., Boston, MA, english ed., 2007. Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean ...

    2007

  55. [64]

    Harary, G

    F. Harary, G. Prins, and W. Tutte, The number of plane trees , Indag. Math, 26 (1964), pp. 319–329

    1964

  56. [65]

    Holmgren and S

    C. Holmgren and S. Janson, Limit laws for functions of fringe trees for binary search trees and random recursive trees, Electronic Journal of Probability, 20 (2015)

    2015

  57. [66]

    I. A. Ibragimov and Y. V. Linnik, Independent and stationary sequences of random vari- ables, Wolters-Noordhoff Publishing, Groningen, 1971. With a supplementary chapter by I. A. Ibragimov and V. V. Petrov, Translation from the Russian edited by J. F. C. Kingman

    1971

  58. [67]

    Janson, As convergence for infinite colour pólya urns associated with random walks, Arkiv för Matematik, 59 (2021), pp

    S. Janson, As convergence for infinite colour pólya urns associated with random walks, Arkiv för Matematik, 59 (2021), pp. 87–123

    2021

  59. [68]

    Janson, D

    S. Janson, D. E. Knuth, T. Łuczak, and B. Pittel, The birth of the giant component , Random Structures & Algorithms, 4 (1993), pp. 233–358

    1993

  60. [69]

    Janson, T

    S. Janson, T. Luczak, and A. Rucinski, Random graphs, vol. 45, John Wiley & Sons, 2011

    2011

  61. [70]

    Kahn and G

    J. Kahn and G. Kalai, Thresholds and expectation thresholds, Combinatorics, Probability and Computing, 16 (2007), pp. 495–502

    2007

  62. [71]

    Kallenberg, Random measures, Akademie-Verlag, Berlin, fourth ed., 1986

    O. Kallenberg, Random measures, Akademie-Verlag, Berlin, fourth ed., 1986. 194

    1986

  63. [72]

    , Foundations of Modern Probability, Springer, New York, second ed., 2002

    2002

  64. [73]

    Khorunzhy, M

    O. Khorunzhy, M. Shcherbina, and V. Vengerovsky, Eigenvalue distribution of large weighted random graphs, Journal of Mathematical Physics, 45 (2004), pp. 1648–1672

    2004

  65. [74]

    J. H. Kim, Poisson cloning model for random graphs, Expositions of current mathematics, 2007 (2007), pp. 104–120

    2007

  66. [75]

    A. G. Konheim and B. Weiss, An occupancy discipline and applications, SIAM Journal on Applied Mathematics, 14 (1966), pp. 1266–1274

    1966

  67. [76]

    Kortchemski, Arbres et marches aléatoires, Journées X-UPS, (2016)

    I. Kortchemski, Arbres et marches aléatoires, Journées X-UPS, (2016)

    2016

  68. [77]

    Krivelevich and B

    M. Krivelevich and B. Sudakov, The phase transition in random graphs: A simple proof , Random Structures & Algorithms, 43 (2013), pp. 131–138

    2013

  69. [78]

    Kuba and A

    M. Kuba and A. Panholzer, Limiting distributions for a class of diminishing urn models , Advances in Applied Probability, 44 (2012), pp. 87–116

    2012

  70. [79]

    Kwa ´snicki, Random walks are determined by their trace on the positive half-line , An- nales Henri Lebesgue, 3 (2020), pp

    M. Kwa ´snicki, Random walks are determined by their trace on the positive half-line , An- nales Henri Lebesgue, 3 (2020), pp. 1389–1397

    2020

  71. [80]

    A. E. Kyprianou, Wiener–hopf decomposition, Encyclopedia of Quantitative Finance, (2010)

    2010

  72. [81]

    Lalley, One-dimensional random walks (lecture notes) , http://galton.uchicago.edu/ lal- ley/Courses/312/RW.pdf

    S. Lalley, One-dimensional random walks (lecture notes) , http://galton.uchicago.edu/ lal- ley/Courses/312/RW.pdf

  73. [82]

    G. F. Lawler and V. Limic, Random walk: a modern introduction, vol. 123 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2010

    2010

  74. [83]

    Le Gall, Random trees and applications, Probability Surveys, (2005)

    J.-F. Le Gall, Random trees and applications, Probability Surveys, (2005)

    2005

  75. [84]

    , Random real trees, Ann. Fac. Sci. T oulouse Math. (6), 15 (2006), pp. 35–62

    2006

  76. [85]

    Le Gall and G

    J.-F. Le Gall and G. Miermont, Scaling limits of random trees and planar maps , Lecture notes for the Clay Mathematical Institute Summer School in Buzios, ( July 11 - August 7, 2010)

    2010

  77. [86]

    Levine and Y

    L. Levine and Y. Peres, Internal erosion and the exponent 3/4 , Unpublished manuscript, (2007)

    2007

  78. [87]

    M. J. Luczak and C. McDiarmid, Bisecting sparse random graphs, Random Structures & Algorithms, 18 (2001), pp. 31–38. 195

    2001

  79. [88]

    Lyons, R

    R. Lyons, R. Pemantle, and Y. Peres,Conceptual proofs of l log l criteria for mean behavior of branching processes, Ann. Probab., 23 (1995), pp. 1125–1138

    1995

  80. [89]

    H. M. Mahmoud, Distances in random plane-oriented recursive trees , Journal of Compu- tational and Applied Mathematics, 41 (1992), pp. 237–245

    1992

  81. [90]

    Marchal, Two consequences of a path transform, Bulletin of the London Mathematical Society, 33 (2001), pp

    P. Marchal, Two consequences of a path transform, Bulletin of the London Mathematical Society, 33 (2001), pp. 213–220

    2001

  82. [91]

    T. F. Móri, The maximum degree of the Barabási–Albert random tree , Combinatorics, Probability and Computing, 14 (2005), pp. 339–348

    2005

  83. [92]

    Nachmias and Y

    A. Nachmias and Y. Peres, The critical random graph, with martingales, Israel Journal of Mathematics, 176 (2010), pp. 29–41

    2010

  84. [93]

    Najnudel and J

    J. Najnudel and J. Pitman, Feller coupling of cycles of permutations and poisson spacings in inhomogeneous bernoulli trials, (2020)

    2020

  85. [94]

    Neveu, Arbres et processus de Galton-Watson , Ann

    J. Neveu, Arbres et processus de Galton-Watson , Ann. Inst. H. Poincaré Probab. Statist., 22 (1986), pp. 199–207

    1986

  86. [95]

    Oulamara, Géométrie aléatoire et énergie libre de modèles critiques sur réseau planaire , PhD thesis, IHES

    M. Oulamara, Géométrie aléatoire et énergie libre de modèles critiques sur réseau planaire , PhD thesis, IHES

  87. [96]

    Park and H

    J. Park and H. T. Pham, A proof of the kahn-kalai conjecture , arXiv preprint arXiv:2203.17207, (2022)

    2022 arXiv

  88. [97]

    Pitman, Combinatorial stochastic processes, vol

    J. Pitman, Combinatorial stochastic processes, vol. 1875 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, 2006. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002, With a foreword by Jean Picard

    2006

  89. [98]

    Pittel, On the probable behaviour of some algorithms for finding the stability number of a graph, in Mathematical Proceedings of the Cambridge Philosophical Society, vol

    B. Pittel, On the probable behaviour of some algorithms for finding the stability number of a graph, in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 92, Cambridge University Press, 1982, pp. 511–526

    1982

  90. [99]

    Pittel, Note on the heights of random recursive trees and random m-ary search trees , Random Structures & Algorithms, 5 (1994), pp

    B. Pittel, Note on the heights of random recursive trees and random m-ary search trees , Random Structures & Algorithms, 5 (1994), pp. 337–347

    1994

  91. [100]

    S. I. Resnick, Extreme values, regular variation, and point processes , vol. 4, Springer Science & Business Media, 2008

    2008

  92. [101]

    Schramm, Compositions of random transpositions, Israel Journal of Mathematics, 147 (2005), pp

    O. Schramm, Compositions of random transpositions, Israel Journal of Mathematics, 147 (2005), pp. 221–243. 196

    2005

  93. [102]

    Shepp, Recurrent random walks with arbitrarily large steps , Bulletin of the American Mathematical Society, 70 (1964), pp

    L. Shepp, Recurrent random walks with arbitrarily large steps , Bulletin of the American Mathematical Society, 70 (1964), pp. 540–542

    1964

  94. [103]

    L. A. Shepp, Symmetric random walk, Transactions of the American Mathematical So- ciety, 104 (1962), pp. 144–153

    1962

  95. [104]

    L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Transactions of the American Mathematical Society, 121 (1966), pp. 340–357

    1966

  96. [105]

    Shi, Branching random walks, Springer, 2015

    Z. Shi, Branching random walks, Springer, 2015

    2015

  97. [106]

    R. T. Smythe and H. M. Mahmoud, A survey of recursive trees, Theory of Probability and Mathematical Statistics, (1995), pp. 1–28

    1995

  98. [107]

    Spencer, Ten lectures on the probabilistic method, SIAM, 1994

    J. Spencer, Ten lectures on the probabilistic method, SIAM, 1994

    1994

  99. [108]

    Spitzer, Principles of random walk, Springer-Verlag, New York-Heidelberg, second ed.,

    F. Spitzer, Principles of random walk, Springer-Verlag, New York-Heidelberg, second ed.,

  100. [109]

    Szyma ´nski, On a nonuniform random recursive tree , in North-Holland mathematics studies, vol

    J. Szyma ´nski, On a nonuniform random recursive tree , in North-Holland mathematics studies, vol. 144, Elsevier, 1987, pp. 297–306

    1987

  101. [110]

    T enenbaum,Introduction to analytic and probabilistic number theory, vol

    G. T enenbaum,Introduction to analytic and probabilistic number theory, vol. 163, Ameri- can Mathematical Soc., 2015

    2015

  102. [111]

    Tóth, Improved lower bound on the thermodynamic pressure of the spin 1/2 heisenberg ferromagnet, letters in mathematical physics, 28 (1993), pp

    B. Tóth, Improved lower bound on the thermodynamic pressure of the spin 1/2 heisenberg ferromagnet, letters in mathematical physics, 28 (1993), pp. 75–84

    1993

  103. [112]

    van der Hofstad, Random graphs and complex networks

    R. van der Hofstad, Random graphs and complex networks. vol. i , available at http://www.win.tue.nl/ rhofstad/

  104. [113]

    Van Der Hofstad, Random graphs and complex networks , Available on http://www

    R. Van Der Hofstad, Random graphs and complex networks , Available on http://www. win. tue. nl/rhofstad/NotesRGCN. pdf, 11 (2009)

    2009

  105. [114]

    van der Hofstad, Random graphs and complex networks

    R. van der Hofstad, Random graphs and complex networks. vol. ii , available at http://www.win.tue.nl/ rhofstad/, (preliminary version)

  106. [115]

    A. M. Vershik, The universal Urysohn space, Gromov metric triples and random metrics on the natural numbers, Russian Mathematical Surveys, 53 (1998), p. 921

    1998

  107. [116]

    Warnke, On wormald’s differential equation method, arXiv preprint arXiv:1905.08928, (2019)

    L. Warnke, On wormald’s differential equation method, arXiv preprint arXiv:1905.08928, (2019). 197

    2019 arXiv

  108. [117]

    Werner, Lectures on two-dimensional critical percolation , arXiv preprint arXiv:0710.0856, (2007)

    W. Werner, Lectures on two-dimensional critical percolation , arXiv preprint arXiv:0710.0856, (2007)

    2007 arXiv

  109. [118]

    N. C. Wormald, Differential equations for random processes and random graphs, The annals of applied probability, (1995), pp. 1217–1235

    1995

  110. [119]

    Wu and J

    Y. Wu and J. Xu, Statistical inference on graphs: Selected topics

  111. [120]

    Zakharevich, A generalization of wigner’s law , Comm

    I. Zakharevich, A generalization of wigner’s law , Comm. Math. Phys., 268 (2006), pp. 403–414. 198

    2006

  112. [1976]

    Graduate T exts in Mathematics, Vol. 34

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.