Gaussian and almost Gaussian formulas for volumes and the number of integer points in polytopes
Speaker:
Alexander Barvinok, University of Michigan
Date and Time:
Thursday, September 16, 2010 - 2:15pm to 3:00pm
Location:
Fields Institute, Room 230
Abstract:
We present a family of computationally efficient formulas for volumes and the number of integer points in polytopes represented as the intersection of the non-negative orthant and an affine subspace. Although the formulas are not always applicable, they are asymptotically exact in a wide variety of situations. In particular, we obtain asymptotic formulas for the number of non-negative integer matrices with prescribed row and column sums and for the volumes of the respective transportation polytopes. The intuition for the formulas is provided by the maximum entropy principle, the Local Central Limit Theorem and its ramifications.