240603 Algebraische Graphentheorie und Komplexitätstheorie (V) (WiSe 2011/2012)

Die Vorlesung setzt die Vorlesung Graphentheorie des SoSe 2011 fort und bereitet ein Bachelorarbeitsseminar im SoSe 2012 vor, das maximal 15 Teilnehmer haben kann.

Zunächst wird es in der Vorlesung um Komplexitätstheorie gehen, genauer um NP-vollständige Probleme. Hierbei wird zunächst die NP-Vollständigkeit des Belegbarkeitsproblems der Aussagenlogik bewiesen werden. Darauf aufbauend werden NP-vollständige Graphentheorie-Probleme, wie das 3-Färbbarkeitsproblem und das Hamiltonkreis-Problem diskutiert werden.

Anschließend wird es um algebraische Graphentheorie gehen. Das beinhaltet zum einen eine kategorielle Heransgehensweise, mit der etwa Färbbarkeit von Produkten diskutiert werden kann. Die kategorielle Herangehensweise erlaubt aber auch die Reduktion graphentheoretischer Fragestellungen auf NP-vollständige Probleme.

Zum anderen kann man man Lineare Algebra einsetzen, um Eigenwert-Spektren von Graph-Matrizen zu untersuchen. Weiterhin kann man Graphen Polynome zuordnen, die Grapheigenschaften widerspiegeln, wie etwa das chromatische Polynom. Hierbei gibt es auch einen Zusammenhang zur Knotentheorie.

Abschließend wird es um den Zusammenhang zwischen Graphen- und Gruppentheorie gehen, insbesondere Gruppenpräsentationen und Freiheit von Gruppen, indem man Gruppenoperationen auf Graphen studiert. Hierbei spielen Cayley-Graphen eine wesentliche Rolle.

Teilnahmevoraussetzungen, notwendige Vorkenntnisse

Notwendig: Die Vorlesung Graphentheorie des SoSe 2011, Lineare Algebra I+II
Hilfreich: Algebra I

Externe Kommentarseite

http://www.math.uni-bielefeld.de/~mseverit/AGT