Towards Random Uniform Sampling of Bipartite Graphs with given Degree Sequence
Keywords:
degree sequence, random sampling, multicommodity flow, Sinclair's method, Markov chain,
Abstract
In this paper we consider a simple Markov chain for bipartite graphs with given degree sequence on $n$ vertices. We show that the mixing time of this Markov chain is bounded above by a polynomial in $n$ in case of half-regular degree sequence. The novelty of our approach lies in the construction of the multicommodity flow in Sinclair's method.