Abstract:

How does the metric induced by an expander graph change when random weights are placed on its edges? In particular, how are typical and maximal distances affected by this perturbation? A recent structure result for the largest component in the supercritical Erdos-Renyi random graph translates the study of its geometry to these questions, where the role of the expander is played by a random cubic graph. This enables us to read off key properties of the supercritical random graph such as the diameter (whose asymptotics for the complete supercritical regime was unknown prior to this work), bounds on longest simple paths and cycles etc. Prior estimates for these include [Luczak'91], [Chung-Lu'01], [Fernholz-Ramachandran'07], [Luczak-Seierstad'09], [Riordan-Wormald'09].

In the talk we will describe the reduction from the supercritical random graph to the random perturbation of a random cubic graph. We will then demonstrate how to readily characterize the geometry of the giant component via this reduction, focusing on typical distances between vertices and the asymptotics of the diameter.

Based on joint works with Jian Ding, Jeong Han Kim and Yuval Peres.