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



Bounds on the number of lattice points
in a polytope via concentration estimates

Austin Shapiro

University of Michigan


Abstract

It is generally hard to count, or even estimate, how many integer points lie in a polytope P. Barvinok and Hartigan approach the problem by way of information theory, showing how to efficiently compute a random vector which samples the integer points of P with (computable) constant mass, but which may also land outside P. Thus, to count the integer points of P, it suffices to determine the frequency with which the random vector falls in P.

I will present several upper bounds on this frequency. This problem may be expressed as a variant of the Littlewood-Offord problem, that is, of bounding the concentration of a sum of independent random variables. I will sketch connections between my work and earlier approaches to this problem.