Simple Markov-chain algorithms for generating bipartite graphs and tournaments
✍ Scribed by Ravi Kannan; Prasad Tetali; Santosh Vempala
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 174 KB
- Volume
- 14
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
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. For the first problem, we cannot prove that our chain is rapidly mixing in general, 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 corresponding problem for general (nonbipartite) regular graphs, which was studied earlier by several researchers. One significant difference in our approach is that our chain has one state for every graph (or bipartite graph) with 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 rapidly mixing, if the score sequence is near-regular. The proof techniques we use for the two problems are similar.