GRD monotonicity for insertion depth and tree height
GRD monotonicity for insertion depth and tree height
Let be the preferential attachment tree on generated by the nondecreasing attachment function . Write for the graph distance from the root to the newest vertex , and for the maximum graph distance from the root to any vertex. For nondecreasing functions , say that dominates in growth-ratio order when
for every , equivalently when is nondecreasing. Set and . GRD monotonicity. If , then for all ,
The conjecture formalizes the intuition that stronger reinforcement toward high-degree vertices produces shallower preferential attachment trees. It asserts simultaneous monotonicity for both insertion depth and height under growth-ratio dominance; the supplied source gives no resolution, so the claim remains open.
Sources & referencesView supporting material
Primary source
Christian Mönch, “Partial orders and monotonicity of logarithmic depth and height in preferential attachment trees”, arXiv:2602.14741 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.