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.

Date
Thursday, December 13, 2018
14:15 — 15:45
Event
Combinatorics seminar
Location
Alfréd Rényi Institute, Budapest