On the Switch Markov Chain for Strongly Stable Degree Sequences
share
We show that the switch Markov chain for sampling undirected and bipartite graphs with a given degree sequence is rapidly mixing when the degree sequence is strongly stable. Strong stability is more restricted than the notion of stability introduced by Jerrum and Sinclair (TCS, 1990). Interestingly enough, strong stability 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 known rapid mixing results of the switch chain and extends them up to sharp characterizations of stability in terms of certain graph parameters. In particular, our work resolves an open problem posed by Greenhill and Sfragara (TCS, 2017) regarding the switch chain for undirected graphs.
READ FULL TEXT