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

Enrico Baroni, Remco van der Hofstad, Júlia Komjáthy (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
29 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)906-934
Number of pages29
JournalJournal of Statistical Physics
Volume174
Issue number4
DOIs
Publication statusPublished - 28 Feb 2019

Keywords

  • Configuration model
  • First passage percolation
  • Power law degrees
  • Weighted typical distances

Fingerprint Dive into the research topics of 'Tight fluctuations of weight-distances in random graphs with infinite-variance degrees'. Together they form a unique fingerprint.

  • Cite this