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


A substantial part of this work has been done at Eurandom and Eindhoven University of Technology. ME and JG are grateful to both institutions for their hospitality. The work of JG was carried out in part while at Leiden University (supported in part by the European Research Council grant VARIS 267356), the Technion, and the University of Auckland (supported by the Marsden Fund, administered by the Royal Society of New Zealand) and JG thanks his hosts at those institutions for their hospitality. The work of RvdH is supported by the Netherlands Organisation for Scientific Research (NWO) through VICI grant 639.033.806 and the Gravitation Networks grant 024.002.003. We thank the anonymous referee for their helpful and insightful comments, which were of great value in improving this paper.

FundersFunder number
Seventh Framework Programme267356
European Research Council
Royal Society of New Zealand
University of Auckland
Universiteit Leiden
Nederlandse Organisatie voor Wetenschappelijk Onderzoek639.033.806, 024.002.003
Technion - Israel Institute of Technology
Marsden Fund


    • 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