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


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.

Combinatorics seminar
Alfréd Rényi Institute, Budapest
Tamás Róbert Mezei

My research interests include Graph Theory, Computational Geometry, and Algorithms