Asymptotic results on Hoppe trees and their variations

DOI10.1017/JPR.2020.12MaRDI QIDQ3299442zbMATH OpenOpenAlexFDO

Authors Ella Hiesmayr, Ümit Işlak

Publication date 22 July 2020

Published in Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

couplingrandom permutationsEwens sampling formulauniform recursive treesHoppe treesrandom tree statistics

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A uniform recursive tree on $n$ vertices is a random tree where each possible $(n-1)!$ labeled recursive rooted tree is selected with equal probability. In this paper we introduce and study weighted trees, a non-uniform recursive tree model departing from the recently introduced Hoppe trees. This class generalizes both uniform recursive trees and Hoppe trees. The generalization provides diversity among the nodes, making the model more flexible for applications. We also analyze the number of leaves, the height, the depth, the number of branches, and the size of the largest branch in these weighted trees.

Recommendations

• Asymptotic analysis of Hoppe trees
• Asymptotics of trees with a prescribed degree sequence and applications
• The asymptotic behaviour of the number of trees in certain classes
• scientific article; zbMATH DE number 2232270
• The asymptotic behavior of the Estrada index for trees
• Several asymptotic bounds on the Balaban indices of trees
• Asymptotic sharpness of bounds on hypertrees
• scientific article; zbMATH DE number 714500
• On a conjecture of Graham and Häggkvist for random trees
• scientific article; zbMATH DE number 1222160

Cites work

• scientific article; zbMATH DE number 4053643 (Why is no real title available?)
• scientific article; zbMATH DE number 2018401 (Why is no real title available?)
• scientific article; zbMATH DE number 1409903 (Why is no real title available?)
• A Probability Model of a Pyramid Scheme
• Asymptotic analysis of Hoppe trees
• Branching structure of uniform recursive trees
• Depth properties of scaled attachment random recursive trees
• Fires on large recursive trees
• Fundamentals of Stein's method
• Logarithmic combinatorial structures: A probabilistic approach
• Note on the heights of random recursive trees and random m‐ary search trees
• On leaf related statistics in recursive tree models
• On the number of terminal vertices in certain random trees with an application to stemma construction in philology
• Random Trees

Cited in

(10)

• Geometry of weighted recursive and affine preferential attachment trees
• Degree distributions in recursive trees with fitnesses
• Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights
• Arbitrarily large jumps of the Golovach function for trees
• The maximal degree in random recursive graphs with random weights
• Height of weighted recursive trees with sub-polynomially growing total weight
• On leaf related statistics in recursive tree models
• Correction terms for the height of weighted recursive trees
• The height of depth-weighted random recursive trees
• Asymptotic analysis of Hoppe trees

This page was built for publication: Asymptotic results on Hoppe trees and their variations

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