Towards Random Uniform Sampling of Bipartite Graphs with given Degree Sequence

István Miklós, Péter L Erdős, Lajos Soukup

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.


Keywords


degree sequence, random sampling, multicommodity flow, Sinclair's method, Markov chain,

Full Text: PDF