Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation

DOI10.1214/11-PS188zbMath1244.60013arXiv1112.0510MaRDI QIDQ431520

Svante Janson

Publication date: 28 June 2012

Published in: Probability Surveys (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.0510

zbMATH Keywords

random trees; random forests; simply generated trees; Galton-Watson trees; balls in boxes; random allocations; size-biased Galton-Watson tree

Mathematics Subject Classification ID

60F05: Central limit and other weak theorems

05C05: Trees

60C05: Combinatorial probability

60J80: Branching processes (Galton-Watson, birth-and-death, etc.)

Related Items

Fixed points of 321-avoiding permutations, A probabilistic approach to block sizes in random maps, Simply Generated Unrooted Plane Trees, Unnamed Item, Random stable-type minimal factorizations of the n-cycle, Very fat geometric Galton-Watson trees, Differentiability of the speed of biased random walks on Galton-Watson trees, Speeding up non-Markovian first-passage percolation with a few extra edges, Graph limits of random graphs from a subset of connected k‐trees, A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees, THE ASYMPTOTIC DEGREE DISTRIBUTIONS OF RANDOM FAST GROWTH MODELS FOR TREELIKE NETWORKS, Asymptotics of Symmetric Compound Poisson Population Models, Simply Generated Non-Crossing Partitions, Inference for conditioned Galton-Watson trees from their Harris path, Trajectories in random minimal transposition factorizations, On the peel number and the leaf-height of Galton–Watson trees, Tree limits and limits of random trees, The distance profile of rooted and unrooted simply generated trees, The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses, Trees with exponential height dependent weight, Maximum degree in minor-closed classes of graphs, Stochastic ordering of infinite geometric Galton-Watson trees, Condensation and symmetry-breaking in the zero-range process with weak site disorder, Profiles of ordered trees with mutation and associated Riordan matrices, Spectral dimension of trees with a unique infinite spine, Generalized gamma approximation with rates for urns, walks and trees, Percolation on random triangulations and stable looptrees, Vertices with fixed outdegrees in large Galton-Watson trees, A decorated tree approach to random permutations in substitution-closed classes, Decomposable branching processes with a fixed extinction moment, Sesqui-type branching processes, Limits of the boundary of random planar maps, Random enriched trees with applications to random graphs, Critical multi-type Galton-Watson trees conditioned to be large, Uniform infinite half-planar quadrangulations with skewness, Non-fringe subtrees in conditioned Galton-Watson trees, On the shape of random Pólya structures, Heavy subtrees of Galton-Watson trees with an application to Apollonian networks, Most trees are short and fat, Central limit theorems for biased randomly trapped random walks on \(\mathbb{Z}\), Local convergence of large critical multi-type Galton-Watson trees and applications to random maps, Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees, Cost functionals for large (uniform and simply generated) random trees, A geometric representation of fragmentation processes on stable trees, On general subtrees of a conditioned Galton-Watson tree, Universal height and width bounds for random trees, The sum of powers of subtree sizes for conditioned Galton-Watson trees, Trees with power-like height dependent weight, Stable shredded spheres and causal random maps with large faces, Random generation and scaling limits of fixed genus factorizations into transpositions, Distinct fringe subtrees in random trees, Rerooting multi-type branching trees: the infinite spine case, Local convergence of critical random trees and continuous-state branching processes, Central limit theorems for additive functionals and fringe trees in tries, Short cycles in high genus unicellular maps, Infinite stable looptrees, Limits of random tree-like discrete structures, The speed of a biased random walk on a Galton-Watson tree is analytic, The boundary of random planar maps via looptrees, Universal limits of substitution-closed permutation classes, The Horton-Strahler number of conditioned Galton-Watson trees, Revisiting Shao and Sokal's \(B_2\) index of phylogenetic balance, Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\), A central limit theorem for almost local additive tree functionals, An analysis of budgeted parallel search on conditional Galton-Watson trees, Penalization of Galton-Watson processes, The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees, Limit theorems for conditioned non-generic Galton-Watson trees, Random walk on random infinite looptrees, Scaling limits of random planar maps with a unique large face, Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees, Conditioning Galton-Watson trees on large maximal outdegree, Escape regimes of biased random walks on Galton-Watson trees, \(k\)-cut on paths and some trees, Asymptotic properties of expansive Galton-Watson trees, Condensation and extremes for a fluctuating number of independent random variables, Cycles in random meander systems, The mesoscopic geometry of sparse random maps, Local convergence of random planar graphs, On degenerate sums of m-dependent variables, Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees, Conditioned multi-type Galton−Watson trees, Scaling limits for a family of unrooted trees, Condensation for random variables conditioned by the value of their sum

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Condensation in nongeneric trees
• Condensation in the Backgammon model
• Convergence of simple random walks on random discrete trees to Brownian motion on the continuum random tree
• The continuum random tree. I
• Asymptotic fringe distributions for general families of random trees
• Rounding of continuous random variables and oscillatory asymptotics
• Asymptotic number of forests from unrooted trees
• Random trees and applications
• Random walks on Galton-Watson trees with infinite variance offspring distribution conditioned to survive
• Extremes and related properties of random sequences and processes
• Arbres et processus de Galton-Watson. (Trees and Galton-Watson processes)
• Subdiffusive behavior of random walk on a random cluster
• Two conditional limit theorems with applications
• Tree-valued Markov chains derived from Galton-Watson processes
• Glassy mean-field dynamics of the backgammon model
• A limit theorem for the contour process of conditioned Galton-Watson trees
• Logarithmic combinatorial structures: A probabilistic approach
• A random walk approach to Galton-Watson trees
• On the Lambert \(w\) function
• Conceptual proofs of \(L\log L\) criteria for mean behavior of branching processes
• Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
• The continuum random tree. III
• The spectral dimension of generic trees
• Random real trees
• Local limit of labeled trees and expected volume growth in a random quadrangulation
• Random walk on the incipient infinite cluster on trees
• On the maximum degree in a random tree
• Formal power series and the total progeny in a branching process
• Faster algorithms for Frobenius numbers
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• The number of trees
• Moment convergence in conditional limit theorems
• Asymptotic distribution for the cost of linear probing hashing
• On the maximum size of a tree in a random unlabelled unrooted forest
• Random trees with superexponential branching weights
• Phase transition for Parking blocks, Brownian excursion and coalescence
• The shape of large Galton-Watson trees with possibly infinite variance
• Random cutting and records in deterministic and random trees
• Random Trees
• Scaling limits for simple random walks on random ordered graph trees
• Multitype Bienaymé–Galton–Watson processes escaping extinction
• On the asymptotic joint distribution of height and width in random trees
• Ballots, queues and random graphs
• A Generalization of the Ballot Problem and its Application in the Theory of Queues
• Left-Continuous Random Walk and the Lagrange Expansion
• The Galton-Watson process conditioned on the total progeny
• On the Altitude of Nodes in Random Trees
• A unified approach to limit theorems for urn models
• The maximum degree in a random tree and related problems
• Components of Random Forests
• A remark on the Galton-Watson forests
• Probability: A Graduate Course
• On the number of vertices with a given degree in a Galton-Watson tree
• Cycles and Unicyclic Components in Random Graphs
• Limit distributions of the maximum size of a tree in a random recursive forest
• On some conditions for absence of a giant component in the generalised allocation scheme
• Emergence of a giant component in a random permutation with given number of cycles
• The limit distributions of the maximum size of a tree in a random forest
• Elementary new proofs of classical limit theorems for Galton–Watson processes
• The Random-Cluster Model
• A derivation of the Borel distribution
• The total progeny in a branching process and a related random walk
• The Multiplicative Process