Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, December 14, 2015

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Benjamin Nill - Otto-von-Guericke-Universität Magdeburg

Ehrhart theory - quo vadis?

A lattice polytope is a polytope whose vertices all lie in the integer lattice. Over 50 years ago, it was shown by Ehrhart that counting integer points in dilates of a lattice polytope leads to a polynomial function. The study of these Ehrhart polynomials of lattice polytopes is nowadays sometimes referred to as Ehrhart theory. In this talk I will try to give a (very incomplete) survey of recent research in Ehrhart theory and present some challenging open questions.

Colloquium - 16:00

Tillmann Miltzow - Hungarian Academy of Science, Budapest

Peeling the Cactus or how to count Triangulations in subexponential time

Joint with Daniel Marx.

Given a set of n points S in the plane, a triangulation T of S is a maximal set of non-crossing segments with endpoints in S. Let t(S) denote the number of all triangulations of S. We present an algorithm that computes t(S) in nO(√n) time. This improves over the previous best algorithm of Alvarez and Seidel with a running time O(2n • n2) [SoCG 2013].

Given a triangulation T, we define a decomposition of T into disjoint nested cactus-graphs. Our main tool is to use this decomposition to identify small separators in an unique way.

Using techniques developed in previous papers, we will demonstrate, how our algorithm can be adopted to solve also 'decomposable' problems. We will also argue that our algorithm can be adopted to count other geometric structures as cycle-decompositions, perfect matchings, etc.

If time permits, we will argue that a considerable improvement on the running time requires different techniques to the ones used so far in the literature.

Letzte Aktualisierung: 08.12.2015