Asymptotic results on Hoppe trees and their variations

DOI10.1017/JPR.2020.12zbMATH Open1444.05041arXiv1712.03572OpenAlexW3042414389MaRDI QIDQ3299442FDOQ3299442

Authors: Ella Hiesmayr, Ümit Işlak 

Publication date: 22 July 2020

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

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.

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

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

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)

Cites Work

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

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
• The maximal degree in random recursive graphs with random weights
• Height of weighted recursive trees with sub-polynomially growing total weight
• Arbitrarily large jumps of the Golovach function for trees
• 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)