Partial orders and monotonicity of logarithmic depth and height in preferential attachment trees
Abstract
We study preferential attachment trees with general attachment rules. A natural intuition is that rewarding high-degree vertices more strongly should make the tree shallower. We test this intuition for the logarithmic growth constants of insertion depth and tree height. We show by an explicit counterexample that growth-ratio dominance alone does not guarantee either monotonicity. We identify additional tail-order conditions, arising from the branching-process representation of the tree, under which both expected comparisons hold.
Fields of Study & Subjects
Complex Network Analysis Techniques
Stochastic processes and statistical mechanics
Limits and Structures in Graph Theory
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 16 February 2026
- Language
- EN
- Document type
- Preprint