A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees

Abstract

We study the conditions for families of subtrees to exist with high probability (whp) in a Galton-Walton tree of size $n$. We first give a Poisson approximation of fringe subtree counts, which yields the height of the maximal complete $r$-ary fringe subtree. Then we determine the maximal $K_n$ such that every tree of size at most $K_n$ appears as fringe subtree whp. Finally, we study non-fringe subtree counts and determine the height of the maximal complete $r$-ary non-fringe subtree.

40 pages, 7 figure

References in corpus (1)

• Limit Laws for Functions of Fringe trees for Binary Search Trees and Recursive Trees

Cited by in corpus (2)

• Inversions in split trees and conditional Galton--Watson trees
• The Horton-Strahler Number of Conditioned Galton-Watson Trees