Degree distribution in the lower levels of the uniform recursive tree

zbMATH Open1249.05355arXiv1112.1250MaRDI QIDQ2898765FDOQ2898765

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)

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{...}$.

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

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

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)

Cited In (7)

• Degree and component size distributions in the generalized uniform recursive tree
• A functional limit theorem for the profile of random recursive trees
• Degree distributions in recursive trees with fitnesses
• The degree profile in some classes of random graphs that generalize recursive trees
• Title not available (Why is that?)
• A random graph of moderate density
• Levels of a scale-free tree

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)