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

Recommendations

• The Ehrhart polynomial of the Birkhoff polytope
• A generating function for all semi-magic squares and the volume of the Birkhoff polytope
• scientific article; zbMATH DE number 2237620
• On the Volume of the Polytope of Doubly Stochastic Matrices
• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes

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)