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

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 normal and directed degree sequences for which rapid mixing of the swap Markov chain is proved. In this paper we present two groups of results. An example from the first group is the following theorem: let [Image: see text] be a directed degree sequence on n vertices. Denote by Δ the maximum value among all in- and out-degrees and denote by [Image: see text] the number of edges in the realization. Assume furthermore that [Image: see text] . Then the swap Markov chain on the realizations of [Image: see text] is rapidly mixing. This result is a slight improvement on one of the results of Greenhill and Sfragara. An example from the second group is the following: let d be a bipartite degree sequence on the vertex set U ⊎ V, and let 0 < c(1) ≤ c(2) < |U| and 0 < d(1) ≤ d(2) < |V| be integers, where c(1) ≤ d(v) ≤ c(2): ∀v ∈ V and d(1) ≤ d(u) ≤ d(2): ∀u ∈ U. Furthermore assume that (c(2) − c(1) − 1)(d(2) − d(1) − 1) < max{c(1)(|V| − d(2)), d(1)(|U| − c(2))}. Then the swap Markov chain on the realizations of d is rapidly mixing. A straightforward application of this latter result shows that when a random bipartite or directed graph is generated under the Erdős—Rényi G(n, p) model with mild assumptions on n and p then the degree sequence of the generated graph has, with high probability, a rapidly mixing swap Markov chain on its realizations.