## Abstract

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 (s_{n})_{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 s_{n} → ∞, 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 language | English |
---|---|

Article number | 85 |

Pages (from-to) | 1-45 |

Number of pages | 45 |

Journal | Electronic Journal of Probability |

Volume | 25 |

DOIs | |

Publication status | Published - 2020 |

## Keywords

- First passage percolation
- Invasion percolation
- Random graphs