Depth of vertices with high degree in random recursive trees

MaRDI QIDQ5093993zbMATH OpenFDO

Authors Laura Eslava

Publication date 2 August 2022

Full work available at URL https://arxiv.org/abs/1611.07466, https://alea.impa.br/articles/v19/19-33.pdf

zbMATH Keywords

extreme valuesrandom recursive treesKingman's coalescentmaximum degreesnear-maximum degrees

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(8)

• High degrees in random recursive trees
• Depth of nodes in random recursive k-ary trees
• scientific article; zbMATH DE number 5081212 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 3952789 (Why is no real title available?)

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)