Degree distribution in the lower levels of the uniform recursive tree

MaRDI QIDQ2898765zbMATH OpenFDO

Authors Tamás F. Móri, Ágnes Backhausz

Publication date 12 July 2012

Published in Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae. Sectio Computatorica (Search for Journal in Brave)

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

zbMATH Keywords

permutationPoisson distributionmethod of momentsdegree distributionrandom recursive tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Strong limit theorems (60F15) Combinatorial probability (60C05)

Abstract: In this note we consider the $k$th level of the uniform random recursive tree after $n$ steps, and prove that the proportion of nodes with degree greater than $tlogn$ converges to $(1-t{)}^k$ almost surely, as $noinfty$, for every $tin(0,1)$. In addition, we show that the number of degree $d$ nodes in the first level is asymptotically Poisson distributed with mean 1; moreover, they are asymptotically independent for $d=1,2,\mathrm{...}$.

Recommendations

• High degrees in recursive trees
• High degrees in random recursive trees
• scientific article; zbMATH DE number 426362
• Asymptotic degree distribution in random recursive trees
• Limit distribution for the maximum degree of a random recursive tree

Cited in

(7)

• scientific article; zbMATH DE number 426362 (Why is no real title available?)
• Levels of a scale-free tree
• A random graph of moderate density
• A functional limit theorem for the profile of random recursive trees
• Degree and component size distributions in the generalized uniform recursive tree
• Degree distributions in recursive trees with fitnesses
• The degree profile in some classes of random graphs that generalize recursive trees

This page was built for publication: Degree distribution in the lower levels of the uniform recursive tree

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