Logo: to the web site of Uppsala University

In this paper, we study uniform rooted plane trees with given degree sequence. We show that, under some natural hypotheses on the degree sequences, these trees converge towards the so-called Inhomogeneous Continuum Random Tree after renormalization. Our proof relies on the convergence of a modification of the well-known & Lstrok;ukasiewicz path. We also give a unified treatment of the limit, as the number of vertices tends to infinity, of the fragmentation process derived by cutting down the edges of a tree with a given degree sequence, including its geometric representation by a lamination-valued process. The latter is a collection of nested laminations, which are compact subsets of the unit disk made of non-crossing chords. In particular, we prove an equivalence between planar Gromov-weak convergence of discrete trees and the convergence of their associated lamination-valued processes.

We use Stein’s method to obtain distributional approximations of subgraph counts in the uniform attachment model or random directed acyclic graph; we provide also estimates of rates of convergence. In particular, we give uni- and multi-variate Poisson approximations to the counts of cycles and normal approximations to the counts of unicyclic subgraphs; we also give a partial result for the counts of trees. We further find a class of multicyclic graphs whose subgraph counts are a.s. bounded as n→∞.

We prove asymptotic normality for the number of fringe subtrees isomorphic to any given tree in uniformly random trees with given vertex degrees. As applications, we also prove corresponding results for random labeled trees with given vertex degrees, for random simply generated trees (or conditioned Galton-Watson trees), and for additive functionals. The key tool for our work is an extension to the multivariate setting of a theorem by Gao and Wormald (2004), which provides a way to show asymptotic normality by analyzing the behavior of sufficiently high factorial moments.

We prove that the number of fringe subtrees, isomorphic to a given tree, in uniformly random trees with given vertex degrees, asymptotically follows a normal distribution. As an application, we establish the same asymptotic normality for random simply generated trees (conditioned Galton-Watson trees). Our approach relies on an extension of Gao and Wormald's (2004) theorem to the multivariate setting.

We consider random two-colorings of random linear preferential attachment trees, which includes recursive trees, plane-oriented recursive trees, binary search trees, and a class of d-ary trees. The random coloring is defined by assigning the root the color red or blue with equal probability, and all other vertices are assigned the color of their parent with probability p$$ p $$ and the other color otherwise. These colorings have been previously studied in other contexts, including Ising models and broadcasting, and can be considered as generalizations of bond percolation. With the help of Polya urns, we prove limiting distributions, after proper rescalings, for the number of vertices, monochromatic subtrees, and leaves of each color, as well as the number of fringe subtrees with two-colorings. Using methods from analytic combinatorics, we also provide precise descriptions of the limiting distribution after proper rescaling of the size of the root cluster; the largest monochromatic subtree containing the root.

Aldous, Evans and Pitman (1998) studied the behavior of the fragmentation process derived from deleting the edges of a uniform random tree on n labelled vertices. In particular, they showed that, after proper rescaling, the above fragmentation process converges as n -> infinity to the fragmentation process of the Brownian CRT obtained by cutting-down the Brownian CRT along its skeleton in a Poisson manner. In this work, we continue the above investigation and study the fragmentation process obtained by deleting randomly chosen edges from a critical Galton-Watson tree t(n) conditioned on having n vertices, whose offspring distribution belongs to the domain of attraction of a stable law of index alpha is an element of(1,2]. Our main results establish that, after rescaling, the fragmentation process of t(n) converges as n -> infinity to the fragmentation process obtained by cutting-down at a rate proportional to the length measure on the skeleton of an alpha-stable Levy tree. We further show that the latter can be constructed by considering the partitions of the unit interval induced by the normalized alpha-stable Levy excursion with a deterministic drift studied by Miermont (2001). This extends the result of Bertoin (2000) on the fragmentation process of the Brownian CRT.

The class of linear preferential attachment trees includes recursive trees, plane-oriented recursive trees, binary search trees, and increasing d-ary trees. Bond percolation with parameter p is performed by considering every edge in a graph independently, and either keeping the edge with probability p or removing it otherwise. The resulting connected components are called clusters. In this extended abstract, we demonstrate how to use methods from analytic combinatorics to compute limiting distributions, after rescaling, for the size of the cluster containing the root. These results are part of a larger work on broadcasting induced colorings of preferential attachment trees.

We study the fragmentation process obtained by deleting randomly chosen edges from a critical Galton-Watson tree 𝐭_n conditioned on having n vertices, whose offspring distribution belongs to the domain of attraction of a stable law of index α ∈ (1,2]. This fragmentation process is analogous to that introduced in the works of Aldous, Evans and Pitman (1998), who considered the case of Cayley trees. Our main result establishes that, after rescaling, the fragmentation process of 𝐭_n converges as n → ∞ to the fragmentation process obtained by cutting-down proportional to the length on the skeleton of an α-stable Lévy tree of index α ∈ (1,2]. We further establish that the latter can be constructed by considering the partitions of the unit interval induced by the normalized α-stable Lévy excursion with a deterministic drift studied by Miermont (2001). In particular, this extends the result of Bertoin (2000) on the fragmentation process of the Brownian CRT.

We consider the model of random trees introduced by Devroye, the so-called random split trees. The model encompasses many important randomized algorithms and data structures. We then perform supercritical Bernoulli bond-percolation on those trees and obtain a precise weak limit theorem for the sizes of the largest clusters. We also show that the approach developed in this work may be useful for studying percolation on other classes of trees with logarithmic height, for instance, we also study the case of d-regular trees.

A split tree of cardinality n is constructed by distributing n “balls” in a subset ofvertices of an infinite tree which encompasses many types of random trees such as m-ary searchtrees, quad trees, median-of-(2k + 1) trees, fringe-balanced trees, digital search trees and randomsimplex trees. In this work, we study Bernoulli bond percolation on arbitrary split trees of large butfinite cardinality n. We show for appropriate percolation regimes that depend on the cardinalityn of the split tree that there exists a unique giant cluster, the fluctuations of the size of the giantcluster as n → ∞ are described by an infinitely divisible distribution that belongs to the class ofstable (asymmetric) Cauchy laws. This work generalizes the results for the random m-ary recursivetrees by Berzunza (2015). Our approach is based on a remarkable decomposition of the size of thegiant percolation cluster as a sum of essentially independent random variables which may be usefulfor studying percolation on other trees with logarithmic height; for instance in this work we studyalso the case of regular trees.