Friday, December 6, 2013 at 3:30pm
Frank H. T. Rhodes Hall, 655
CAM Colloquium: Hamed Amini (EPFL) - Shortest-weight paths in random graphs
Consider a random regular graph with degree d and of size n. Assign to each edge an i.i.d. exponential random variable. In the first part, we establish a precise asymptotic expression for the maximum number of edges on the shortest-weight paths between a fixed vertex and all the other vertices, as well as between any pair of vertices. This is a joint work with Yuval Peres. We then analyze the impact of the edge weights on distances in sparse random graphs. Our main result consists of a precise asymptotic expression for the weighted diameter when the edge weights are i.i.d. exponential random variables.
This is based on a joint work with Marc Lelarge.