A non-stable bipartite degree sequence on which the swap Markov chain is rapidly mixing

Abstract

The swap Markov chain on a bipartite degree sequence $d$ operates on realizations of $d$ by taking two-two vertices from each color class uniformly, and if the four vertices induce exactly two disjoint edges, replaces them with the two edges induced in the complement. A bipartite degree sequence is stable, if reducing the degrees of one vertex from each color class changes the number of realizations by at most a factor of a polynomial of the number of vertices. Recently, we have shown that the swap Markov chain is rapidly mixing on the realizations of stable (bipartite) degree sequences.