Short paths for first passage percolation on the complete graph

Abstract

We study the complete graph equipped with a topology induced by independent and identically distributed edge weights. The focus of our analysis is on the weight W_n and the number of edges H_n of the minimal weight path between two distinct vertices in the weak disorder regime. We establish novel and simple first and second moment methods using path counting to derive first order asymptotics for the considered quantities. Our results are stated in terms of a sequence of parameters (s_n) that quantifies the extreme-value behaviour of the edge weights, and that describes different universality classes for first passage percolation on the complete graph. These classes contain both n-independent and n-dependent edge weight distributions. The method is most effective for the universality class containing the edge weights E^{s_n}, where E is an exponential(1) random variable and s_n log n -> infty, s_n^2 log n -> 0. We discuss two types of examples from this class in detail. In addition, the class where s_n log n stays finite is studied. This article is a contribution to the program initiated in \cite{BhaHof12}.

31 pages, 4 figures

References in corpus (2)

• Distances in random graphs with finite variance degrees
• Universality for first passage percolation on sparse random graphs

Cited by in corpus (8)

• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• Random geometry and the Kardar-Parisi-Zhang universality class
• Long paths in first passage percolation on the complete graph I. Local PWIT dynamics
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• Degree distribution of shortest path trees and bias of network sampling algorithms
• On The Time Constant for Last Passage Percolation on Complete Graph
• Successive shortest paths in complete graphs with random edge weights
• Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems