On the Asymptotic Probability of Forbidden Motifs on the Fringe of Recursive Trees

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.

KEYWORDS:

• analytic combinatorics
• asymptotic analysis
• forbidden patterns
• generating functions
• recursive trees

2000 AMS Subject Classification:

• 60C05
• 05C05

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.