Combinatorics Seminar
When: Sunday, December 27, 10am
Where: Schreiber 309
Speaker: Eyal Lubetzky, Microsoft Research
Title: Distances in random metrics: from weighted expanders
to the geometry of the random graph
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 full supercritical regime
were unknown prior to this work), bounds on longest simple paths
and cycles etc. Prior estimates for these include works by Luczak,
Chung and Lu, Fernholz and Ramachandran, Luczak and Seierstad and
Riordan and Wormald.
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 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.