Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.