RTG Kolloquium

How many connected graphs have a prescribed degree sequence? This classical combinatorial question turns out to admit a surprisingly natural probabilistic interpretation. In joint work with Sasha Bell and Remco van der Hofstad, we derive asymptotic formulas for the number of connected graphs with a given degree sequence in the sparse regime. Our approach is based on the probabilistic method: rather than counting graphs directly, we study a random graph model in which the desired structures appear with a certain probability. A major challenge is that connectivity is exponentially unlikely in a random graph when many vertices have degree 1. We overcome this by using a probabilistic "change of perspective" that turns the rare event into a typical one. Pre-talk: Local convergence of random graphs The Benjamini-Schramm topology is a useful tool for understanding local functionals of large random graphs, such as degrees, triangle counts and clustering coefficients, but also more surprising properties such as the cover number, the size of the largest component and the spectral distribution. In the pre-talk I will give a gentle, high-level introduction to this notion of convergence, which will be useful (but not essential) for following the main talk.

tba

tba