Abstract: Die Minorentheorie von Robertson und Seymour beginnt mit der Beschreibung besonders einfach strukturierter Graphen: solcher, die "aus der Ferne etwa wie ein Weg aussehen". Nicht alle Graphen sind von dieser Art, haben eine Wegzerlegung in kleine Teile. Aber unter denen, die nicht so sind, gibt es minimale: alle Graphen ohne Wegzerlegung in kleine Teile enthalten grosse binäre Bäume als Minoren (die selbst keine solche Wegzerlegung haben). Als nächste Komplexitätsstufe werden dann Graphen betrachtet, die zwar keine Wegzerlegung aber doch eine Baumzerlegung in kleine Teile haben, also "aus der Ferne etwa wie ein Baum aussehen". Unter den Graphen, die nicht von dieser Art sind, gibt es wiederum Minoren-minimale: die Gitter. Wie aber geht es weiter? Können wir sinnvoll als nächste Hierarchieschicht Graphen mit "Gitterzerlegungen" in kleine Teile identifizieren? Gibt es dann wieder minimale Graphen "unbeschränkter Gitterweite", und so weiter? Der Vortrag stellt einen Ansatz vor, wie wir die endlichen Graphen in einer solchen mit der Minorenrelation verträglichen Komplexitäts-Hierarchie ordnen können. Sind die Schichten dieser Hierarchie einmal bestimmt, so lassen sich dann geeignete Probleme - abstrakter oder auch algorithmischer Art - vielleicht dort einordnen oder induktiv lösen, ganz wie es mit den Graphenklassen beschränkter Weg- oder Baumweite bereits geschieht. Dieser Prozess steht jetzt ganz am Anfang: noch ist die Bestimmung selbst der ersten nicht-trivialen Schichten ein offenes Problem!
Colloquium - 16 Uhr s.t.
Abstract: What is the curvature of the cube? Or of the tetrahedron? Maybe you have asked this question once or twice in your lifetime. And decided this question does not make any sense at all. Actually, quite a few people worked on this problem and as a consequence, we have different answers, each making sense in its context. In my talk, I want you to get acquainted with Robin Forman's notion of Ricci curvature, which is a combinatorial invariant with interesting properties. Even more: I promise that you will be able to compute the Ricci curvature of all platonic solids easily after the talk (or even during the talk, if I start to bore you). Besides, you will get an idea how Robin Forman approached the subject, what type of results he derived from his axiomatic point of view, and finally I shall sketch how his axiomatics can be justified.