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.

40 pages. v3 contains minor fixes and corrects the counterexample bounds; a python script has been added to the source to certify the counterexample; the qualitative conclusions are unchanged