Weak disorder in the stochastic mean-field model of distance. II (Q1952427)

The complete graph is considered where each edge carries an exponentially distributed weight with parameter equal to 1. Assume that the complete graph has \(n\) vertices that are labelled with the numbers from 1 to \(n\) and consider two arbitrary vertices; without loss of generality suppose that these are 1 and \(n\). Let \(\mathcal{P}\) be a path between vertices 1 and \(n\) and consider the weight of \(\mathcal{P}\) that is defined as \(w (\mathcal{P}) = \sum_{e \in \mathcal{P}} E_e^{-s}\), where \(E_e\) is the weight of the edge \(e\) and \(s>0\). Note that when \(s \rightarrow \infty\), the weight is in fact the minimum edge weight. The parameters that are considered are the weight of an optimal path as well as its number of edges. The main result states that for all positive values of \(s\) except for a countably infinite set, which is explicitely described, the number of edges is concentrated to a unique value, whereas the weight of an optimal path, when rescaled appropriatelly, follows, asymptotically as \(n\) grows, the Gumbel distribution. When \(s\) belongs to the exceptional set, the authors also determine the asymptotic distributions of these random variables. In particular, it is shown that the number of edges is concentrated on a set of two values, which occur with positive probability each.