Monday, June 12, 2017
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
The Ehrhart polynomial of a lattice polytope P encodes fundamental arithmetic data of P, namely, the number of integer lattice points in positive integral dilates of P. Mirroring Herb Wilf's much-cherished and still-wide-open question which polynomials are chromatic polynomials?, we give a brief survey of attempts during the last half century to classify Ehrhart polynomials. It turns out that this classification problem is related to that of a whole family of polynomials in combinatorics.
We will present some new results for Ehrhart polynomials of zonotopes, i.e., projections of (higher dimensional) cubes. This includes a combinatorial description in terms of refined descent statistics of permutations and a formula in matroidal terms which complements a well-known zonotopal identity of Stanley (1991). Finally, we give a complete description of the convex hull of the Ehrhart coefficients of zonotopes in a given dimension: it is a simplicial cone spanned by refined Eulerian polynomials.
Das Eingemachte in this talk is joint work with Katharina Jochemko (KTH) and Emily McCullough (University of San Francisco).
Colloquium - 16:00
Abstract:
The calculation of the worst possible stretch for a pair of points in
a Delaunay Triangulation is a classical question in computational geometry. The
stretch of a pair of points is defined by the worst length of a shortest path
between those points divided by the Euclidian distance between them. Computing
this shortest path is generally considered as efficient but it is not the case
for very big triangulations. It becomes interesting to only consider local
information at each step while routing from one vertex to the other. Our work
consists in designing an algorithm with this restriction that outputs a path
with a worst stretch of 4.08 (down from 5.9). We will first look at the
different ideas of the study of the stretch in Delaunay triangulations and then
focus on our new routing algorithm.