The asymptotic volume of the Birkhoff polytope

MaRDI QIDQ3565415zbMATH OpenFDO

Authors E. Rodney Canfield, Brendan D. McKay

Publication date 3 June 2010

Full work available at URL https://arxiv.org/abs/0705.2422, http://www.math.rochester.edu/ojac/vol4/CanfieldMcKayBirkhoff.pdf

Mathematics Subject Classification ID

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

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).

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

Cited in

(23)

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

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)