On the Asymptotic Probability of Forbidden Motifs on the Fringe of Recursive Trees. Issue 3 (2nd July 2016)

• Record Type: Journal Article
• Authors: Gopaladesikan, Mohan; Wagner, Stephan; Ward, Mark Daniel
• Is Part Of: Experimental mathematics. Volume 25:Issue 3(2016)
• Page Start: 237
• Page End: 245
• Publication Date: 2016-07-02
• Subjects: analytic combinatorics -- asymptotic analysis -- forbidden patterns -- generating functions -- recursive trees; 60C05 -- 05C05; Mathematics -- Periodicals; Mathematics -- Research -- Periodicals; 510.724
• DOI: 10.1080/10586458.2015.1065525
• Languages: English
• ISSNs: 1058-6458

Abstract

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.