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