Description:

Title: Giant Component of Random Graphs with Given Degrees

Abstract: Given a feasible degree sequence D, we consider the uniform distribution over all graphs with degree sequence D. In 1995, Molloy and Reed gave a criterion for determining the existence of a giant (i.e. linear in n) component for degree sequences satisfying certain technical conditions, and it was not until 2018 that Joos, Perarnau, Rautenbach, and Reed gave a precise threshold-like characterization that applies to almost all feasible D. In this talk, we work in the "supercritical" regime and uncover the precise structure of the giant component when it exists, obtaining bounds on the diameter and random walk mixing time on the giant which are tight up to polylogarithmic factors. Our techniques involve a variation of core-kernel reduction and analysis of switching-type operations. Joint work with Louigi Addario-Berry and Bruce Reed.