Fragmentation of random trees

We investigate the fragmentation of a random recursive tree by repeated removal of nodes, resulting in a forest of disjoint trees. The initial tree is generated by sequentially attaching new nodes to randomly chosen existing nodes until the tree contains $N$ nodes. As nodes are removed, one at a time, the tree dissolves into an ensemble of separate trees, namely a forest. We study the statistical properties of trees and nodes in this heterogeneous forest. In the limit $N \to \infty$, we find that the system is characterized by a single parameter: the fraction of remaining nodes $m$. We obtain analytically the size density $\phi_s$ of trees of size $s$, which has a power-law tail $\phi_s \sim s^{-\alpha}$, with exponent $\alpha=1+1/m$. Therefore, the tail becomes steeper as further nodes are removed, producing an unusual scaling exponent that increases continuously with time. Furthermore, we investigate the fragment size distribution in a growing tree, where nodes are added as well as removed, and find that the distribution for this case is much narrower.