A random forest process with a variable number of giant components in the threshold window

Given a graph G, and an ordering π of its vertices, a permutation forest F(G,π) is a spanning forest of G whose components are obtained as follows. For each vertex v, connect v to its first neighbour w in G that appears after v in the ordering π. If we regard this edge (v,w) as directed forward, from v to w, then each vertex has at most one forward edge, and the components of F(G,π) are arborescences. The roots of the components formed by this process are those vertices of G with no forward edge in the ordering π. This paper shows that the permutation forests of the random graphs G_n,p have a threshold for the emergence of a linear size component around p=1/n. In contrast to the w.h.p. emergence of a unique giant in G_n,p, the permutation forest process has the unusual property that, with positive probability, a number of linear size components occur within the threshold window.