Monday, June 6, 2011
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room 3.113 (Haus 3, 1. Etage)
Lecture - 14:15
Abstract:
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
Abstract:
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)