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

heightwidthrandom treessimply generated treesGalton-Watson trees

Mathematics Subject Classification ID

Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items (30)

Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees ⋮ The distance profile of rooted and unrooted simply generated trees ⋮ Tail bounds for the height and width of a random tree with a given degree sequence ⋮ Random enriched trees with applications to random graphs ⋮ Scaling limits of random Pólya trees ⋮ Scaling limit for the ant in a simple high-dimensional labyrinth ⋮ Finding paths in sparse random graphs requires many queries ⋮ A branching process approach to level‐k phylogenetic networks ⋮ On breadth‐first constructions of scaling limits of random graphs and random unicellular maps ⋮ Slightly supercritical percolation on non‐amenable graphs I: The distribution of finite clusters ⋮ Limits of random tree-like discrete structures ⋮ The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses ⋮ A branching process with coalescence to model random phylogenetic networks ⋮ Growing random graphs with a preferential attachment structure ⋮ Large unicellular maps in high genus ⋮ Asymptotic behaviour of the first positions of uniform parking functions ⋮ Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics ⋮ Automatic choice of the threshold of a grain filter via Galton-Watson trees: application to granite cracks detection ⋮ Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation ⋮ Heavy subtrees of Galton-Watson trees with an application to Apollonian networks ⋮ Most trees are short and fat ⋮ Asymptotics of trees with a prescribed degree sequence and applications ⋮ 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 ⋮ Асимптотические свойства числа инверсий в случайном лесе ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ Simply Generated Unrooted Plane Trees ⋮ Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees ⋮ Graph limits of random graphs from a subset of connected k‐trees ⋮ Universal height and width bounds for random trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees