In estimating the mixing time of a random walk on a random graph, the intrinsic diameter of the random graph is a crucial related quantity. In a variety of supercritical models, including the Erdos-Renyi graph with average degree c>1, the mixing time is quadratic in the diameter; on the other hand, in mean field critical models such as the Erdos-Renyi graph with average degree 1, the mixing time is cubic in the diameter. A new structure theorem allows us to interpolate between these cases and handle near-critical random graphs. [Talk based on joint works with J. Ding, E.
Lubetzky, J.-H. Kim and A. Nachmias.]
Copyright. All Rights Reserved.