Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Daniel Kral - Charles University in Prague

Algorithms for testing FOL properties


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

Karim Adiprasito - FU Berlin

Triangulations of spaces fulfilling curvature bounds

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)

Letzte Aktualisierung: 03.06.2011