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

At least 18 years old · documented by

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 dist⁡G(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 m≥2m\geq 2 and δ∈(−m,0)\delta\in(-m,0). Then

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

and

dist⁡Gm,δ(t)(V1,V2)log⁡log⁡t\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.

References

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.