Vienna Combinatorics Seminar

How many connected graphs have a prescribed degree sequence?
 This classical combinatorial question turns out to admit a natural probabilistic approach.

In joint ongoing work with Sasha Bell and Remco van der Hofstad, we derive asymptotic formulas for the number of connected graphs with a given degree sequence. Our approach is an example of the probabilistic method. Concretely, we construct a random graph in which (an approximation of) the prescribed degree sequence appears with high probability inside a large connected component. This perspective allows us to translate questions about enumeration into probabilistic statements about random graphs.

Along the way, I will discuss several key probabilistic tools, including the configuration model, branching process approximations, and local weak convergence, and explain how they combine to yield asymptotic counting results.