University of Delaware
Discrete Mathematics Seminar

Random Generation of Bipartite Graphs with Prescribed Degrees
Nayantara Bhatnagar
University of Delaware
Tuesday, November 13, 2012
Ewing Hall 336 4.00 - 5.00 pm

ABSTRACT: Randomly generation of 0-1 contingency tables is a well-studied problem in statistics as well as the theory of random graphs, since it is equivalent to generating a random bipartite graph with a prescribed degree sequence. I will present a (polynomial time) random walk algorithm which outputs approximately uniform samples.

This is joint work with Ivona Bezakova and Eric Vigoda.