Asymptotics of trees with a prescribed degree sequence and applications

Let t be a rooted tree and n_bi(t) the number of nodes in t having i children. The degree sequence of t satisfies , where denotes the number of nodes in t. In this paper, we consider trees sampled uniformly among all plane trees having the same degree sequence ; we write for the corresponding distribution. Let be a list of degree sequences indexed by κ corresponding to trees with size . We show that under some simple and natural hypotheses on the trees sampled under converge to the Brownian continuum random tree after normalisation by . Some applications concerning Galton–Watson trees and coalescence processes are provided.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 290‐316, 2014     

Tail bounds for the height and width of a random tree with a given degree sequence

Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}$ be a plane tree drawn uniformly at random from among all plane trees with child sequence c . In this note we prove sub‐Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of ${\mathcal T}$. These bounds are optimal up to the constant in the exponent when c satisfies $\sum_{i=1}^n c_i^2=O(n)$; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Central limit theorems for a branching random walk with a random environment in time

We consider a branching random walk with a random environment in time, in which the offspring distribution of a particle of generation n and the distribution of the displacements of its children depend on an environment indexed by the time n. The environment is supposed to be independent and identically distributed. For A ?, let Z_n(A) be the number of particles of generation n located in A. We show central limit theorems for the counting measure Z_n(·) with appropriate normalization.     

Geometry of large Boltzmann outerplanar maps

We study the phase diagram of random outerplanar maps sampled according to nonnegative 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 α‐stable looptree introduced by Curien and Kortchemski (2014), with the parameter α 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.     

On martingale tail sums for the path length in random trees

For a martingale (X_n) converging almost surely to a random variable X, the sequence (X_n– X) is called martingale tail sum. Recently, Neininger (Random Structures Algorithms 46 (2015), 346–361) proved a central limit theorem for the martingale tail sum of Régnier's martingale for the path length in random binary search trees. Grübel and Kabluchko (in press) gave an alternative proof also conjecturing a corresponding law of the iterated logarithm. We prove the central limit theorem with convergence of higher moments and the law of the iterated logarithm for a family of trees containing binary search trees, recursive trees and plane‐oriented recursive trees. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 493–508, 2017     

Branching random walk with a critical branching part

We consider the branching treeT(n) of the first (n+1) generations of a critical branching process, conditioned on survival till time βn for some fixed β>0 or on extinction occurring at timek _n withk _n /n→β. We attach to each vertexv of this tree a random variableX(v) and define , where π(0,v) is the unique path in the family tree from its root tov. FinallyM _n is the maximal displacement of the branching random walkS(·), that isM _n =max{S(v):v∈T(n)}. We show that if theX(v), v∈T(n), are i.i.d. with mean 0, then under some further moment conditionn ^−1/2 M _n converges in distribution. In particular {n ^−1/2 M _n } _n⩾1 is a tight family. This is closely related to recent results about Aldous' continuum tree and Le Gall's Brownian snake.     

A functional limit theorem for random graphs with applications to subgraph count statistics

We consider a random graph that evolves in time by adding new edges at random times (different edges being added at independent and identically distributed times). A functional limit theorem is proved for a class of statistics of the random graph, considered as stochastic processes. the proof is based on a martingale convergence theorem. the evolving random graph allows us to study both the random graph model K_{n, p}, by fixing attention to a fixed time, and the model K_{n, N}, by studying it at the random time it contains exactly N edges. in particular, we obtain the asymptotic distribution as n → ∞ of the number of subgraphs isomorphic to a given graph G, both for K_{n, p} (p fixed) and K_{n, N} (N/(ⁿ₂)→ p). the results are strikingly different; both models yield asymptotically normal distributions, but the variances grow as different powers of n (the variance grows slower for K_n, N; the powers of n usually differ by 1, but sometimes by 3). We also study the number of induced subgraphs of a given type and obtain similar, but more complicated, results. in some exceptional cases, the limit distribution is not normal.     

SIR epidemics on random graphs with a fixed degree sequence

Let Δ > 1 be a fixed positive integer. For \begin{align*}{\textbf{ {z}}} \in \mathbb{R}_+^\Delta\end{align*} let G_z be chosen uniformly at random from the collection of graphs on ∥z∥₁n vertices that have z_in vertices of degree i for i = 1,…,Δ. We determine the likely evolution in continuous time of the SIR model for the spread of an infectious disease on G_z, starting from a single infected node. Either the disease halts after infecting only a small number of nodes, or an epidemic spreads to infect a linear number of nodes. Conditioning on the event that more than a small number of nodes are infected, the epidemic is likely to follow a trajectory given by the solution of an associated system of ordinary differential equations. These results also give the likely number of nodes infected during the course of the epidemic and the likely length in time of the epidemic. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Scaling exponents of random walks in random sceneries

We compute the exact asymptotic normalizations of random walks in random sceneries, for various null recurrent random walks to the nearest neighbours, and for i.i.d., centered and square integrable random sceneries. In each case, the standard deviation grows like n with . Here, the value of the exponent is determined by the sole geometry of the underlying graph, as opposed to previous examples, where this value reflected mainly the integrability properties of the steps of the walk, or of the scenery. For discrete Bessel processes of dimension d[0;2[, the exponent is . For the simple walk on some specific graphs, whose volume grows like n^d for d[1;2[, the exponent is =1−d/4. We build a null recurrent walk, for which without logarithmic correction. Last, for the simple walk on a critical Galton–Watson tree, conditioned by its nonextinction, the annealed exponent is . In that setting and when the scenery is i.i.d. by levels, the same result holds with .     

Vertices of degree k in random unlabeled trees

Let ??_n be the class of unlabeled trees with n vertices, and denote by H _n a tree that is drawn uniformly at random from this set. The asymptotic behavior of the random variable deg_k(H _n) that counts vertices of degree k in H _n was studied, among others, by Drmota and Gittenberger in [J Graph Theory 31(3) (1999), 227–253], who showed that this quantity satisfies a central limit theorem. This result provides a very precise characterization of the “central region” of the distribution, but does not give any non‐trivial information about its tails. In this work, we study further the number of vertices of degree k in H _n. In particular, for k = ??((logn/(loglogn))^1/2) we show exponential‐type bounds for the probability that deg_k(H _n) deviates from its expectation. On the technical side, our proofs are based on the analysis of a randomized algorithm that generates unlabeled trees in the so‐called Boltzmann model. The analysis of such algorithms is quite well‐understood for classes of labeled graphs, see e.g. the work [Bernasconi et al., SODA '08: Proceedings of the 19th Annual ACM‐SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2008, pp. 132–141; Bernasconi et al., Proceedings of the 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization, Springer, Berlin, 2008, pp. 303–316] by Bernasconi, the first author, and Steger. Comparable algorithms for unlabeled classes are unfortunately much more complex. We demonstrate in this work that they can be analyzed very precisely for classes of unlabeled graphs as well. © 2011 Wiley Periodicals, Inc. J Graph Theory. 69:114‐130, 2012     

On the profile of random trees

Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree may be described by the number of nodes or the number of leaves in layer , respectively. It is shown that these two processes converge weakly to Brownian excursion local time. This is done via characteristic functions obtained by means of generating functions arising from the combinatorial setup and complex contour integration. Besides, an integral representation for the two-dimensional density of Brownian excursion local time is derived. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 421–451, 1997     

Scaling Limits of Bipartite Planar Maps are Homeomorphic to the 2-Sphere

We prove that scaling limits of random planar maps which are uniformly distributed over the set of all rooted 2k-angulations are a.s. homeomorphic to the two-dimensional sphere. Our methods rely on the study of certain random geodesic laminations of the disk. Received: December 2006, Revision: August 2007, Accepted: October 2007     

The order of the giant component of random hypergraphs

We establish central and local limit theorems for the number of vertices in the largest component of a random d‐uniform hypergraph H_d(n,p) with edge probability p = c/ , where c > (d ‐ 1)^‐1 is a constant. The proof relies on a new, purely probabilistic approach. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

The distribution of nodes of given degree in random trees

Let 𝒯_n denote the set of unrooted unlabeled trees of size n and let k ≥ 1 be given. By assuming that every tree of 𝒯_n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ∼ μ_kn and variance ∼ σn with positive constants μ_k and σ_k. Besides, the asymptotic behavior of μ_k and σ_k for k → ∞ as well as the corresponding multivariate distributions are derived. Furthermore, similar results can be proved for plane trees, for labeled trees, and for forests. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 227–253, 1999     

A Note on “State Spaces of the Snake and Its Tour—Convergence of the Discrete Snake” by J.-F. Marckert and A. Mokkadem

In State spaces of the snake and its tour—Convergence of the discrete snake the authors showed a limit theorem for Galton–Watson trees with geometric offspring distribution. In this note it is shown that their result holds for all Galton–Watson trees with finite offspring variance.     

Geometry of the vacant set left by random walk on random graphs,Wright's constants,and critical random graphs with prescribed degrees

We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (1) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (2) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by ?erný and Teixeira study by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs.     

Convergence of Discrete Snakes

The discrete snake is an arborescent structure built with the help of a conditioned Galton-Watson tree and random i.i.d. increments Y. In this paper, we show that if and , then the discrete snake converges weakly to the Brownian snake (this result was known under the hypothesis ). Moreover, if this condition fails, and the tails of Y are sufficiently regular, we show that the discrete snake converges weakly to an object that we name jumping snake. In both case, the limit of the occupation measure is shown to be the integrated super-Brownian excursion. The proofs rely on the convergence of the codings of discrete snake with the help of two processes, called tours.     

A central limit theorem for branching Brownian motion with random immigration

We establish a central limit theorem for a branching Brownian motion with random immigration under the annealed law,where the immigration is determined by another branching Brownian motion.The limit is a Gaussian random measure and the normalization is t3/4for d=3 and t1/2for d≥4,where in the critical dimension d=4 both the immigration and the branching Brownian motion itself make contributions to the covariance of the limit.     

Critical random graphs and the structure of a minimum spanning tree

We consider the complete graph on n vertices whose edges are weighted by independent and identically distributed edge weights and build the associated minimum weight spanning tree. We show that if the random weights are all distinct, then the expected diameter of such a tree is Θ(n^1/3). This settles a question of Frieze and Mc‐Diarmid (Random Struct Algorithm 10 (1997), 5–42). The proofs are based on a precise analysis of the behavior of random graphs around the critical point. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009