Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs

Abstract

Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. All of these results assume some kind of regularity in the corresponding degree sequences. Recently, Greenhill and Sfragara published a breakthrough paper about irregular simple and directed degree sequences for which rapid mixing of the MCMC is known (for e.g., scale-free graphs with $\gamma>2.5$). In this paper we present two group of theorems. The first one contains a result similar to the theorem of GS for bipartite degree sequences, which slightly improve their result on directed degree sequences. The second group presents another vast region of bipartite degree sequences with rapidly mixing MCMC sampling process.