Monday, June 6, 2011
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
room 3.113 (Haus 3, 1. Etage)
Lecture - 14:15
Algorithmic metatheorems guarantee that certain types of
problems have efficient algorithms. A classical example
is the theorem of Courcelle asserting that every MSOL
property can be tested in linear time for graphs
with bounded tree-width. Another example is a result of
Frick and Grohe that every FOL property can be tested
in almost linear time in graph classes with locally
bounded tree-width. Such graph classes include planar
graphs or graphs with bounded maximum degree. An example
of an FOL property is the existence of a fixed graph
as a subgraph.
We extend these results in two directions:
* we show that FOL properties can be tested in linear time for classes of graphs with bounded expansion (this is a joint work with Zdenek Dvorak and Robin Thomas), and
* FOL properties can be polynomially tested (with the degree of the polynomial independent of the property) in classes of regular matroids with locally bounded branch-width (this is a joint result with Tomas Gavenciak and Sang-il Oum).
In the talk, we will define all the above mentioned notions, present their mutual relation and sketch the main ideas behind our algorithms. An alternative proof of our first result was obtained by Dawar and Kreutzer.
Colloquium - 16:00
Marston Morse examined a smooth manifold X by looking at critical values of a generic differentiable real-valued function on X. Similarly, Forman examined a simplicial complex C by looking at critical cells of order-preserving functions on the face poset of C. These two theories are very useful tools in various branches of mathematics. It is desirable to choose the functions in such a way that they are not more complicated than the topology requires. Simplicial balls that allow such a function are called collapsible. In contrast to the smooth case (where all balls admit `simple' smooth function), not all simplicial balls are collapsible.
In this lecture we want to translate a classical theorem from differential geometry to the language of simplicial complexes. If a metric length space has nonpositive curvature, and it is simply connected, then it is even contractible (Hadamard-Cartan-Alexandrov). We show that if on a simplicial complex there is a metric fulfilling with nonpositive curvature in the Cartan-Alexandrov-Topogonov sense, and in addition the star of every vertex is geodesically convex, then the ball is collapsible. This is the first time that a result of this type can be proven in dimension greater than 3.
(Joint work with Bruno Benedetti)