Search

We study random $k$-connected chordal graphs with bounded tree-width. Our main results are scaling limits and quenched local limits.

We determine the Gromov--Hausdorff--Prokhorov scaling limits and local limits of Kemp's $d$-dimensional binary trees and other models of supertrees. The limits exhibit a root vertex with infinite degree and are constructed by rescaling infinitely many independent stable trees or other spaces according to a function of a two-parameter Poisson--Dirichlet process and gluing them together at their roots. We discuss universality aspects of random spaces constructed in this fashion and sketch a phase diagram.

We present a new probabilistic proof of Otter's asymptotic formula for the number of unlabelled trees with a given number of vertices. We additionally prove a new approximation result, showing that the total variation distance between random P\'olya trees and random unlabelled trees tends to zero when the number of vertices tends to infinity. In order to demonstrate that our approach is not restricted to trees we extend our results to tree-like classes of graphs.

We define decorated $\alpha$-stable trees which are informally obtained from an $\alpha$-stable tree by blowing up its branchpoints into random metric spaces. This generalizes the $\alpha$-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 $\alpha$-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., Comment: 52 pages, 6 figures. Comments are welcome

We study Gibbs partition models, also known as composition schemes. Our main results comprehensively describe their phase diagram, including a phase transition from the convergent case described in Stufler (2018, Random Structures \& Algorithms) to a new dense regime characterized by a linear number of components with fluctuations of smaller order quantified by an $\alpha$-stable law for $1< \alpha \le 2$. We prove a functional scaling limit for a process whose jumps correspond to the component sizes and discuss applications to extremal component sizes. At the transition we observe a mixture of the two asymptotic shapes. We also treat extended composition schemes and prove a local limit theorem in a dilute regime with the limiting law being related to an $\alpha$-stable law for $0< \alpha < 1$. We describe the asymptotic size of the largest components via a point process limit.

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 $\gamma n^{-1/4} $ for a specific constant $\gamma>0$.

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.

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 $\kappa n$ for $\kappa \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})$.

We survey some properties of Gromov--Hausdorff--Prokhorov convergent sequences $(\mathsf{X}_n, d_{\mathsf{X}_n}, \nu_{\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.

Various combinatorial classes such as outerplanar graphs and maps, series-parallel graphs, substitution-closed classes of permutations and many more allow bijective encodings by so-called enriched trees, which are rooted trees with additional structure on the offspring of each node. Using this universal description we develop sampling procedures that uniformly generate objects from this classes with a given size $n$ in expected time $O(n)$.The key ingredient is a representation of enriched trees in terms of decorated Bienaym\'e--Galton--Watson trees, which allows us to develop a novel combination of Devroye's efficient sampler for trees (Devroye, 2012) with Boltzmann sampling techniques. Additionally, we construct expected linear time samplers for critical Bienaym\'e--Galton--Watson trees having exactly $n$ (out of $\ge n$ total) nodes with outdegree in some fixed set, enabling uniform generation for many combinatorial classes such as dissections of polygons.

The main goal of this paper is to determine the asymptotic behavior of the number $X_n$ of cut-vertices in random planar maps with $n$ edges. It is shown that $X_n/n \to c$ in probability (for some explicit $c>0$). For so-called subcritical classes of planar maps (like outerplanar maps) we obtain a central limit theorem, too. Interestingly the combinatorics behind this seemingly simple problem is quite involved.

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., Comment: The results of this work were initially part of [21]. The paper got split during the refereeing process following a referee's recommendation. arXiv admin note: substantial text overlap with arXiv:1908.04843

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.

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., Comment: The paper was split during the review process following a referee's recommendation. The results on Boltzmann planar maps are now a separate paper: [22]

The present work describes the asymptotic local shape of a graph drawn uniformly at random from all connected simple planar graphs with n labelled vertices. We establish a novel uniform infinite planar graph (UIPG) as quenched limit in the local topology as n tends to infinity. We also establish such limits for random 2-connected planar graphs and maps as their number of edges tends to infinity. Our approach encompasses a new probabilistic view on the Tutte decomposition. This allows us to follow the path along the decomposition of connectivity from planar maps to planar graphs in a uniformed way, basing each step on condensation phenomena for random walks under subexponentiality and Gibbs partitions. Using large deviation results, we recover the asymptotic formula by Gim\'enez and Noy (2009) for the number of planar graphs.

We study the behaviour of random labelled and unlabelled cographs with n vertices as n tends to infinity. Our main result is a novel probabilistic limit in the space of graphons.

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., Comment: New version including referee's corrections, accepted for publication in Electronic Journal of Probability

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

We study random unrooted plane trees with $n$ vertices sampled according to the weights corresponding to the vertex-degrees. Our main result shows that if the generating series of the weights has positive radius of convergence, then this model of random trees may be approximated geometrically by a Galton--Watson tree conditioned on having a large random size. This implies that a variety of results for the well-studied planted case also hold for unrooted trees, including Gromov--Hausdorff--Prokhorov scaling limits, tail-bounds for the diameter, distributional graph limits, and limits for the maximum degree. Our work complements results by Wang~(2016), who studied random unrooted plane trees whose diameter tends to infinity.

We study random unlabelled $k$-dimensional trees by combining the colouring approach by Gainer-Dewar and Gessel (2014) with the cycle pointing method by Bodirsky, Fusy, Kang and Vigerske (2011). Our main applications are Gromov-Hausdorff-Prokhorov and Benjamini-Schramm limits, that describe their asymptotic geometric shape on a global and local scale as the number of hedra tends to infinity.

We consider planar maps adjusted with a (regular critical) Boltzmann distribution and show that the expected number of pattern occurrences of a given map is asymptotically linear when the number n of edges goes to infinity. The main ingredient for the proof is an extension of a formula by Liskovets (1999).

We study the asymptotic shape of random unlabelled graphs subject to certain subcriticality conditions. The graphs are sampled with probability proportional to a product of Boltzmann weights assigned to their $2$-connected components. As their number of vertices tends to infinity, we show that they admit the Brownian tree as Gromov--Hausdorff--Prokhorov scaling limit, and converge in a strengthened Benjamini--Schramm sense toward an infinite random graph. We also consider a family of random graphs that are allowed to be disconnected. Here a giant connected component emerges and the small fragments converge without any rescaling towards a finite random limit graph.

We study the phase diagram of random outerplanar maps sampled according to non-negative Boltzmann weights that are assigned to each face of a map. We prove that for certain choices of weights the map looks like a rescaled version of its boundary when its number of vertices tends to infinity. The Boltzmann outerplanar maps are then shown to converge in the Gromov-Hausdorff sense towards the $\alpha$-stable looptree introduced by Curien and Kortchemski (2014), with the parameter $\alpha$ depending on the specific weight-sequence. This allows us to describe the transition of the asymptotic geometric shape from a deterministic circle to the Brownian tree.

We study a model of random $\mathcal{R}$-enriched trees that is based on weights on the $\mathcal{R}$-structures and allows for a unified treatment of a large family of random discrete structures. We establish distributional limits describing local convergence around fixed and random points in this general context, limit theorems for component sizes when $\mathcal{R}$ is a composite class, and a Gromov--Hausdorff scaling limit of random metric spaces patched together from independently drawn metrics on the $\mathcal{R}$-structures. Our main applications treat a selection of examples encompassed by this model. We consider random outerplanar maps sampled according to arbitrary weights assigned to their inner faces, and classify in complete generality distributional limits for both the asymptotic local behaviour near the root-edge and near a uniformly at random drawn vertex. We consider random connected graphs drawn according to weights assigned to their blocks and establish a Benjamini--Schramm limit. We also apply our framework to recover in a probabilistic way a central limit theorem for the size of the largest $2$-connected component in random graphs from planar-like classes. We prove Benjamini--Schramm convergence of random $k$-dimensional trees and establish both scaling limits and local weak limits for random planar maps drawn according to Boltzmann-weights assigned to their $2$-connected components.

We discuss various forms of convergence of the vicinity of a uniformly at random selected vertex in random simply generated trees, as the size tends to infinity. For the standard case of a critical Galton-Watson tree conditioned to be large the limit is the invariant random sin-tree constructed by Aldous (1991). In the condensation regime, we describe in complete generality the asymptotic local behaviour from a random vertex up to its first ancestor with large degree. Beyond this distinguished ancestor, different behaviour may occur, depending on the branching weights. In a subregime of complete condensation, we obtain convergence toward a novel limit tree, that describes the asymptotic shape of the vicinity of the full path from a random vertex to the root vertex. This includes the case where the offspring distribution follows a power law up to a factor that varies slowly at infinity.

We study random composite structures considered up to symmetry that are sampled according to weights on the inner and outer structures. This model may be viewed as an unlabelled version of Gibbs partitions and encompasses multisets of weighted combinatorial objects. We describe a general setting characterized by the formation of a giant component. The collection of small fragments is shown toconverge in total variation toward a limit object following a P\'olya-Boltzmann distribution., Comment: arXiv admin note: text overlap with arXiv:1609.08859

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

For any set $\Omega$ of non-negative integers such that $\{0,1\}\subseteq \Omega$ and $\{0,1\}\ne \Omega$, we consider a random $\Omega$-$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 $\Omega$. We prove that ${\sf G}_{n,k}$, scaled by $(kH_{k}\sigma_{\Omega})/(2\sqrt{n})$ where $H_{k}$ is the $k$-th Harmonic number and $\sigma_{\Omega}>0$, converges to the Continuum Random Tree $\mathcal{T}_{{\sf e}}$. Furthermore, we prove the local convergence of the rooted random $\Omega$-$k$-tree ${\sf G}_{n,k}^{\circ}$ to an infinite but locally finite random $\Omega$-$k$-tree ${\sf G}_{\infty,k}$., Comment: 21 pages, 6 figures

The scaling limit of large simple outerplanar maps was established by Caraceni using a bijection due to Bonichon, Gavoille and Hanusse. The present paper introduces a new bijection between outerplanar maps and trees decorated with ordered sequences of edge-rooted dissections of polygons. We apply this decomposition in order to provide a new, short proof of the scaling limit that also applies to the general setting of first-passage percolation. We obtain sharp tail-bounds for the diameter and recover the asymptotic enumeration formula for outerplanar maps. Our methods also enable us treat subclasses such as bipartite outerplanar maps.

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.

P\'olya trees are rooted trees considered up to symmetry. We establish the convergence of large uniform random P\'olya trees with arbitrary degree restrictions to Aldous' Continuum Random Tree with respect to the Gromov-Hausdorff metric. Our proof is short and elementary, and it shows that the global shape of a random P\'olya tree is essentially dictated by a large Galton-Watson tree that it contains. We also derive sub-Gaussian tail bounds for both the height and the width, which are optimal up to constant factors in the exponent.

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.

We study the uniform random graph $\mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_n / \sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_{\mathsf{e}}$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter $\text{D}(\mathsf{C}_n)$ and height $\text{H}(\mathsf{C}_n^\bullet)$ of the rooted random graph $\mathsf{C}_n^\bullet$. We give analytic expressions for the scaling factor of several classes, including for example the prominent class of outerplanar graphs. Our methods also enable us to study first passage percolation on $\mathsf{C}_n$, where we show the convergence to $\mathcal{T}_{\mathsf{e}}$ under an appropriate rescaling.