GRD monotonicity for insertion depth and tree height

Let Tn(f)T_n(f) be the preferential attachment tree on [n][n] generated by the nondecreasing attachment function f:N0R>0f:{\mathbb{N}}_0\to\mathbb{R}_{>0}. Write Dn(f)D_n(f) for the graph distance from the root to the newest vertex nn, and Hn(f)H_n(f) for the maximum graph distance from the root to any vertex. For nondecreasing functions f,g:N0R>0f,g:{\mathbb{N}}_0\to\mathbb{R}_{>0}, say that ff dominates gg in growth-ratio order when

f(k+1)f(k)g(k+1)g(k)\frac{f(k+1)}{f(k)}\geq\frac{g(k+1)}{g(k)}

for every kN0k\in\mathbb{N}_0, equivalently when f(k)/g(k)f(k)/g(k) is nondecreasing. Set Ef[Dn]:=E[Dn(f)]{\mathbb{E}}_f[D_n]:={\mathbb{E}}[D_n(f)] and Ef[Hn]:=E[Hn(f)]{\mathbb{E}}_f[H_n]:={\mathbb{E}}[H_n(f)]. GRD monotonicity. If fGRgf\succeq_{\mathrm{GR}}g, then for all n1n\geq1,

Ef[Dn]Eg[Dn],Ef[Hn]Eg[Hn].{\mathbb{E}}_f[D_n]\leq{\mathbb{E}}_g[D_n],\qquad {\mathbb{E}}_f[H_n]\leq{\mathbb{E}}_g[H_n].

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.