Papers

We study the connected components in critical percolation on the Hamming hypercube. We show that their sizes properly rescaled converge in distribution, and that, considered as metric measure spaces with the graph distance properly rescaled and the uniform measure, they converge in distribution with respect to the Gromov-Hausdorff-Prokhorov topology. The two corresponding limits are as in critical Erdős-Rényi graphs.

We consider large uniform random trees where we fix for each vertex its degree and height. We prove, under natural conditions of convergence for the profile, that those trees properly renormalized converge. To this end, we study the paths from random vertices to the root using coalescent processes. As an application, we obtain scaling limits of Bienaymé-Galton-Watson trees in varying environment.

We introduce a new theory of plane R-tree, to define plane ICRT (inhomogeneous continuum random tree), and its looptree, fennec (a Gaussian free field on the looptree), and snake. We prove that a.s. the looptree is compact, and that a.s. the fennec and snake are continuous. We compute the looptree's fractal dimensions, and the fennec and snake's Hölder exponent. Alongside, we define a Gaussian free field on the ICRT, and prove a condition for its continuity. In a companion paper , we prove that the looptrees, fennecs, and snakes of trees with fixed degree sequence converge toward the looptrees, fennecs and snakes of ICRT.

We use a new stick-breaking construction, also introduced independently by Addario-Berry, Donderwinkel, Maazoun, and Martin in arXiv:2107.09726, to study uniform rooted trees with fixed degree sequence D (D-trees). This construction allows us to prove, under natural conditions of convergence of the degree sequence, that D-trees converge toward either P-trees or ICRT. Alongside we provide an upper-bound for the height of D-trees. We deduce similar results concerning P-trees and ICRT. In passing we confirm a conjecture of Aldous, Miermont, and Pitman arXiv:math/0401115 stating that Lévy trees are ICRT with random parameters.

Motivated by the scaling limits of the connected components of the configuration model, we study uniform connected multigraphs with fixed degree sequence D and with surplus k. We call those random graphs (D, k)-graphs. We prove that, for every k ∈ N, under natural conditions of convergence of the degree sequence, (D, k)-graphs converge toward either (P, k)-graphs or (Θ, k)-ICRG (inhomogeneous continuum random graphs). We prove similar results for (P, k)-graphs and (Θ, k)-ICRG, which have applications to multiplicative graphs. Our approach relies on two algorithms, the cycle-breaking algorithm, and the stick-breaking construction of D-tree that we introduced in a recent paper. From those algorithms we deduce a biased construction of (D, k)-graph, and we prove our results by studying this bias.

We present a very simple bijective proof of Cayley’s formula due to Foata and Fuchs (1970). This bijection turns out to be very useful when seen through a probabilistic lens; we explain some of the ways in which it can be used to derive probabilistic identities, bounds, and growth procedures for random trees with given degrees, including random d-ary trees. We also introduce a partial order on the degree sequences of rooted trees, and conjecture that it induces a stochastic partial order on heights of random rooted trees with given degrees.

We introduce a new stick-breaking construction for inhomogeneous continuum random trees (ICRT). This new construction allows us to prove the necessary and sufficient condition for compactness conjectured by Aldous, Miermont and Pitman arXiv:math/0401115 by comparison with Lévy trees. We also compute the fractal dimensions (Minkowski, Packing, Hausdorff).

We investigate scaling limits of trees built by uniform attachment with freezing, which is a variant of the classical model of random recursive trees introduced in a companion paper. Here vertices are allowed to freeze, and arriving vertices cannot be attached to already frozen ones. We identify a phase transition when the number of non-frozen vertices roughly evolves as the total number of vertices to a given power. In particular, we observe a critical regime where the scaling limit is a random compact real tree, closely related to a time non-homogenous Kingman coalescent process identified by Aldous. Interestingly, in this critical regime, a condensation phenomenon can occur.

In the classical model of random recursive trees, trees are recursively built by attaching new vertices to old ones. What happens if vertices are allowed to freeze, in the sense that new vertices cannot be attached to already frozen ones? We are interested in the impact of freezing on the height of such trees.

We consider a recent model of random walk that recursively grows the network on which it evolves, namely the Tree Builder Random Walk. We introduce a bias ρ∈(0,∞) towards the root, and exhibit a phase transition for transience/recurrence at a critical threshold ρ_c=1+2ν, where ν is the (possibly infinite) expected number of new leaves attached to the walker's position at each step. This generalizes previously known results, which focused on the unbiased case ρ=1. The proofs rely on a recursive analysis of the local times of the walk at each vertex of the tree, after a given number of returns to the root. We moreover characterize the strength of the transience (law of large numbers and central limit theorem with positive speed) via standard arguments, establish recurrence at ρ_c, and show a condensation phenomenon in the non-critical recurrent case.

We study the random digraph in which each of the n(n-1) possible directed edges are present with probability p. We show that in the critical window the length of the longest self avoiding oriented path and so the diameter has order n^{1/3}.

We answer Problem 11.1 of Janson arXiv:1803.04207 on Pólya urns associated with stable random walk. Our proof use neither martingales nor trees, but an approximation with a differential equation.