Premium
Simple Markov‐chain algorithms for generating bipartite graphs and tournaments
Author(s) -
Kannan Ravi,
Tetali Prasad,
Vempala Santosh
Publication year - 1999
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
ISBN - 0-89871-390-0
DOI - 10.1002/(sici)1098-2418(199907)14:4<293::aid-rsa1>3.0.co;2-g
Subject(s) - bipartite graph , markov chain , combinatorics , mathematics , sequence (biology) , simple (philosophy) , mixing (physics) , markov chain mixing time , degree (music) , discrete mathematics , chain (unit) , graph , variable order markov model , markov model , statistics , philosophy , physics , epistemology , quantum mechanics , astronomy , biology , acoustics , genetics
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. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 293–308, 1999