The asymptotic volume of the Birkhoff polytope

zbMATH Open1193.15034arXiv0705.2422MaRDI QIDQ3565415FDOQ3565415

Brendan D. McKay, E. Rodney Canfield

Publication date: 3 June 2010

Abstract: Let m,n be positive integers. Define T(m,n) to be the transportation polytope consisting of the m x n non-negative real matrices whose rows each sum to 1 and whose columns each sum to m/n. The special case B(n)=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 T(m,n) as n goes to infinity, 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 B(n).

Full work available at URL: https://arxiv.org/abs/0705.2422

Mathematics Subject Classification ID

Length, area, volume and convex sets (aspects of convex geometry) (52A38) Asymptotic enumeration (05A16) Stochastic matrices (15B51)

Cited In (23)

• A generating function for all semi-magic squares and the volume of the Birkhoff polytope
• Phase transition in random contingency tables with non-uniform margins
• Asymptotic enumeration of integer matrices with large equal row and column sums
• A practical algorithm for volume estimation based on billiard trajectories and simulated annealing
• Stochastic n-point D-bifurcations of stochastic Lévy flows and their complexity on finite spaces
• Random doubly stochastic matrices: the circular law
• Four questions on Birkhoff polytopes
• A practical volume algorithm
• High pseudomoments of the Riemann zeta function
• Commutative algebra of statistical ranking
• Secular coefficients and the holomorphic multiplicative chaos
• On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope
• Tighter bounds on the independence number of the Birkhoff graph
• Algebraic and geometric structures inside the Birkhoff polytope
• A quick estimate for the volume of a polyhedron
• Unconditional reflexive polytopes
• Unistochastic Matrices and Related Problems
• Deformation cones of Tesler polytopes
• Restricted Birkhoff polytopes and Ehrhart period collapse
• Ehrhart positivity of Tesler polytopes and Berline-Vergne's valuation
• Lower bounds for contingency tables via Lorentzian polynomials
• Faces of Birkhoff Polytopes
• The diameter of the Birkhoff polytope

This page was built for publication: The asymptotic volume of the Birkhoff polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3565415)