Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes
| dc.creator | Barvinok, Alexander | |
| dc.date | 2007-09-24 | |
| dc.date | 2008-08-21 | |
| dc.date.accessioned | 2026-07-07T09:57:24Z | |
| dc.date.available | 2026-07-07T09:57:24Z | |
| dc.description | We prove an asymptotic estimate for the number of mxn non-negative integer matrices (contingency tables) with prescribed row and column sums and, more generally, for the number of integer feasible flows in a network. Similarly, we estimate the volume of the polytope of mxn non-negative real matrices with prescribed row and column sums. Our estimates are solutions of convex optimization problems and hence can be computed efficiently. As a corollary, we show that if row sums R=(r_1, ..., r_m) and column sums C=(c_1, ..., c_n) with r_1 + ... + r_m =c_1 + ... +c_n =N are sufficiently far from constant vectors, then, asymptotically, in the uniform probability space of the mxn non-negative integer matrices with the total sum N of entries, the event consisting of the matrices with row sums R and the event consisting of the matrices with column sums C are positively correlated. | |
| dc.description | 35 pages, estimates sharpened, details and references added | |
| dc.identifier | https://arxiv.org/abs/0709.3810 | |
| dc.identifier | http://arxiv.org/abs/0709.3810 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/167329 | |
| dc.subject | Combinatorics | |
| dc.subject | Metric Geometry | |
| dc.subject | 05A16, 60C05, 52A38, 52B12, 52B55 | |
| dc.title | Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes | |
| dc.type | text |