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 (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.
