Rapid mixing of the switch Markov chain for strongly stable degree sequences

  • Thu 5 Nov 20

    15:00 - 16:00

  • Online

    Zoom (ID 978 6853 5544)

  • Event speaker

    Dr Georgios Amanatidis

  • Event type

    Lectures, talks and seminars

  • Event organiser

    Mathematical Sciences, Department of

  • Contact details

    Jesus Martinez-Garcia

These Departmental Seminars are for everyone in Maths. We encourage anyone interested in the subject in general, or in the particular subject of the seminar, to come along. It's a great opportunity to meet people in the Maths Department and join in with our community.

Rapid mixing of the switch Markov chain for strongly stable degree sequences

The switch Markov chain has been extensively studied as the most natural Markov Chain Monte Carlo approach for sampling graphs with prescribed degree sequences. We show that the switch chain for sampling simple undirected graphs with a given degree sequence is rapidly mixing when the degree sequence is so-called strongly stable.

Strong stability is satisfied by all degree sequences for which the switch chain was known to be rapidly mixing based on Sinclair's multicommodity flow method up until a recent manuscript of Erd\H{o}s et al. (2019). Our approach relies on an embedding argument, involving a Markov chain defined by Jerrum and Sinclair (1990). This results in a much shorter proof that unifies (almost) all the rapid mixing results for the switch chain in the literature, and extends them up to sharp characterizations of P-stable degree sequences. In particular, our work resolves an open problem posed by Greenhill and Sfragara (2017).


Georgios Amanatidis, University of Essex

How to attend

If not a member of the Dept. Mathematical Science at the University of Essex, you can register your interest in attending the seminar and request the Zoom’s meeting password by emailing Dr Jesus Martinez-Garcia (jesus.martinez-garcia@essex.ac.uk).

Related events