The University of Michigan Combinatorics Seminar
Fall 2006
September 15, 4:10-5:00, 3866 East Hall



Counting contingency tables and integer flows

Alexander Barvinok

University of Michigan


Abstract

I will discuss an efficient algorithm to approximate the number of contingency tables (non-negative integer matrices with prescribed row and column sums) and integer flows in networks as well as certain Brunn-Minkowski type inequalities relating the quantities of interest. The key idea is to approximate the number of integer points in a certain polytope by the integral of a log-concave density.