Simple Markov-chain algorithms for generating bipartite graphs and tournaments

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. F or the first problem, we cannot prove that our chain is rapidly mixing in g eneral, but in the near-regular case, i.e., when all the degrees are almost equal, we give a proof of rapid mixing. Our methods also apply to the corr esponding problem for general (nonbipartite) regular graphs, which was stud ied earlier by several researchers. One significant difference in our appro ach is that our chain has one state for every graph (or bipartite graph) wi th the given degree sequence; in particular, there are no auxiliary states as in the chain used by Jerrum and Sinclair. For the problem of generating tournaments, we are able to prove that our Markov chain on tournaments is r apidly mixing, if the score sequence is near-regular. The proof techniques we use for the two problems are similar. (C) 1999 John Wiley & Sons, Inc.