High degrees in random recursive trees

DOI10.1002/RSA.20753MaRDI QIDQ4584910zbMATH OpenOpenAlexFDO

Authors Louigi Addario-Berry, Laura Eslava

Publication date 5 September 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

degree distributionsextreme valuesKingman's coalescentrandom recursive trees

Mathematics Subject Classification ID

Trees (05C05) Vertex degrees (05C07) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Abstract: For $nge1$, let $T_n$ be a random recursive tree on the vertex set $[n]=1,ldots,n$. Let $mathrm{deg}_{T_n}(v)$ be the degree of vertex $v$ in $T_n$, that is, the number of children of $v$ in $T_n$. Devroye and Lu showed that the maximum degree $Delt{a}_n$ of $T_n$ satisfies $Delt{a}_n/lfloorlo{g}_{2}nflooro1$ almost surely; Goh and Schmutz showed distributional convergence of $Delt{a}_n-lfloorlo{g}_{2}nfloor$ along suitable subsequences. In this work we show how a version of Kingman's coalescent can be used to access much finer properties of the degree distribution in $T_n$. For any $iinmathbbZ$, let $X_i^{(n)}=|vin[n]:mathrm{deg}_{T_n}(v)=lfloorlognfloor+i|$. Also, let $mathcalP$ be a Poisson point process on $mathbbR$ with rate function $lambda(x)=2^{-x}cdotln2$. We show that, up to lattice effects, the vectors $(X_i^{(n)},,iinmathbbZ)$ converge weakly in distribution to $(mathcalP[i,i+1),,iinmathbbZ)$. We also prove asymptotic normality of $X_i^{(n)}$ when $i=i(n)o-infty$ slowly, and obtain precise asymptotics for $mathbbP(Delt{a}_n-lo{g}_{2}n>i)$ when $i(n)oinfty$ and $i(n)/logn$ is not too large. Our results recover and extends the previous results on maximal and near-maximal degrees in random recursive trees.

Recommendations

• Depth of vertices with high degree in random recursive trees
• High degrees in recursive trees
• scientific article; zbMATH DE number 17686
• scientific article; zbMATH DE number 426362
• Asymptotic degree distribution in random recursive trees
• The maximum degree in a random tree and related problems
• scientific article; zbMATH DE number 1222137
• Nodes of large degree in random trees and forests

Cited in

(21)

• Persistence of hubs in growing random networks
• On joint properties of vertices with a given degree or label in the random recursive tree
• Profile of random exponential recursive trees
• Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights
• Degree distribution in the lower levels of the uniform recursive tree
• Depth properties of scaled attachment random recursive trees
• High degrees in recursive trees
• scientific article; zbMATH DE number 3952789 (Why is no real title available?)
• scientific article; zbMATH DE number 17686 (Why is no real title available?)
• Limit distribution of the degrees in scaled attachment random recursive trees
• Asymptotic degree distribution in random recursive trees
• The strong convergence of maximal degrees in uniform random recursive trees and dags
• A non-increasing tree growth process for recursive trees and applications
• Depth of vertices with high degree in random recursive trees
• Tree evolution processes for bucket increasing trees
• The maximal degree in random recursive graphs with random weights
• Uniform temporal trees
• Uniform attachment with freezing: scaling limits
• Uniform attachment with freezing
• Quenched worst-case scenario for root deletion in targeted cutting of random recursive trees
• The location of high-degree vertices in weighted recursive graphs with bounded random weights

This page was built for publication: High degrees in random recursive trees

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