[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - November 25th 2019

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our Monday Lecture & Colloquium on November 25th at 14:15 h & 16:00 h at FU Berlin.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, November 25th - 14:15 h

Lecture: Georg Loho (London School of Economics and Political Science)

Title: Signed tropical convexity

Abstract:

Convexity for the max-plus algebra has been studied from different directions including discrete geometry, scheduling, computational complexity. As there is no inverse for the max-operation, this used to rely on an implicit non-negativity assumption. We remove this restriction by introducing `signed tropical convexity'. This allows to exhibit new phenomena at the interplay between computational complexity and geometry. We obtain several structural theorems including a new Farkas lemma and a Minkowski-Weyl theorem for polytopes over the signed tropical numbers. Our notion has several natural formulations in terms of balance relations, polytopes over Puiseux series and hyperoperations.

Coffee & Tea Break:
Room 134

Time: Monday, November 25th - 16:00 h s.t.

Colloquium: Manfred Scheucher (Technische Universität Berlin)

Title: Topological Drawings meet SAT Solvers and Classical Theorems of Convex Geometry

Abstract:

In a simple topological drawing of the complete graph $K_n$, vertices are mapped to points in the plane, edges are mapped to simple curves connecting the corresponding end points, and each pair of edges intersects at most once, either in a common vertex or in a proper crossing. We discuss an axiomatization of simple drawings and for various sub-classes and present a SAT model. With the aid of modern SAT solvers, we investigate some famous and important classical theorems from Convex Geometry (such as Caratheodory’s, Helly's, Kirchberger's Theorem, and the Erdös-Szekeres Theorem) in the context of simple drawings. This is joint work with Helena Bergold, Stefan Felsner, Felix Schröder, and Raphael Steiner. Research is in progress.