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).