Seva Shneer

First passage percolation on Erdos-Renyi graphs with general weights

We consider an Erdos-Renyi random graph on n nodes where the probability of an edge being present between any two nodes is equal to λ/n with λ > 1. Every edge is assigned a (non-negative) weight independently at random from a general distribution. For every path between two typical vertices we introduce its hop-count (which counts the number of edges on the path) and its total weight (which adds up the weights of all edges on the path). We prove a limit theorem for the joint distribution of the appropriately scaled hop-count and general weights. This theorem, in particular, provides a limiting result for hop-count and the total weight of the shortest path between two nodes. This is a joint work Fraser Daly and Matthias Schulte.