Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees

DOI10.1214/12-AOP758zbMath1278.60128arXiv1011.4121WikidataQ101203337 ScholiaQ101203337MaRDI QIDQ1951700

Svante Janson, Louigi Addario-Berry, Luc P. Devroye

Publication date: 24 May 2013

Published in: The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

height; width; random trees; simply generated trees; Galton-Watson trees

Mathematics Subject Classification ID

60C05: Combinatorial probability

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

Related Items

Simply Generated Unrooted Plane Trees, Growing random graphs with a preferential attachment structure, Speeding up non-Markovian first-passage percolation with a few extra edges, Inversions in Split Trees and Conditional Galton–Watson Trees, Graph limits of random graphs from a subset of connected k‐trees, Asymptotics of trees with a prescribed degree sequence and applications, Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Large unicellular maps in high genus, Random enriched trees with applications to random graphs, Automatic choice of the threshold of a grain filter via Galton-Watson trees: application to granite cracks detection, Heavy subtrees of Galton-Watson trees with an application to Apollonian networks, Most trees are short and fat, Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees, Universal height and width bounds for random trees, Limits of random tree-like discrete structures, Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics, Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees, Scaling limits of random Pólya trees, Scaling limit for the ant in a simple high-dimensional labyrinth, Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees, Finding paths in sparse random graphs requires many queries, Tail bounds for the height and width of a random tree with a given degree sequence, Асимптотические свойства числа инверсий в случайном лесе

Cites Work

• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Random trees and applications
• Subdiffusive behavior of random walk on a random cluster
• The average height of binary trees and other simple trees
• Tree-valued Markov chains derived from Galton-Watson processes
• A limit theorem for the contour process of conditioned Galton-Watson trees
• Probabilistic and fractal aspects of Lévy trees
• Conceptual proofs of \(L\log L\) criteria for mean behavior of branching processes
• Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursions
• SOME REMARKS ABOUT THE I ENTITY IN LAW FOR THE BESSEL BRIDGE
• Random cutting and records in deterministic and random trees
• Random Trees
• On the asymptotic joint distribution of height and width in random trees
• The Galton-Watson process conditioned on the total progeny
• Maxima in Brownian excursions
• The distribution of the maximum Brownian excursion
• On the Altitude of Nodes in Random Trees
• The Distribution of Heights of Binary Trees and Other Simple Trees
• On the profile of random trees
• Probability Inequalities for Sums of Bounded Random Variables
• On the height of trees
• The total progeny in a branching process and a related random walk
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item