Everyone is welcome to attend the next N&O seminar with Pieter Kleer on the topic 'The switch Markov chain for the uniform sampling of graphs with given degrees'.
Abstract: The uniform generation generation of graphs with given degrees in an important problem in the analysis of complex networks. One of the simplest approaches to this problem is the switch Markov chain. Here, one repeatedly switches two edges uniformly at random, while preserving the degree sequence. How many switches are needed before the resulting network is close to a uniform sample from the set of all graphs with the given degrees? The answer to this question is still open for general degree sequences. In this talk we will present a novel proof approach for the analysis of the switch Markov chain, based on Sinclair's multi-commodity flow method. The analysis relies on combinatorial arguments (no knowledge of Markov chains is required beyond the basic definition). In particular, our proof approach allows us to extend the existing range of degree sequences for which the switch Markov chain is known to be rapidly mixing (the chain is called rapidly mixing if only a po!
lynomial number of switches is needed to get close to a uniform sample). If time permits, we will also look at an extension of the generation problem, where, in addition to the degree sequence, also degree correlations are specified.
This is a joint work with Yorgos Amanatidis (CWI) and appeared in SODA 2019.
