Kingman's coalescent on a random graph

We introduce a generalization of Kingman's coalescent on $[n]$ that we call the Kingman coalescent on a graph $G = ([n],E)$. Specifically, we generalize a forest valued representation of the coalescent introduced in Addario-Berry and Eslava (2018). The difference between the Kingman coalescent on G and the normal Kingman coalescent on $[n]$ is that two trees T₁,T₂ with roots ρ₁,ρ₂ can merge if and only if \ρ₁,ρ₂\ ∈ E. When this process finishes (when there are no trees left that can merge anymore), we are left with a random spanning forest that we call a Kingman forest of G. In this article, we study the Kingman coalescent on Erdős-Rényi random graphs, Gn,p. We derive a relationship between the Kingman coalescent on Gn,p and uniform random recursive trees, which provides many answers concerning structural questions about the corresponding Kingman forests. We explore the heights of Kingman forests as well as the sizes of their trees as illustrative examples of how to use the connection. Our main results concern the number of trees, Cn,p, in a Kingman forest of Gn,p. For fixed p ∈ (0,1), we prove that Cn,p converges in distribution to an almost surely finite random variable as n → ∞. For $p = p(n)$ such that p → 0 and np → ∞ as n → ∞, we prove that Cn,p converges in probability to 2(1-p)/p.