Lorenzo Federico

Almost connected configuration model

The configuration model is a simple and popular way to produce uniform random graphs with a fixed degree sequence. In this talk, we use it to formulate asymptotic conditions on the degree sequence such that, in the graph generated, the largest component contains n−o(n) vertices. We also provide stricter conditions under which the graph has a non-vanishing probability to be connected. We show that the relevant parameters in this regime are the number of vertices of degree 1 and 2, and the average degree, while vertices of higher degree play a minor role. We also derive sharp asymptotics for the number of vertices outside the giant, as a function of these parameters. Our proof uses the method of moments to compute the number of components that are lines or cycles and employs an exploration algorithm to prove that other kinds of small components are rare. Based on joint work with Remco van der Hofstad and Fiona Sloothaak.