The University of Michigan Combinatorics Seminar
Winter 2005
January 28, 4:10-5:00, 3866 East Hall



Counting contingency tables and 0-1 matrices

Alexander Barvinok

University of Michigan


Abstract

Contingency tables are non-negative integer matrices with prescribed row and column sums. I am planning to talk about some new ideas and results in efficient enumeration of contingency tables and 0-1 matrices with prescribed row and column sums. The results are based on two observations: first, that the number of contingency tables can be expressed as the expected value of the permanent of a matrix with random exponentially distributed entries and second, that certain symmetric polynomials admit low-rank approximations.