Critical random forests

2017/09/21 by James Martin, Martin, James, Dominic Yeo +1 · 1 citation
Mathematics · #FOS: Mathematics #Probability (math.PR) #math.PR

paper · pdf · doi:10.48550/arxiv.1709.07514

arxiv created 2018/07/02 · arxiv updated 2018/07/04

Abstract

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 Erdos-Renyi 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(N^2/3). Aldous 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.

Cited by

• Sampling biased spanning forests through marked vertices

Related

• The scaling limit of a critical random directed graph
• Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős-Rényi random graph
• Scaling limits of random graphs
• Critical random graphs: limiting constructions and distributional properties
• The scaling limit of the minimum spanning tree of the complete graph