Towards random uniform sampling of bipartite graphs with given degree sequence

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 {\em semi-regular} degree sequence. The novelty of our approach lays in the construction of the canonical paths in Sinclair's method.

47 pages, submitted for publication. In this version we explain explicitly our main contribution and corrected a serious flaw in the cycle decomposition

Cited by in corpus (1)

• Deciding football sequences