UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Computing the continuous discretely: the quest for the volume of the Birkhoff polytope

Algebra & Discrete Mathematics

Speaker: Dr. Matthias Beck, SUNY Binghamton
Location: 693 Kerr
Start time: Thu, Nov 21 2002, 12:00PM

Abstract: The \emph{$n^{\text{th}}$ Birkhoff polytope} $B_n$ is the set of all \emph{doubly stochastic} $n \times n$ matrices, that is, those matrices with nonnegative real entries in which every row and column sums to one. A famous open problem concerns the volume of $B_n$, which is only known up to $n=9$. The \emph{Ehrhart polynomial} of a polytope with integral vertices counts the integer points in the polytope as it gets dilated by an integer factor. One reason for being interested in this counting function is that its leading term gives the volume of the polytope. We will present a novel way of computing Ehrhart polynomials for polytopes using complex-analytic methods. En route to their application to the Birkhoff polytope, we will introduce ideas and concepts from discrete geometry, number theory, and combinatorics. The application of our methods to the Birkhoff polytope provides an example showing that pure mathematics and computationally efficient algorithms are not mutually exclusive.