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



Gaussian and almost Gaussian formulas for the number of integer points in polytopes

Alexander Barvinok

University of Michigan


Abstract

I plan to discuss a rather simple and computationally efficient formula for the number of integer points in a higher-dimensional polytope. The underlying intuition is based on the maximum entropy principle and the local Central Limit Theorem. One can prove that the formula is asymptotically exact in a wide variety of situations, including, in particular, counting integer points in multi-way transportation polytopes. To count integer points in a two-way transportation polytope (that is, to count non-negative integer matrices with prescribed row and column sums), one has to introduce the Edgeworth correction factor, which is also efficiently computable.

This is a joint work with J.A. Hartigan (Yale).