The asymptotic volume of the Birkhoff polytope

By E. Rodney Canfield, Brendan D. McKay. Online Journal of Analytic Combinatorics, 2007

53 citations recorded by the source corpus.

Let \( m, n \geq 1 \) be integers. Define \( \mathcal{T}_{m,n} \) to be the transportation polytope consisting of the \( m \times n \) non-negative real matrices whose rows each sum to \( 1 \) and whose columns each sum to \( m/n \). The special case \( \mathcal{B}_n = \mathcal{T}_{n,n} \) is the much-studied Birkhoff-von Neumann polytope of doubly-stochastic matrices. Using a recent asymptotic enumeration of non-negative integer matrices (Canfield and McKay, 2007), we determine the asymptotic volume of \( \mathcal{T}_{m,n} \) as \( n \to \infty \) with \( m = m(n) \) such that \( m/n \) neither decreases nor increases too quickly. In particular, we give an asymptotic formula for the volume of \( \mathcal{B}_n \).

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/6db3c19cc8d4b04387869619f6010fc0e8fd7c63