The Ehrhart polynomial of the Birkhoff polytope
Matthias Beck and Dennis Pixton
-
Our paper: Matthias
Beck and Dennis
Pixton, The Ehrhart polynomial of the Birkhoff polytope,
Discrete
Comput. Geom., 30 (2003), 623-637.
(Abstract, dvi, pdf,
postscript).
-
Our announcement of the calculation of the volume of the tenth polytope (dvi, pdf,
postscript).
-
The full Ehrhart polynomials for n ≤ 9.
-
The volumes of the Birkhoff polytope for n ≤
10. The volume for n = 9 has been corrected (Dean Hickerson noticed that we
forgot the scaling factor 98).
-
Calculation times.
-
The source code for our program.
- The On-Line
Encyclopedia of Integer Sequences is a wonderful resource. It currently
catalogues almost 80000 integer sequences, many with citations and
commentary, and provides a powerful search facility. For sequences related
to the Birkhoff polytope see sequence
A037302.
n = 10
The calculation of the volume of the Birkhoff polytope when n = 10 requires
the evaluation of 4862 integrals.
We started the calculation on March 13, 2002, using between 10 and 40
computers (depending on load).
The last integral was finished on May 18, 2003
The total computer
time,
scaled to a "standard" processor running at 1 GHz, is
6160 days, or
almost 17 years.
And here's the answer:
727291284016786420977508457990121862548823260052557333386607889 / 828160860106766855125676318796872729344622463533089422677980721388055739956270293750883504892820848640000000