The asymptotic volume of the Birkhoff polytope

Abstract

Let $m,n\ge 1$ be integers. Define ${\mathcal{T}}_{m,n}$ to be the <i>transportation polytope</i> 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 <i>Birkhoff-von Neumann polytope</i> 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 \mathrm{\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$.