First passage percolation on random graphs with infinite variance degrees

Research output: Book/ReportReportAcademic

1 Downloads (Pure)

Abstract

We prove non-universality results for first-passage percolation on the configuration model with i.i.d. degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviors are possible. When the weights are a.s. larger than a constant, the weight and number of edges in the graph grow proportionally to loglog(n), as for the graph distances. On the other hand, when the continuous-time branching process describing the first passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the processes started from the two sources. This non-universality is in sharp contrast to the setting where the degree sequence has a finite variance (see Bhamidi, Hofstad and Hooghiemstra arXiv: 1210.6839).
Original languageEnglish
Publishers.n.
Number of pages18
Publication statusPublished - 2015

Publication series

NamearXiv
Volume1506.01255 [math.PR]

Fingerprint Dive into the research topics of 'First passage percolation on random graphs with infinite variance degrees'. Together they form a unique fingerprint.

  • Cite this