Depth of vertices with high degree in random recursive trees

zbMATH Open1492.60020arXiv1611.07466MaRDI QIDQ5093993FDOQ5093993

Authors: Laura Eslava 

Publication date: 2 August 2022

Abstract: Let $T_n$ be a random recursive tree with $n$ nodes. List vertices of $T_n$ in decreasing order of degree as $v^1,ldots,v^n$, and write $d^i$ and $h^i$ for the degree of $v^i$ and the distance of $v^i$ from the root, respectively. We prove that, as $noinfty$ along suitable subsequences, [ �igg(d^i - lfloor log_2 n floor, frac{h^i - muln n}{sqrt{sigma^2ln n}}�igg) o ((P_i,i ge 1),(N_i,i ge 1)), , ] where $mu=1-(lo{g}_{2}e)/2$, $sigm{a}^2=1-(lo{g}_{2}e)/4$, $(P_i,ige1)$ is a Poisson point process on $mathbbZ$ and $(N_i,ige1)$ 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 $lnn$. 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.

Full work available at URL: https://arxiv.org/abs/1611.07466

Recommendations

• High degrees in random recursive trees
• On joint properties of vertices with a given degree or label in the random recursive tree
• High degrees in recursive trees
• scientific article; zbMATH DE number 17686
• Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees

zbMATH Keywords

extreme valuesrandom recursive treesKingman's coalescentmaximum degreesnear-maximum degrees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Cites Work

• An Introduction to the Theory of Point Processes
• Title not available (Why is that?)
• Concentration inequalities. A nonasymptotic theory of independence
• Title not available (Why is that?)
• Random Trees
• The Maximum Degree of the Barabási–Albert Random Tree
• Recent progress in coalescent theory.
• Limit distribution for the maximum degree of a random recursive tree
• Distribution of nodes of a tree by degree
• Note on the heights of random recursive trees and random m‐ary search trees
• The strong convergence of maximal degrees in uniform random recursive trees and dags
• Limiting Distributions for Path Lengths in Recursive Trees
• Applications of the theory of records in the study of random trees
• Persistence of hubs in growing random networks
• High degrees in random recursive trees
• A non-increasing tree growth process for recursive trees and applications
• Partition functions of discrete coalescents: from Cayley's formula to Frieze's \(\zeta (3)\) limit theorem

Cited In (8)

• High degrees in random recursive trees
• Depth of nodes in random recursive \(k\)-ary trees
• Title not available (Why is that?)
• Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights
• High degrees in recursive trees
• Depths in random recursive metric spaces
• On joint properties of vertices with a given degree or label in the random recursive tree
• Title not available (Why is that?)

This page was built for publication: Depth of vertices with high degree in random recursive trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5093993)