Research

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 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 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.

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 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.

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).