TY - JOUR

T1 - Short paths for first passage percolation on the complete graph

AU - Eckhoff, M.

AU - Goodman, J.

AU - van der Hofstad, R.

AU - Nardi, F.R.

PY - 2013/6

Y1 - 2013/6

N2 - 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 and the number of edges H 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) that quantifies the extremevalue 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, where E is an exponential random variable and s log n → ∞, s log n → 0. We discuss two types of examples from this class in detail. In addition, the class where slog n stays finite is studied. This article is a contribution to the program initiated by Bhamidi and van der Hofstad (Ann. Appl. Probab. 22(1):29-69, 2012).

AB - 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 and the number of edges H 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) that quantifies the extremevalue 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, where E is an exponential random variable and s log n → ∞, s log n → 0. We discuss two types of examples from this class in detail. In addition, the class where slog n stays finite is studied. This article is a contribution to the program initiated by Bhamidi and van der Hofstad (Ann. Appl. Probab. 22(1):29-69, 2012).

UR - http://www.scopus.com/inward/record.url?scp=84877604917&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1007/s10955-013-0743-7

U2 - 10.1007/s10955-013-0743-7

DO - 10.1007/s10955-013-0743-7

M3 - Article

AN - SCOPUS:84877604917

VL - 151

SP - 1056

EP - 1088

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 6

ER -