Components of Random Forests

Source abstract

A forest ℱ( n, M ) chosen uniformly from the family of all labelled unrooted forests with n vertices and M edges is studied. We show that, like the Érdős-Rényi random graph G ( n, M ), the random forest exhibits three modes of asymptotic behaviour: subcritical, nearcritical and supercritical, with the phase transition at the point M = n /2. For each of the phases, we determine the limit distribution of the size of the k -th largest component of ℱ( n, M ). The similarity to the random graph is far from being complete. For instance, in the supercritical phase, the giant tree in ℱ( n, M ) grows roughly two times slower than the largest component of G ( n, M ) and the second largest tree in ℱ( n, M ) is of the order n ⅔ for every M = n /2 + s , provided that s 3 n −2 → ∞ and s = o(n) , while its counterpart in G ( n, M ) is of the order n 2 s −2 log( s 3 n −2 ) ≪ n ⅔ .