Distances between pairs of vertices and vertical profile in conditioned Galton–Watson trees

We consider a conditioned Galton–Watson tree and prove an estimate of the number of pairs of vertices with a given distance, or, equivalently, the number of paths of a given length. We give two proofs of this result, one probabilistic and the other using generating functions and singularity analysis. Moreover, the latter proof yields a more general estimate for generating functions, which is used to prove a conjecture by Bousquet–Mélou and Janson (Bousquet‐Mélou and Janson, Ann Appl Probab 16 (2006) 1597–1632), saying that the vertical profile of a randomly labelled conditioned Galton–Watson tree converges in distribution, after suitable normalization, to the density of ISE (Integrated Superbrownian Excursion). © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 381–395, 2011     

A system of grabbing particles related to Galton‐Watson trees

We consider a system of particles with arms that are activated randomly to grab other particles as a toy model for polymerization. We assume that the following two rules are fulfilled: once a particle has been grabbed then it cannot be grabbed again, and an arm cannot grab a particle that belongs to its own cluster. We are interested in the shape of a typical polymer in the situation when the initial number of monomers is large and the numbers of arms of monomers are given by i.i.d. random variables. Our main result is a limit theorem for the empirical distribution of polymers, where limit is expressed in terms of a Galton‐Watson tree. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton–Watson trees

We consider conditioned Galton–Watson trees and show asymptotic normality of additive functionals that are defined by toll functions that are not too large. This includes, as a special case, asymptotic normality of the number of fringe subtrees isomorphic to any given tree, and joint asymptotic normality for several such subtree counts. Another example is the number of protected nodes. The offspring distribution defining the random tree is assumed to have expectation 1 and finite variance; no further moment condition is assumed. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 57–101, 2016     

Graph limits of random graphs from a subset of connected k‐trees

For any set Ω of non‐negative integers such that , we consider a random Ω‐k‐tree G_n,k that is uniformly selected from all connected k‐trees of (n + k) vertices such that the number of (k + 1)‐cliques that contain any fixed k‐clique belongs to Ω. We prove that G_n,k, scaled by where H_k is the kth harmonic number and σ_Ω > 0, converges to the continuum random tree . Furthermore, we prove local convergence of the random Ω‐k‐tree to an infinite but locally finite random Ω‐k‐tree G_∞,k.     

Random non‐crossing plane configurations: A conditioned Galton‐Watson tree approach

We study various models of random non‐crossing configurations consisting of diagonals of convex polygons, and focus in particular on uniform dissections and non‐crossing trees. For both these models, we prove convergence in distribution towards Aldous’ Brownian triangulation of the disk. In the case of dissections, we also refine the study of the maximal vertex degree and validate a conjecture of Bernasconi, Panagiotou and Steger. Our main tool is the use of an underlying Galton‐Watson tree structure. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 236–260, 2014     

Random tree recursions: Which fixed points correspond to tangible sets of trees?

Let be the set of rooted trees containing an infinite binary subtree starting at the root. This set satisfies the metaproperty that a tree belongs to it if and only if its root has children u and v such that the subtrees rooted at u and v belong to it. Let p be the probability that a Galton‐Watson tree falls in . The metaproperty makes p satisfy a fixed‐point equation, which can have multiple solutions. One of these solutions is p, but what is the meaning of the others? In particular, are they probabilities of the Galton‐Watson tree falling into other sets satisfying the same metaproperty? We create a framework for posing questions of this sort, and we classify solutions to fixed‐point equations according to whether they admit probabilistic interpretations. Our proofs use spine decompositions of Galton‐Watson trees and the analysis of Boolean functions.     

Random suffix search trees

A random suffix search tree is a binary search tree constructed for the suffixes X_i = 0 · B_iB_i+1B_i+2… of a sequence B₁, B₂, B₃, … of independent identically distributed random b‐ary digits B_j. Let D_n denote the depth of the node for X_n in this tree when B₁ is uniform on ?_b. We show that for any value of b > 1, ??D_n = 2 log n + O(log²log n), just as for the random binary search tree. We also show that D_n/??D_n → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Bisexual Galton‐Watson Branching Process in Varying Environments

Abstract

In this paper we introduce a bisexual Galton‐Watson branching process (BGWP) in which the offspring probability distribution is different in each generation. We obtain some relations among the probability generating functions (pgf) involved in the model and, making use of mean growth rates and fractional linear functions (flf), we provide sufficient and necessary conditions for its almost sure extinction.     

On the complexity of branch‐and‐bound search for random trees

Let T_n be a b‐ary tree of height n, which has independent, non‐negative, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T_n. Assume that the edge random variable X is nondegenerate, has E {X^θ}<∞ for some θ>2, and satisfies bP{X=c}<1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch‐and‐bound algorithm for this problem and prove that the number of nodes visited is in probability (β+o(1))ⁿ, where β∈(1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for β are derived. We also show that any search algorithm must visit (β+o(1))ⁿ nodes with probability tending to 1, so branch‐and‐bound is asymptotically optimal where first‐order asymptotics are concerned. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 309–327, 1999     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

Existential monadic second order logic on random rooted trees

We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton–Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).     

Growth of Lévy trees

We construct random locally compact real trees called Lévy trees that are the genealogical trees associated with continuous-state branching processes. More precisely, we define a growing family of discrete Galton–Watson trees with i.i.d. exponential branch lengths that is consistent under Bernoulli percolation on leaves; we define the Lévy tree as the limit of this growing family with respect to the Gromov–Hausdorff topology on metric spaces. This elementary approach notably includes supercritical trees and does not make use of the height process introduced by Le Gall and Le Jan to code the genealogy of (sub)critical continuous-state branching processes. We construct the mass measure of Lévy trees and we give a decomposition along the ancestral subtree of a Poisson sampling directed by the mass measure. T. Duquesne is supported by NSF Grants DMS-0203066 and DMS-0405779. M. Winkel is supported by Aon and the Institute of Actuaries, EPSRC Grant GR/T26368/01, le département de mathématique de l’Université d’Orsay and NSF Grant DMS-0405779.     

Percolation on random recursive trees

We study Bernoulli bond percolation on a random recursive tree of size n with percolation parameter p(n) converging to 1 as n tends to infinity. The sizes of the percolation clusters are naturally stored in a tree structure. We prove convergence in distribution of this tree‐indexed process of cluster sizes to the genealogical tree of a continuous‐state branching process in discrete time. As a corollary we obtain the asymptotic sizes of the largest and next largest percolation clusters, extending thereby a recent work of Bertoin [5]. In a second part, we show that the same limit tree appears in the study of the tree components which emerge from a continuous‐time destruction of a random recursive tree. We comment on the connection to our first result on Bernoulli bond percolation. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 655–680, 2016     

Justifying the small‐world phenomenon via random recursive trees

We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. The advantage of the technique is three‐fold: it is quite simple and provides short proofs, it is applicable to a broad variety of models including those incorporating preferential attachment, and it provides bounds with small constants. We illustrate this by proving, for the first time, logarithmic upper bounds for the diameters of the following well known models: the forest fire model, the copying model, the PageRank‐based selection model, the Aiello‐Chung‐Lu models, the generalized linear preference model, directed scale‐free graphs, the Cooper‐Frieze model, and random unordered increasing k‐trees. Our results shed light on why the small‐world phenomenon is observed in so many real‐world graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 201–224, 2017     

Selection by rank in K‐dimensional binary search trees

In this work we show how to augment general purpose multidimensional data structures, such as K‐d trees, to efficiently support search by rank (that is, to locate the i‐th smallest element along the j‐th coordinate, for given i and j) and to find the rank of a given item along a given coordinate. To do so, we introduce two simple, practical and very flexible algorithms – Select‐by‐Rank and Find‐Rank – with very little overhead. Both algorithms can be easily implemented and adapted to several spatial indexes, although their analysis is far from trivial. We are able to show that for random K‐d trees of size n the expected number of nodes visited by Find‐Rank is for or , and for (with ), where depends on the dimension K and the variant of K‐d tree under consideration. We also show that Select‐by‐Rank visits nodes on average, where is the given rank and the exponent α is as above. We give the explicit form of the functions and , both are bounded in [0, 1] and they depend on K, on the variant of K‐d tree under consideration, and, eventually, on the specific coordinate j for which we execute our algorithms. As a byproduct of the analysis of our algorithms, but no less important, we give the average‐case analysis of a partial match search in random K‐d trees when the query is not random. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 14–37, 2014     

Limit laws for local counters in random binary search trees

Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for w-dependent random variables. Examples include: the number of leaves (L_n), the number of nodes with k descendants (k fixed), the number of nodes with no left child, the number of nodes with k left descendants. Some of these results can also be obtained via the theory of urn models, but the present method seems easier to apply.     

The height of depth‐weighted random recursive trees

In this paper, we introduce a model of depth‐weighted random recursive trees, created by recursively joining a new leaf to an existing vertex . In this model, the probability of choosing depends on its depth in the tree. In particular, we assume that there is a function such that if has depth then its probability of being chosen is proportional to . We consider the expected value of the diameter of this model as determined by , and for various increasing we find expectations that range from polylogarithmic to linear.