Asymptotics of trees with a prescribed degree sequence and applications

DOI10.1002/rsa.20463zbMath1290.05059arXiv1110.5203OpenAlexW2114349008MaRDI QIDQ5415593

Nicolas Broutin, Jean-François Marckert

Publication date: 13 May 2014

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Brownian excursioncoalescenceinvariance principlecontinuum random treereal tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07)

Related Items

Random tree-weighted graphs ⋮ Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees ⋮ On scaling limits of random trees and maps with a prescribed degree sequence ⋮ Scaling limits of slim and fat trees ⋮ Models of random subtrees of a graph ⋮ Large deviation local limit theorems and limits of biconditioned planar maps ⋮ The boundary of random planar maps via looptrees ⋮ Invariance principles for Galton-Watson trees conditioned on the number of leaves ⋮ Dini derivatives and regularity for exchangeable increment processes ⋮ Small trees in supercritical random forests ⋮ Invariance principles for random walks in random environment on trees ⋮ Geometry of the minimal spanning tree of a random 3-regular graph ⋮ Self-similar real trees defined as fixed points and their geometric properties ⋮ Graph limits of random graphs from a subset of connected k‐trees ⋮ Scaling limit of random forests with prescribed degree sequences ⋮ Universality for random surfaces in unconstrained genus ⋮ Universal height and width bounds for random trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Invariance principles for Galton-Watson trees conditioned on the number of leaves
• Critical random graphs: limiting constructions and distributional properties
• Novel scaling limits for critical inhomogeneous random graphs
• The continuum random tree. I
• Limit of normalized quadrangulations: the Brownian map
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• Coalescent random forests
• The standard additive coalescent
• The uniform random tree in a Brownian excursion
• Brownian excursions, critical random graphs and the multiplicative coalescent
• The depth first processes of Galton-Watson trees converge to the same Brownian excursion
• A fragmentation process connected to Brownian motion
• A random walk approach to Galton-Watson trees
• 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
• Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
• The continuum random tree. III
• The continuum limit of critical random graphs
• Random real trees
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Convergence of discrete snakes
• A problem of arrangements
• The Phase Transition in the Configuration Model
• Phase transition for Parking blocks, Brownian excursion and coalescence
• Tail bounds for the height and width of a random tree with a given degree sequence
• Recent progress in coalescent theory
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• A critical point for random graphs with a given degree sequence
• Random Fragmentation and Coagulation Processes
• Asymptotics in Knuth's parking problem for caravans