Scaling limit of random forests with prescribed degree sequences

DOI10.3150/18-BEJ1058MaRDI QIDQ2325329zbMATH OpenFDO

Authors Tao Lei

Publication date 25 September 2019

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.02064, https://projecteuclid.org/euclid.bj/1568362031

zbMATH Keywords

first passage bridgeGromov-Hausdorff-Prokhorov distancerandom forests

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Brownian motion (60J65) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: In this paper, we consider the random plane forest uniformly drawn from all possible plane forests with a given degree sequence. Under suitable conditions on the degree sequences, we consider the limit of a sequence of such forests with the number of vertices tends to infinity in terms of Gromov-Hausdorff-Prokhorov topology. This work falls into the general framework of showing convergence of random combinatorial structures to certain Gromov-Hausdorff scaling limits, described in terms of the Brownian Continuum Random Tree, pioneered by the work of Aldous. In fact we identify the limiting random object as a sequence of random real trees encoded by excursions of some first passage bridges reflected at minimum. We establish such convergence by studying the associated Lukasiewicz walk of the degree sequences. In particular, our work is closely related to and uses the results from the recent work of Broutin and Marckert on scaling limit of random trees with prescribed degree sequences, and the work of Addario-Berry on tail bounds of the height of a random tree with prescribed degree sequence.

Review text

The main result of this paper is the proof of the convergence of the large uniformly random forests with given degree sequence to the distribution to the forests coded by Brownian first passage bridge, with respect to the Gromov-Hausdorff-Prokhorov topology.

Recommendations

• Small trees in supercritical random forests
• Critical random forests
• Limits of random trees. II
• Limit distributions of the number of trees of a given size in a random forest
• Asymptotics of trees with a prescribed degree sequence and applications

Cites work

• A course in metric geometry
• A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotics of trees with a prescribed degree sequence and applications
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Critical random graphs: limiting constructions and distributional properties
• scientific article; zbMATH DE number 3896009 (Why is no real title available?)
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 503432 (Why is no real title available?)
• scientific article; zbMATH DE number 1859371 (Why is no real title available?)
• Invariance principles for spatial multitype Galton-Watson trees
• Path transformations of first passage bridges
• Phase transition for Parking blocks, Brownian excursion and coalescence
• Random trees and applications
• Scaling limit of random planar quadrangulations with a boundary
• Scaling limits for random quadrangulations of positive genus
• Scaling limits of random planar maps with a unique large face
• Tail bounds for the height and width of a random tree with a given degree sequence
• The asymptotic number of labeled graphs with given degree sequences
• The continuum random tree. I
• The continuum random tree. III
• The CRT is the scaling limit of unordered binary trees
• The standard additive coalescent

Cited in

(4)

• Small trees in supercritical random forests
• Asymptotics of trees with a prescribed degree sequence and applications
• Scaling limits of slim and fat trees
• Scaling limits of random looptrees and bipartite plane maps with prescribed large faces

This page was built for publication: Scaling limit of random forests with prescribed degree sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2325329)