Leírás
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.
The main goal of this talk is to show that stability is not a
necessary condition for the rapid mixing of the swap Markov
chain.
(Joint work by Erdős, Miklós, M, Soltész)