Long paths in first passage percolation on the complete graph I. Local pwit dynamics

Maren Eckhoff, Jesse Goodman, Remco van der Hofstad, Francesca R. Nardi

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)


We study the random geometry of first passage percolation on the complete graph equipped with independent and identically distributed edge weights. We find classes with different behaviour depending on a sequence of parameters (sn)n≥1 that quantifies the extreme-value behavior of small weights. We consider both n-independent as well as n-dependent edge weights and illustrate our results in many examples. In particular, we investigate the case where sn → ∞, and focus on the exploration process that grows the smallest-weight tree from a vertex. We establish that the smallest-weight tree process locally converges to the invasion percolation cluster on the Poisson-weighted infinite tree, and we identify the scaling limit of the weight of the smallest-weight path between two uniform vertices. In addition, we show that over a long time interval, the growth of the smallest-weight tree maintains the same volume-height scaling exponent – volume proportional to the square of the height – found in critical Galton–Watson branching trees and critical Erdős-Rényi random graphs.

Original languageEnglish
Article number85
Pages (from-to)1-45
Number of pages45
JournalElectronic Journal of Probability
Publication statusPublished - 2020


  • First passage percolation
  • Invasion percolation
  • Random graphs


Dive into the research topics of 'Long paths in first passage percolation on the complete graph I. Local pwit dynamics'. Together they form a unique fingerprint.

Cite this