Critical random forests

Journal article

Let F(N, m) denote a random forest on a set of N vertices, chosen uniformly from all forests with m edges. Let F(N, p) denote the forest obtained by conditioning the Erd˝os-R´enyi graph G(N, p) to be acyclic. We describe scaling limits for the largest components of F(N, p) and F(N, m), in the critical window p = N −1 + O(N −4/3 ) or m = N/2 + O(N2/3 ). Aldous (1997) described a scaling limit for the largest components of G(N, p) within the critical window in terms of the excursion lengths of a reflected Brownian motion with time-dependent drift. Our scaling limit for critical random forests is of a similar nature, but now based on a reflected diffusion whose drift depends on space as well as on time.

Authors: Martin, JB; Yeo, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Instituto Nacional de Matemática Pura e Aplicada
• Journal: Latin American Journal of Probability and Mathematical Statistics
• Volume: 15
• Issue: 2
• Pages: 913–960
• Publication date: 2018-08-08
• Acceptance date: 2018-07-08
• DOI: 10.30757/alea.v15-35
• ISSN: 1980-0436
• Language: English
• Keywords: random forest; critical window; exploration process; random graph