Return to Colloquia & Seminar listing
Filliman duality and the volume of the Birkhoff polytope
Student-Run Research| Speaker: | Prof. Greg Kuperberg, Mathematics UC Davis |
| Location: | 593 Kerr |
| Start time: | Wed, May 30 2001, 1:10PM |
Description
The polytope of n x n doubly stochastic matrices, also known as the
Birkhoff polytope, is a convex polytope that often appears in linear
programming and combinatorics, but much of its geometry is unknown.
It is challenging even to compute its volume, which is unknown beyond
n=8. Two methods have been used to find its volume for ``large'' n (7
and 8). The methods are based on counting simplices in a triangulation
and counting lattice points inside the polytope. I will discuss a
third method that uses cotriangulations instead of triangulations.
The cotriangulation method depends on an interesting involution on
polyhedral measures found by the late UC Davis graduate Paul Filliman.
The method also depends on a particular interesting triangulation of
the dual of the Birkhoff polytope. It is ultimately equivalent to a
classification of vertices of a certain transportation polytope due to
Klee and Witzgall.