Towards Random Uniform Sampling of Bipartite Graphs with given Degree Sequence

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

The Electronic Journal of Combinatorics · 2013 · 51 citations · 16 references

DOIFull text

Open access

Concepts

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.

References

16