Weak disorder in the stochastic mean-field model of distance II

Original · EN

In this paper, we study the complete graph Kₙ with n vertices, where we attach an independent and identically distributed (i.i.d.) weight to each of the n(n-1)/2 edges. We focus on the weight Wₙ and the number of edges Hₙ of the minimal weight path between vertex 1 and vertex n. It is shown in (Ann. Appl. Probab. 22 (2012) 29-69) that when the weights on the edges are i.i.d. with distribution equal to that of Eˢ, where s>0 is some parameter, and E has an exponential distribution with mean 1, then Hₙ is asymptotically normal with asymptotic mean s n and asymptotic variance s² n. In this paper, we analyze the situation when the weights have distribution E⁻ˢ,s>0, in which case the behavior of Hₙ is markedly different as Hₙ is a tight sequence of random variables. More precisely, we use the method of Stein-Chen for Poisson approximations to show that, for almost all s>0, the hopcount Hₙ converges in probability to the nearest integer of s+1 greater than or equal to 2, and identify the limiting distribution of the recentered and rescaled minimal weight. For a countable set of special s values denoted by S={sⱼ}ⱼ≥₂, the hopcount Hₙ takes on the values j and j+1 each with positive probability.