AG 1, AG 2, AG 3, AG 4   Info

AG Audience

-- Not specified --

Saarbrücken

Die Entscheidungskomplexität von monotonen Grapheigenschaften (z.B. nicht zusammenhängend) auf fester Eckenmenge im Berechnungsmodell ``binärer Entscheidungsbaum'' ist nach einer Vermutung, die auf Karp zurückgeht, immer maximal (d.h. der Baum hat maximale Höhe). In Arbeiten von Kahn, Saks, Sturtevant und Forman hat sich gezeigt, daß in diesem Berechnungsmodell homologische Invarianten eng mit der Komplexität interagieren. Wir führen in diesem Vortrag in dieses Themenfeld ein und zeigen wie die homologischen Invarianten von monotonen Grapheigenschaften, die zur Bestimmung unterer Schranken der Komplexität herangezogen werden können, auch an zentralen Stellen in der reinen Mathematik eine Rolle spielen (Knoteninvarianten, kommutative Algebra, Gruppentheorie, etc.).

Christian Schulte

--email hidden

passcode not visible

logged in users only