The invariant Galton–Watson (IGW) tree measures are a one-parameter family of critical Galton–Watson measures invariant with respect to a large class of tree reduction operations. Such operations include the generalized dynamical pruning (also known as hereditary reduction in a real tree setting) that eliminates descendant subtrees according to the value of an arbitrary subtree function that is monotone nondecreasing with respect to an isometry-induced partial tree order. We show that, under a mild regularity condition, the IGW measures are attractors of arbitrary critical Galton–Watson measures with respect to the generalized dynamical pruning. We also derive the distributions of height, length, and size of the IGW trees.

We consider fragmentation processes with values in the space of marked partitions of $\mathbb{N}$, i.e. partitions where each block is decorated with a nonnegative real number. Assuming that the marks on distinct blocks evolve as independent positive self-similar Markov processes and determine the speed at which their blocks fragment, we get a natural generalization of the self-similar fragmentations of Bertoin (Ann. Inst. H. Poincaré Prob. Statist.38, 2002). Our main result is the characterization of these generalized fragmentation processes: a Lévy–Khinchin representation is obtained, using techniques from positive self-similar Markov processes and from classical fragmentation processes. We then give sufficient conditions for their absorption in finite time to a frozen state, and for the genealogical tree of the process to have finite total length.

We introduce a class of non-uniform random recursive trees grown with an attachment preference for young age. Via the Chen–Stein method of Poisson approximation, we find that the outdegree of a node is characterized in the limit by ‘perturbed’ Poisson laws, and the perturbation diminishes as the node index increases. As the perturbation is attenuated, a pure Poisson limit ultimately emerges in later phases. Moreover, we derive asymptotics for the proportion of leaves and show that the limiting fraction is less than one half. Finally, we study the insertion depth in a random tree in this class. For the insertion depth, we find the exact probability distribution, involving Stirling numbers, and consequently we find the exact and asymptotic mean and variance. Under appropriate normalization, we derive a concentration law and a limiting normal distribution. Some of these results contrast with their counterparts in the uniform attachment model, and some are similar.

In this paper we consider random trees associated with the genealogy of Crump–Mode–Jagers processes and perform Bernoulli bond-percolation whose parameter depends on the size of the tree. Our purpose is to show the existence of a giant percolation cluster for appropriate regimes as the size grows. We stress that the family trees of Crump–Mode–Jagers processes include random recursive trees, preferential attachment trees, binary search trees for which this question has been answered by Bertoin [7], as well as (more general) m-ary search trees, fragmentation trees, and median-of-( $2\ell+1$ ) binary search trees, to name a few, where to our knowledge percolation has not yet been studied.

The accessibility percolation model is investigated on random rooted labeled trees. More precisely, the number of accessible leaves (i.e. increasing paths) Zn and the number of accessible vertices Cn in a random rooted labeled tree of size n are jointly considered in this work. As n → ∞, we prove that (Zn, Cn) converges in distribution to a random vector whose probability generating function is given in an explicit form. In particular, we obtain that the asymptotic distributions of Zn + 1 and Cn are geometric distributions with parameters e/(1 + e) and 1/e, respectively. Much of our analysis is performed in the context of local weak convergence of random rooted labeled trees.

In Balaji and Mahmoud [1], the authors introduced a distance-based Gini index for rooted trees. In this paper, we introduce a degree-based Gini index (or just simply degree Gini index) for graphs. The latter index is a topological measure on a graph capturing the proximity to regular graphs. When applied across the random members of a class of graphs, we can identify an average measure of regularity for the class. Whence, we can compare the classes of graphs from the vantage point of closeness to regularity.

We develop a simplified computational formula for the degree Gini index and study its extreme values. We show that the degree Gini index falls in the interval [0, 1). The main focus in our study is the degree Gini index for the class of binary trees. Via a left-packing transformation, we show that, for an arbitrary sequence of binary trees, the Gini index has inferior and superior limits in the interval [0, 1/4]. We also show, via the degree Gini index, that uniform rooted binary trees are more regular than binary search trees grown from random permutations.

We propose two distance-based topological indices (level index and Gini index) as measures of disparity within a single tree and within tree classes. The level index and the Gini index of a single tree are measures of balance within the tree. On the other hand, the Gini index for a class of random trees can be used as a comparative measure of balance between tree classes. We establish a general expression for the level index of a tree. We compute the Gini index for two random classes of caterpillar trees and see that a random multinomial model of trees with finite height has a countable number of limits in [0, ⅓], whereas a model with independent level numbers fills the spectrum (0, ⅓].

We consider a marking procedure of the vertices of a tree where each vertex is marked independently from the others with a probability that depends only on its out-degree. We prove that a critical Galton–Watson tree conditioned on having a large number of marked vertices converges in distribution to the associated size-biased tree. We then apply this result to give the limit in distribution of a critical Galton–Watson tree conditioned on having a large number of protected nodes.

It is well known that the central limit theorem holds for partial sums of a stationary sequence (Xi) of m-dependent random variables with finite variance; however, the limit may be degenerate with variance 0 even if var(Xi) ≠ 0. We show that this happens only in the case when Xi – EXi = Yi – Yi–1 for an (m − 1)-dependent stationary sequence (Yi) with finite variance (a result implicit in earlier results), and give a version for block factors. This yields a simple criterion that is a sufficient condition for the limit not to be degenerate. Two applications to subtree counts in random trees are given.

We study semi-infinite paths of the radial spanning tree (RST) of a Poisson point process in the plane. We first show that the expectation of the number of intersection points between semi-infinite paths and the sphere with radius r grows sublinearly with r. Then we prove that in each (deterministic) direction there exists, with probability 1, a unique semi-infinite path, framed by an infinite number of other semi-infinite paths of close asymptotic directions. The set of (random) directions in which there is more than one semi-infinite path is dense in [0, 2π). It corresponds to possible asymptotic directions of competition interfaces. We show that the RST can be decomposed into at most five infinite subtrees directly connected to the root. The interfaces separating these subtrees are studied and simulations are provided.

This paper is based on works presented at the 2012 Applied Probability Trust Lecture in Sheffield; its main purpose is to survey the recent asymptotic results of Bertoin (2012a) and Bertoin and Uribe Bravo (2012b) about Bernoulli bond percolation on certain large random trees with logarithmic height. We also provide a general criterion for the existence of giant percolation clusters in large trees, which answers a question raised by David Croydon.

We introduce and analyze a random tree model associated to Hoppe's urn. The tree is built successively by adding nodes to the existing tree when starting with the single root node. In each step a node is added to the tree as a child of an existing node, where these parent nodes are chosen randomly with probabilities proportional to their weights. The root node has weight ϑ>0, a given fixed parameter, all other nodes have weight 1. This resembles the stochastic dynamic of Hoppe's urn. For ϑ=1, the resulting tree is the well-studied random recursive tree. We analyze the height, internal path length, and number of leaves of the Hoppe tree with n nodes as well as the depth of the last inserted node asymptotically as n→∞. Mainly expectations, variances, and asymptotic distributions of these parameters are derived.

We consider a multivariate distributional recursion of sum type, as arises in the probabilistic analysis of algorithms and random trees. We prove an upper tail bound for the solution using Chernoff's bounding technique by estimating the Laplace transform. The problem is traced back to the corresponding problem for binary search trees by stochastic domination. The result obtained is applied to the internal path length and Wiener index of random b-ary recursive trees with weighted edges and random linear recursive trees. Finally, lower tail bounds for the Wiener index of these trees are given.

We investigate the Zagreb index, one of the topological indices, of random recursive trees in this paper. Through a recurrence equation, the first two moments of Z n , the Zagreb index of a random recursive tree of size n, are obtained. We also show that the random process {Z n − E[Z n ], n ≥ 1} is a martingale. Then the asymptotic normality of the Zagreb index of a random recursive tree is given by an application of the martingale central limit theorem. Finally, two other topological indices are also discussed in passing.

Limit theorems are established for some functionals of the distances between two nodes in weighted random b-ary recursive trees. We consider the depth of the nth node and of a random node, the distance between two random nodes, the internal path length, and the Wiener index. As an application, these limit results imply, by an imbedding argument, corresponding limit theorems for further classes of random trees: plane-oriented recursive trees and random linear recursive trees.

In this paper we study the number of random records in an arbitrary split tree (or, equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for the convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree in Holmgren (2010), which is one specific case of split trees. Other important examples of split trees include m-ary search trees, quad trees, medians of (2k + 1)-trees, simplex trees, tries, and digital search trees.

On the boundary of a Galton-Watson tree we can define the visibility measure by splitting mass equally between the children of each vertex, and the branching measure by splitting unit mass equally between all vertices in the nth generation and then letting n go to infinity. The multifractal structure of each of these measures is well studied. In this paper we address the question of a joint multifractal spectrum, i.e. we ask for the Hausdorff dimension of the boundary points which simultaneously have an unusual local dimension for both these measures. The resulting two-parameter spectrum exhibits a number of surprising new features, among them the emergence of a swallowtail-shaped spectrum for the visibility measure in the presence of a nontrivial condition on the branching measure.

We consider a variety of subtrees of various shapes lying on the fringe of a recursive tree. We prove that (under suitable normalization) the number of isomorphic images of a given fixed tree shape on the fringe of the recursive tree is asymptotically Gaussian. The parameters of the asymptotic normal distribution involve the shape functional of the given tree. The proof uses the contraction method.

The probability that two randomly selected phylogenetic trees of the same size are isomorphic is found to be asymptotic to a decreasing exponential modulated by a polynomial factor. The number of symmetrical nodes in a random phylogenetic tree of large size obeys a limiting Gaussian distribution, in the sense of both central and local limits. The probability that two random phylogenetic trees have the same number of symmetries asymptotically obeys an inverse square-root law. Precise estimates for these problems are obtained by methods of analytic combinatorics, involving bivariate generating functions, singularity analysis, and quasi-powers approximations.

In this paper, we consider a possible representation of a DNA sequence in a quaternary tree, in which one can visualize repetitions of subwords(seen as suffixes of subsequences). The CGR-tree turns a sequence of letters into a Digital Search Tree (DST), obtained from the suffixes of the reversed sequence. Several results are known concerning the height, the insertion depth for DST built from independent successive random sequences having the same distribution. Here the successive inserted words are strongly dependent. We give the asymptotic behaviour of the insertion depth and the length of branches for the CGR-tree obtained from the suffixes of a reversed i.i.d. or Markovian sequence.This behaviour turns out to be at first order the same one as in the case of independent words. As a by-product, asymptotic results on the length of longest runs in a Markovian sequence are obtained.