Benedikt Stufler

Decorated stable trees

We define decorated $α$ -stable trees which are informally obtained from an $α$ -stable tree by blowing up its branchpoints into random metric spaces. This generalizes the $α$ -stable looptrees of Curien and Kortchemski, where those metric spaces are just deterministic circles. We provide different constructions for these objects, which allows us to understand some of their geometric properties, including compactness, Hausdorff dimension and self-similarity in distribution. We prove an invariance principle which states that under some conditions, analogous discrete objects, random decorated discrete trees, converge in the scaling limit to decorated $α$ -stable trees. We mention a few examples where those objects appear in the context of random trees and planar maps, and we expect them to naturally arise in many more cases.

First-passage percolation on random simple triangulations

We study first-passage percolation on random simple triangulations and their dual maps with independent identically distributed link weights. Our main result shows that the first-passage percolation distance concentrates in an $o_p(n^{1/4})$ window around a constant multiple of the graph distance.

Mass and radius of balls in Gromov-Hausdorff-Prokhorov convergent sequences

We survey some properties of Gromov--Hausdorff--Prokhorov convergent sequences $(\mathsf{X}_n, d_{\mathsf{X}_n}, ν_{\mathsf{X}_n})_{n \ge 1}$ of random compact metric spaces equipped with Borel probability measures. We formalize that if the limit is almost surely non-atomic, then for large $n$ each open ball in $\mathsf{X}_n$ with small radius must have small mass. Conversely, if the limit is almost surely fully supported, then each closed ball in $\mathsf{X}_n$ with small mass must have small radius. We do not claim any new results, but justifications are provided for properties for which we could not find explicit references.

The scaling limit of random cubic planar graphs

We study the random simple connected cubic planar graph $\mathsf{C}_n$ with an even number $n$ of vertices. We show that the Brownian map arises as Gromov--Hausdorff--Prokhorov scaling limit of $\mathsf{C}_n$ as $n \in 2 \ndN$ tends to infinity, after rescaling distances by $γn^{-1/4}$ for a specific constant $γ>0$ .

The Uniform Infinite Cubic Planar Graph

We prove that the random simple cubic planar graph $\mathsf{C}_n$ with an even number $n$ of vertices admits a novel uniform infinite cubic planar graph (UICPG) as quenched local limit. We describe how the limit may be constructed by a series of random blow-up operations applied to the dual map of the type~III Uniform Infinite Planar Triangulation established by Angel and Schramm (Comm. Math. Phys., 2003). Our main technical lemma is a contiguity relation between $\mathsf{C}_n$ and a model where the networks inserted at the links of the largest $3$ -connected component of $\mathsf{C}_n$ are replaced by independent copies of a specific Boltzmann network. We prove that the number of vertices of the largest $3$ -connected component concentrates at $κn$ for $κ\approx 0.85085$ , with Airy-type fluctuations of order $n^{2/3}$ . The second-largest component is shown to have significantly smaller size $O_p(n^{2/3})$ .

A branching process approach to level- $k$ phylogenetic networks

The mathematical analysis of random phylogenetic networks via analytic and algorithmic methods has received increasing attention in the past years. In the present work we introduce branching process methods to their study. This approach appears to be new in this context. Our main results focus on random level- $k$ networks with $n$ labelled leaves. Although the number of reticulation vertices in such networks is typically linear in $n$ , we prove that their asymptotic global and local shape is tree-like in a well-defined sense. We show that the depth process of vertices in a large network converges towards a Brownian excursion after rescaling by $n^{-1/2}$ . We also establish Benjamini--Schramm convergence of large random level- $k$ networks towards a novel random infinite network.

On the maximal offspring in a subcritical branching process

We consider a subcritical Galton--Watson tree conditioned on having $n$ vertices with outdegree in a fixed set $Ω$ . Under mild regularity assumptions we prove various limits related to the maximal offspring of a vertex as $n$ tends to infinity.

Quenched local convergence of Boltzmann planar maps

Stephenson~(2018) established annealed local convergence of Boltzmann planar maps conditioned to be large. The present work uses results on rerooted multi-type branching trees to prove a quenched version of this limit.

Rerooting multi-type branching trees: the infinite spine case

We prove local convergence results of rerooted conditioned multi-type Galton--Watson trees. The limit objects are multitype variants of the random sin-tree constructed by Aldous (1991), and differ according to which types recur infinitely often along the backwards growing spine.

preprint2020arXiv

A decorated tree approach to random permutations in substitution-closed classes

We establish a novel bijective encoding that represents permutations as forests of decorated (or enriched) trees. This allows us to prove local convergence of uniform random permutations from substitution-closed classes satisfying a criticality constraint. It also enables us to reprove and strengthen permuton limits for these classes in a new way, that uses a semi-local version of Aldous' skeleton decomposition for size-constrained Galton--Watson trees.

Gibbs partitions: the convergent case

We study Gibbs partitions that typically form a unique giant component. The remainder is shown to converge in total variation toward a Boltzmann-distributed limit structure. We demon- strate how this setting encompasses arbitrary weighted assemblies of tree-like combinatorial structures. As an application, we establish smooth growth along lattices for small block-stable classes of graphs. Random graphs with n vertices from such classes are shown to form a giant connected component. The small fragments may converge toward different Poisson Boltzmann limit graphs, depending along which lattice we let n tend to infinity. Since proper addable minor-closed classes of graphs belong to the more general family of small block-stable classes, this recovers and generalizes results by McDiarmid (2009).

Graph limits of random graphs from a subset of connected $k$ -trees

For any set $Ω$ of non-negative integers such that $\{0,1\}\subseteq Ω$ and $\{0,1\}\ne Ω$ , we consider a random $Ω$ - $k$ -tree ${\sf G}_{n,k}$ that is uniformly selected from all connected $k$ -trees of $(n+k)$ vertices where the number of $(k+1)$ -cliques that contain any fixed $k$ -clique belongs to $Ω$ . We prove that ${\sf G}_{n,k}$ , scaled by $(kH_{k}σ_Ω)/(2\sqrt{n})$ where $H_{k}$ is the $k$ -th Harmonic number and $σ_Ω>0$ , converges to the Continuum Random Tree $\mathcal{T}_{\sf e}$ . Furthermore, we prove the local convergence of the rooted random $Ω$ - $k$ -tree ${\sf G}_{n,k}^{\circ}$ to an infinite but locally finite random $Ω$ - $k$ -tree ${\sf G}_{\infty,k}$ .

Random enriched trees with applications to random graphs

We establish limit theorems that describe the asymptotic local and global geometric behaviour of random enriched trees considered up to symmetry. We apply these general results to random unlabelled weighted rooted graphs and uniform random unlabelled $k$ -trees that are rooted at a $k$ -clique of distinguishable vertices. For both models we establish a Gromov--Hausdorff scaling limit, a Benjamini--Schramm limit, and a local weak limit that describes the asymptotic shape near the fixed root.

The continuum random tree is the scaling limit of unlabelled unrooted trees

We prove that the uniform unlabelled unrooted tree with n vertices and vertex degrees in a fixed set converges in the Gromov-Hausdorff sense after a suitable rescaling to the Brownian continuum random tree. This proves a conjecture by Aldous. Moreover, we establish Benjamini-Schramm convergence of this model of random trees.