Name: Random Recursive Trees and Preferential Attachment Trees are Random Split Trees
Creator: Svante Janson
Keywords: 60C05, 05C05, 05C80, 68P05, Probability (math.PR), FOS: Mathematics, 1. No poverty, Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, 01 natural sciences, Mathematics - Probability, 6. Clean water

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 21 May 2018Embargo end date: 01 Jan 2017 English Publisher:Cambridge University Press (CUP)Journal:Combinatorics, Probability and Computing, volume 28, pages 81-99 (issn: 0963-5483, eissn: 1469-2163,

Authors: Svante Janson;

doi: 10.1017/s0963548318000226 , 10.48550/arxiv.1706.05487

arXiv: http://arxiv.org/abs/1706.05487

Random Recursive Trees and Preferential Attachment Trees are Random Split Trees

- Summary
- Subjects
- Metrics

Abstract

We consider linear preferential attachment trees, and show that they can be regarded as random split trees in the sense of Devroye (1999), although with infinite potential branching. In particular, this applies to the random recursive tree and the standard preferential attachment tree. An application is given to the sum over all pairs of nodes of the common number of ancestors.

Related Organizations

Uppsala University
Sweden

Keywords

60C05, 05C05, 05C80, 68P05, Probability (math.PR), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Probability

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	12
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%