Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees

0504147 - ÚI 2020 US eng J - Journal Article
Holmgren, C. - Janson, S. - Šileikis, Matas
Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees.
Electronic Journal of Combinatorics. Roč. 24, č. 2 (2017), č. článku P2.51. ISSN 1077-8926. E-ISSN 1077-8926
Keywords : asymptotic joint normality * random recursive trees * branching-processes * theorems * size * nodes * space * Random trees * Fringe trees * Normal limit laws * Polya urns * m-ary search trees * Preferential attachment trees * Protected nodes
Impact factor: 0.762, year: 2017

We study fringe subtrees of random m-ary search trees and of preferential attachment trees, by putting them in the context of generalised Polya urns. In particular we show that for the random m-ary search trees with m <= 26 and for the linear preferential attachment trees, the number of fringe subtrees that are isomorphic to an arbitrary fixed tree T converges to a normal distribution; more generally, we also prove multivariate normal distribution results for random vectors of such numbers for different fringe subtrees. Furthermore, we show that the number of protected nodes in random m-ary search trees for m <= 26 has asymptotically a normal distribution.
Permanent Link: http://hdl.handle.net/11104/0295844