Conjecture on double-logarithmic diameter and typical distance in preferential attachment graphs

Let Gm,δ(t)G_{m,\delta}(t) be the preferential attachment graph with parameters mm and δ\delta, and let V1,V2[t]V_1,V_2\in [t] be two uniformly chosen independent vertices. Write distG(V1,V2)\operatorname{dist}_{G}(V_1,V_2) for the graph distance between V1V_1 and V2V_2, and call this the typical distance. Convergence conjecture for δ<0\delta<0. Fix m2m\geq 2 and δ(m,0)\delta\in(-m,0). Then

diam(Gm,δ(t))loglogt\frac{\operatorname{diam}(G_{m,\delta}(t))}{\log\log t}

and

distGm,δ(t)(V1,V2)loglogt\frac{\operatorname{dist}_{G_{m,\delta}(t)}(V_1,V_2)}{\log\log t}

converge in probability to positive and different constants. The available bounds show double-logarithmic growth of the diameter in this regime, but do not determine the limiting constants or provide a matching lower bound for typical distances.

Sources & referencesView supporting material

Primary source

Sander Dommers, Remco van der Hofstad and Gerard Hooghiemstra, “Diameters in preferential attachment models”, arXiv:0705.4153 (2010).

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.