Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The computation of Ehrhart polynomials of matroid polytopes

Algebra & Discrete Mathematics

Speaker: Matthias Koeppe, Universitaet Magdeburg / UC Davis
Location: 1147 MSB
Start time: Mon, Oct 8 2007, 4:10PM

We show the polynomial-time computability of Ehrhart polynomials for matroid polytopes, matroid base polytopes, and polymatroids, whenever the rank function is bounded by an arbitrary constant.

This result complements other complexity results, like the polynomial-time computability of the highest k (fixed) coefficients of the Ehrhart (quasi-)polynomials of rational simplices in varying dimension (Barvinok 2005).

The proof relies on the following new techniques:

1. a polynomial-time construction of a triangulation of the vertex cones of the polytopes into half-open simplicial unimodular cones

2. a technique to turn a triangulation into an exact partition of half-open cones

3. a polynomial-time specialization algorithm of multivariate rational generating functions in varying dimension

Based on unpublished joint work with Jesus De Loera and David Haws and my paper arXiv:0705.3651 [math.CO] (with Sven Verdoolaege).