On the Asymptotic Probability of Forbidden Motifs on the Fringe of Recursive Trees. Issue 3 (2nd July 2016) - Gopaladesikan, Mohan; Wagner, Stephan; Ward, Mark Daniel
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.