Towards random uniform sampling of bipartite graphs with given degree sequence

P\'eter L. Erd\"os, Ist\'an Mikl\'os, Lajos Soukup
Arxiv ID: 1004.2612Last updated: 1/1/2021
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.

PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.

Related papers

Commercial Disclosure
© 2023 Paper Studio™. All Rights Reserved.