TY - JOUR

T1 - Tight fluctuations of weight-distances in random graphs with infinite-variance degrees

AU - Baroni, Enrico

AU - van der Hofstad, Remco

AU - Komjáthy, Júlia

PY - 2019/2/28

Y1 - 2019/2/28

N2 - We prove results for first-passage percolation on the configuration model with degrees having asymptotic finite mean, infinite variance and i.i.d. edge-weights with strictly positive support of the form Y= a+ X, where a is a positive constant and the excess edge-weight X is a non-negative random variable with zero as the infimum of its support. We prove that the weight of the optimal path between two uniformly chosen vertices has tight fluctuations around the asymptotic mean of the graph-distance if and only if the following condition holds: the random variable X is such that the age-dependent branching process describing first-passage percolation exploration in the same graph with edge-weights from distribution X has a positive probability to reach infinitely many individuals in a finite time. This shows that almost-shortest paths in the graph-distance proliferate, in the sense that there even exist paths having tight total excess edge-weight for appropriate edge-weight distributions. Our proof makes use of a degree-dependent percolation model that we believe is interesting in its own right, as well as tightness results for distances in scale-free configuration models that we prove to hold under rather weak conditions on the degrees.

AB - We prove results for first-passage percolation on the configuration model with degrees having asymptotic finite mean, infinite variance and i.i.d. edge-weights with strictly positive support of the form Y= a+ X, where a is a positive constant and the excess edge-weight X is a non-negative random variable with zero as the infimum of its support. We prove that the weight of the optimal path between two uniformly chosen vertices has tight fluctuations around the asymptotic mean of the graph-distance if and only if the following condition holds: the random variable X is such that the age-dependent branching process describing first-passage percolation exploration in the same graph with edge-weights from distribution X has a positive probability to reach infinitely many individuals in a finite time. This shows that almost-shortest paths in the graph-distance proliferate, in the sense that there even exist paths having tight total excess edge-weight for appropriate edge-weight distributions. Our proof makes use of a degree-dependent percolation model that we believe is interesting in its own right, as well as tightness results for distances in scale-free configuration models that we prove to hold under rather weak conditions on the degrees.

KW - Configuration model

KW - First passage percolation

KW - Power law degrees

KW - Weighted typical distances

UR - http://www.scopus.com/inward/record.url?scp=85059663348&partnerID=8YFLogxK

U2 - 10.1007/s10955-018-2213-8

DO - 10.1007/s10955-018-2213-8

M3 - Article

AN - SCOPUS:85059663348

VL - 174

SP - 906

EP - 934

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 4

ER -