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:N0→R>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:N0→R>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 k∈N0k\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 f⪰GRgf\succeq_{\mathrm{GR}}g, then for all n≥1n\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.

References

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.