Alexander Barvinok, U. of Michigan Enumeration of contingency tables and integer flows

A contingency table is a non-negative integer matrix with prescribed row and column sums.

Given a positive integer m-vector R of row sums, a positive integer n-vector C of column sums, and a non-negative mxn matrix W of weights, we consider the weighted number T(R,C;W) of contingency tables with the row sums R, the column sums C, and the weight of the table equal to the product of the entries of W, each raised to the power determined by the corresponding entry of the contingency table. Hence if W is a matrix of 1s, we obtain the number of contingency tables with prescribed margins and if W is a 0-1 matrix, we obtain the number of integer feasible flows in a bipartite network with prescribed demands/supplies at the vertices. These numbers are of interest for a variety of problems in combinatorics, statistics, and representation theory. Generally speaking, one can think of T(R,C;W) as of the generating function for the set of integer points in the transportation polytope of mxn non-negative matrices with the row sums R and the column sums C.

We represent T(R,C;W) as the expectation of the permanent of a random matrix with exponentially distributed entries. This allows us to approximate T(R,C;W) by the integral of some log-concave function on the space of mxn matrices. The representation leads to an efficient approximation algorithm for computing T(R,C;W) as well as to a certain version of the Brunn-Minkowski inequality. Geometrically, we obtain a version of the Brunn-Minkowski inequality for the number of integer points in some special class polytopes, namely the flow polytopes.