Counting integer points in higher-dimensional polyhedra
Counting integer points in higher-dimensional polyhedra
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.