Depth of vertices with high degree in random recursive trees

2016/11/22 by Eslava, Laura · 1 citation
#05C80 #60C05 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1611.07466

Abstract

Let T_n be a random recursive tree with n nodes. List vertices of T_n in decreasing order of degree as v¹,…,vⁿ, and write dⁱ and hⁱ for the degree of vⁱ and the distance of vⁱ from the root, respectively. We prove that, as n → ∞ along suitable subsequences, (dⁱ - \lfloor log₂ n \rfloor, (hⁱ - μln n)/(√(σ²ln n))) → ((P_i,i ≥ 1),(N_i,i ≥ 1)) , where μ=1-(log₂ e)/2, σ²=1-(log₂ e)/4, (P_i,i ≥ 1) is a Poisson point process on ℤ and (N_i,i ≥ 1) is a vector of independent standard Gaussians. We additionally establish joint normality for the depths of uniformly random vertices in T_n, which extends results for the case of a single random vertex. The joint limit holds even if the random vertices are conditioned to have large degree, provided the normalizing constants are adjusted accordingly; however, both the mean and variance of the conditinal depths remain of orden ln n. Our results are based on a simple relationship between random recursive trees and Kingman's n-coalescent; a utility that seems to have been largely overlooked.

Cited by

• Kingman's coalescent on a random graph

Related

• On joint properties of vertices with a given degree or label in the random recursive tree
• Degree distribution in the lower levels of the uniform recursive tree
• Large degree vertices in random directed acyclic graphs
• Targeted cutting of random recursive trees
• On the tree-depth of Random Graphs