Abstract
We use analytic methods to study the probability of a family of motifs not occurring on the fringe of a random recursive tree. We obtain an asymptotic formula for this probability by means of singularity analysis. Two regimes are treated in particular: the case that a fixed proportion of motifs of size γ is forbidden, and the case that a fixed number of motifs of size γ is forbidden. In both cases, we observe phase transitions as the size of the random tree and the size of the motif tend to infinity. The required asymptotic expansions of the dominant singularities were first found by computer experiments and only later made rigorous.
Acknowledgments
The authors thank Dr. Hosam Mahmoud for guidance and suggestions during the course of this investigation, as well as for his hospitality during M.G.’s and M.D.W.’s extended visit to The George Washington University in 2013–14.