[home] - [up]

Lectures and Colloquia during the semester

Monday, November 1, 2004

Freie Universität Berlin - Institut für Informatik
Takustraße 9
14195 Berlin
Room 005           - map -
Lecture - 14:15

Jeff Erickson -University of Illinois

Greedy optimal homotopy and homology generators

Abstract: We describe simple greedy algorithms to construct the shortest set of loops that generates either the fundamental group (with a given basepoint) or the first homology group (over any fixed coefficient field) of any oriented 2-manifold. In particular, we show that the shortest set of loops that generate the fundamental group of any oriented combinatorial 2-manifold, with any given basepoint, can be constructed in O(n log n) time using a straightforward application of Dijkstra algorithm. This solves an open problem of Colin de Verdière and Lazarus.

This is joint work with Kim Whittlesey.

Colloquium - 16:00

Ivan Izmestiev -Freie Universität Berlin

On the hull number of torus links

Abstract: The n-th hull of a union of curves in R^3 is the set of points with the property: Any plane passing through the point intersects the curves at least 2n times. The hull number u(L) of a link L is defined as the minimum number of non-empty hulls a representative of L can have. In the talk we will show that the hull number of torus links (links that can be drawn on an unknotted torus) is smaller than expected, but still large. In particular, for a link of type (p,p) it is equal to 3p/5, and in general for the type (p,q) with q>p it is greater than or equal to p/2.

[home] - [up] - [top]