[home] - [up]


Lectures and Colloquia during the semester



Monday, May 12, 2003

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 042           - map -
Lecture - 14:15

Anders Björner -KTH Stockholm

Blockers, subspace arrangements and ideals

Abstract: The blocker of a set family A is the collection of inclusionwise minimal sets that intersect all sets in A. This construction is well-known in combinatorics and combinatorial optimization. The corresponding construction on set partitions (and more generally on geometric lattices) arises in the study of vanishing ideals of arrangements of linear subspaces in a vector space.

I will survey examples and properties of blocker duality from a combinatorial viewpoint. I will then describe the relevance of this concept for ideals that are generated by products of linear forms. In particular, an algorithm for deciding if an ideal is generated by products of linear forms is given.

The talk is based on joint work with I. Peeva and J. Sidman.


Colloquium - 16:00

Sergi(o) Cabello -University of Utrecht

Testing Homotopy for Paths in the Plane

Abstract: We present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For paths specified by n line segments with obstacles described by n points, several standard ways achieve quadratic running time. For simple paths, our algorithm runs in O(nlogn) time, which we show is tight. For self-intersecting paths the problem is related to Hopcroft's problem; our algorithm runs in O(n^{3/2}\log n) time.

The talk is based on joint work with Yuanxin Liu, Andrea Mantler, and Jack Snoeyink


[home] - [up] - [top]