Counting integer points in higher-dimensional polyhedra

Counting integer points in higher-dimensional polyhedra

-
Alexander Barvinok, University of Michigan
Fine Hall 314

Counting integer points in polyhedra, or even establishing if there is one, is computationally hard, and yet we would like to do it for a variety of reasons. An example of a particular interest concerns counting “contingency tables”, that is non-negative integer matrices with prescribed row and column sums, and also “integer flows”, that is, non-negative integer matrices with prescribed row and column sums and zeros in specified positions. I plan to discuss the “maximum entropy approach”, its successes, and some yet unexplained recent experimental data. The idea of the approach, coming from statistical physics, is roughly as follows: given a polyhedron, represented as the intersection of an affine subspace with the non-negative orthant, we supplant the uniform distribution on the set of integer points in the polyhedron by a much more tractable maximum entropy distribution on the set  of all non-negative integer vectors with expectation in the subspace. To make the approach rigorous requires (not surprisingly) some Fourier analysis and (somewhat unexpectedly) classical van der Waerden and Bregman-Minc inequalities for the permanent of a non-negative matrix.