Spring 2010 Seminar Series

DATE: May 6th
LOCATION: E51-376
TIME: 4:15pm
Reception immediately following in the ORC Conference Room, E40-106

SPEAKER:
Alexander Barvinok

TITLE
Gaussian and Almost Gaussian Formulas for the Number of Integer Points in Polyhedra

ABSTRACT
In this work, joint with J.A. Hartigan (Yale), we present some rather simple and computationally efficient approximate formulas for the number of integer points in higher-dimensional polyhedra. The underlying intuition is provided by the maximum entropy principle and the Local Central Limit Theorem. We show that the formulas are asymptotically exact for a reasonably wide class of polyhedra, including multi-way transportation polytopes. For other interesting enumeration problems, such as those of counting non-negative integer matrices with prescribed row and column sums or counting labeled graphs with prescribed degree sequences, one has to employ an "Edgeworth correction factor", which is also efficiently computable.