Research Repository

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

Amanatidis, Georgios and Kleer, Pieter (2020) 'Rapid mixing of the switch Markov chain for strongly stable degree sequences.' Random Structures and Algorithms, 57 (3). pp. 637-657. ISSN 1042-9832

RSA_final_UoE.pdf - Accepted Version

Download (410kB) | Preview


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ős and coworkers in 2019. Our approach relies on an embedding argument, involving a Markov chain defined by Jerrum and Sinclair in 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 in 2017.

Item Type: Article
Uncontrolled Keywords: degree sequence; mixing time; sampling; switch Markov chain
Divisions: Faculty of Science and Health
Faculty of Science and Health > Mathematical Sciences, Department of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 11 Aug 2020 12:56
Last Modified: 06 Jan 2022 14:17

Actions (login required)

View Item View Item