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

DOI10.1214/11-PS188zbMath1244.60013arXiv1112.0510OpenAlexW2120547819MaRDI 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 treesrandom forestssimply generated treesGalton-Watson treesballs in boxesrandom allocationssize-biased Galton-Watson tree

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Trees (05C05) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items (96)

Maximum degree in minor-closed classes of graphs ⋮ Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees ⋮ Sesqui-type branching processes ⋮ 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 ⋮ Limits of the boundary of random planar maps ⋮ 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 ⋮ Asymptotic properties of expansive Galton-Watson trees ⋮ 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 ⋮ Random stable-type minimal factorizations of the n-cycle ⋮ Short cycles in high genus unicellular 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 ⋮ Condensation and extremes for a fluctuating number of independent random variables ⋮ Cycles in random meander systems ⋮ Non-fringe subtrees in conditioned Galton-Watson trees ⋮ Conditioning Galton-Watson trees on large maximal outdegree ⋮ Escape regimes of biased random walks on Galton-Watson trees ⋮ Infinite stable looptrees ⋮ The mesoscopic geometry of sparse random maps ⋮ Exact-Size Sampling of Enriched Trees in Linear Time ⋮ Unnamed Item ⋮ Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels ⋮ Sharpness of the phase transition for parking on random trees ⋮ Conditioned multi-type Galton−Watson trees ⋮ Scaling limits of slim and fat trees ⋮ Limits of random tree-like discrete structures ⋮ \(k\)-cut on paths and some trees ⋮ The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses ⋮ A branching process with coalescence to model random phylogenetic networks ⋮ A phase transition in block-weighted random maps ⋮ 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 ⋮ Trees with exponential height dependent weight ⋮ Decomposable branching processes with a fixed extinction moment ⋮ Decorated stable trees ⋮ Parking on Cayley trees and frozen Erdős-Rényi ⋮ Models of random subtrees of a graph ⋮ Large deviation local limit theorems and limits of biconditioned planar maps ⋮ Asymptotic behaviour of the first positions of uniform parking functions ⋮ On the shape of random Pólya structures ⋮ On random trees and forests ⋮ The speed of a biased random walk on a Galton-Watson tree is analytic ⋮ Asymptotics of Symmetric Compound Poisson Population Models ⋮ Local convergence of random planar graphs ⋮ The boundary of random planar maps via looptrees ⋮ Simply Generated Non-Crossing Partitions ⋮ Spectral dimension of trees with a unique infinite spine ⋮ Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees ⋮ Universal limits of substitution-closed permutation classes ⋮ Heavy subtrees of Galton-Watson trees with an application to Apollonian networks ⋮ Very fat geometric Galton-Watson trees ⋮ Most trees are short and fat ⋮ Central limit theorems for biased randomly trapped random walks on \(\mathbb{Z}\) ⋮ Condensation for random variables conditioned by the value of their sum ⋮ Local convergence of large critical multi-type Galton-Watson trees and applications to random maps ⋮ Fixed points of 321-avoiding permutations ⋮ The Horton-Strahler number of conditioned Galton-Watson trees ⋮ Cost functionals for large (uniform and simply generated) random trees ⋮ Revisiting Shao and Sokal's \(B_2\) index of phylogenetic balance ⋮ Differentiability of the speed of biased random walks on Galton-Watson trees ⋮ On degenerate sums of m-dependent variables ⋮ Generalized gamma approximation with rates for urns, walks and trees ⋮ 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 ⋮ Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees ⋮ Speeding up non-Markovian first-passage percolation with a few extra edges ⋮ A probabilistic approach to block sizes in random maps ⋮ Percolation on random triangulations and stable looptrees ⋮ A geometric representation of fragmentation processes on stable trees ⋮ An analysis of budgeted parallel search on conditional Galton-Watson trees ⋮ Penalization of Galton-Watson processes ⋮ Simply Generated Unrooted Plane Trees ⋮ On general subtrees of a conditioned Galton-Watson tree ⋮ Inference for conditioned Galton-Watson trees from their Harris path ⋮ Trajectories in random minimal transposition factorizations ⋮ Graph limits of random graphs from a subset of connected k‐trees ⋮ The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees ⋮ Scaling limits for a family of unrooted trees ⋮ Vertices with fixed outdegrees in large Galton-Watson trees ⋮ A decorated tree approach to random permutations in substitution-closed classes ⋮ 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 ⋮ Limit theorems for conditioned non-generic Galton-Watson trees ⋮ Distinct fringe subtrees in random trees ⋮ Random walk on random infinite looptrees ⋮ Scaling limits of random planar maps with a unique large face

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

This page was built for publication: Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation