Towards Random Uniform Sampling of Bipartite Graphs with given Degree Sequence

  • István Miklós
  • Péter L Erdős
  • Lajos Soukup
Keywords: degree sequence, random sampling, multicommodity flow, Sinclair's method, Markov chain,


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.

Article Number