Combinatorics, Probability and Computing

Table of Contents - 1992 - Volume 1, Issue 01  

Research Article

Components of Random Forests

Tomasz Łuczaka1 and Boris Pittela2

a1 Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland.

a2 Department of Mathematics, Ohio State University, Columbus, Ohio 43210, USA.

Abstract

A forest xs2131(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 xs2131(n, M). The similarity to the random graph is far from being complete. For instance, in the supercritical phase, the giant tree in xs2131(n, M) grows roughly two times slower than the largest component of G(n, M) and the second largest tree in xs2131(n, M) is of the order n⅔ for every M = n/2 +s, provided that s3n−2 → ∞ and s = o(n), while its counterpart in G(n, M) is of the order n2s−2 log(s3n−2) xs226A n⅔.

(Received October 04 1991)

(Revised November 19 1991)