Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences
share
We show that the switch Markov chain for sampling simple undirected, as well as bipartite, graphs with a given degree sequence is rapidly mixing when the degree sequence is strongly stable. Strong stability is closely related to the notion of P-stability introduced by Jerrum and Sinclair (1990), and is satisfied by all degree sequences for which the switch chain is known to be rapidly mixing based on Sinclair's multicommodity flow method. Our approach relies on a comparison argument with a Markov chain defined by Jerrum and Sinclair for sampling graphs that almost have a given degree sequence. This comparison provides a much shorter proof for the currently known rapid mixing results of the switch chain and extends them up to sharp characterizations of P-stability in terms of certain graph parameters. In particular, our work resolves an open problem posed by Greenhill and Sfragara (2017) regarding the switch chain on undirected graphs.
READ FULL TEXT