Sampling bipartite graphs with given vertex degrees and fixed edges and non-edges

Abstract

We consider the problem of sampling a bipartite graph with given vertex degrees where a set $F$ of edges and non-edges which need to be contained is predefined. Our general result shows that the repeated swap of edges and non-edges in alternating cycles of at most size $2\ell -2$ ('$j$-swaps' with $j\le 2\ell -2$) in a current graph lead to an ergodic Metropolis Markov chain whenever $F$ does not contain a cycle of length $2\ell$ with $\ell \ge 4.$ This leads to useful Markov chains whenever $\ell$ is not too large. If $F$ is a forest, $4$- and $6$-swaps are sufficient. Furthermore, we prove that $4$-swaps are sufficient when $F$ does not contain a matching of size $3.$ We extend the Curveball algorithm of Strona et al. \cite{Strona2014b} to our cases.

19 pages, 5 figures