(Pro)Seminar Graphentheorie

• Interessentenkreis: Studierende nach dem 3. Semester
• Dozent: Thomas Schick
• Termin: Dienstag, 14:15-15:55 (Vorschlag)
• Kontakt: schick@uni-math.gwdg.de, Tel. 397766, Raum 201

Graphen sind grundlegende mathematische Objekte. Sie haben viele praktische Anwendungen (Netzwerke, Transportprobleme, Datenverarbeitung, insbesondere Bezug zur Informatik), aber sind auch rein innermathematisch sehr wichtig.

Im Seminar sollen eine Reihe klassischer Probleme der Graphengheorie und deren Lösungen, sowie wichtige Klassen von Graphen in der Mathematik vorgestellt werden. Wir werden:

• in die Grundbegriffe der Graphentheorie einführen
• das Eulerproblem lösen (Graphen in einem Zug zeichnen)
• das Einbettungsproblem lösen (welche Graphen passen ohne Überkreuzungen in die Ebene)
• reguläre Polyeder mit Hilfe ihres Kantengraphen klassifizieren
• das Färbungsproblem diskutieren: wieviele Farben braucht man zum Färben einer Landkarte
• das matching-Problem studieren
• Expander-Graphen studieren: wie kann man die Konnektivität eines Graphen messen; hier wird ein Bezug zur Spektraltheorie des Graphen-Laplace-Operators hergestellt. Existenz, Konstruktion, Anwendungen von Expandergraphen (mehrere Vorträge).
• Cheeger-Dodziuk-Ungleichung zwischen Eigenwert der Nachbarschaftsmatrix und isoperimetrischer Konstante eines Graphen [6, Section 4].
• Margulis explizite Konstruktion von Expandergraphen
• (zufällige) Irrfahrten auf Graphen und ihre Eigenschaften
• Cayley-Graphen definieren und ihre wichtigsten Eigenschaften studieren (polynomiales Wachstum/exponentielles Wachstum, Eigenschaft T?) ([1, Kapitel 3], [6, Section 11], [4, Chaper 15], [8, Chapter 1]).
• Transportprobleme in Graphen studierenDurchfluss und Begrenzung (min cut-max flow) (Ford-Fulkerson, Grieser Sec 2)

Seminarprogramm

Thema	Quelle	Gebiet
Grundlagen und Bäume	[5, 1.1,1.3]	Kombinatorik, Algorithmik
Eulergraphen (ev. auch Hamiltongraphen)	[5, 1.4], [2, 1.8, 10]	Algorithmik
planare Graphen	[5, 1.5], [2, 4]	Kombinatorik, Topologie
Reguläre Polyeder und einfache Polytope	[5, 1.5.3], [2, 3.4]	Geometrie
Fünf-Farben-Satz	[5, 1.6], [2, 5.1]	Kombinatorik, Topology
(perfekte) matchings	[5, 1.7], [2, 2]	Kombinatorik
Isoperimetrie und Graph-Laplace	[6, Section 4]	Lineare Algebra, Analysis
magische Graphen, Existenz, Codes	[6, 1.1.2,1.2,1.3.2]	Kombinatorik, Informatik
Expandergraphen, Spektrum	[6, 2]	Kombinatorik
Irrfahrten auf (Expander)graphen	[6, 3.1,3.2]	W-Theorie
Cayley-Graphen und Eigenschaften (polynomiales Wachstum/exponentielles Wachstum, Eigenschaft T?)	[1, Kapitel 3], [6, Section 11], [4, Chaper 15], [8, Chapter 1]	Gruppentheorie, Geometrie
Margulis explizite Konstruktion von Expandergraphen	[6, Section 8]	Gruppentheorie, lineare Algebra
Transport in Graphen (min cut/max flow)	[7, 8.1][3]	Algorithmik, Analysis

Bibliography

1

Thorsten Camps, Volkmar große Rebel, and Gerhard Rosenberger.
Einführung in die kombinatorische und die geometrische Gruppentheorie, volume 19 of Berliner Studienreihe zur Mathematik [Berlin Study Series on Mathematics].
Heldermann Verlag, Lemgo, 2008.

2

Reinhard Diestel.
Graph theory, volume 173 of Graduate Texts in Mathematics.
Springer, Heidelberg, fourth edition, 2010.

3

L. R. Ford, Jr. and D. R. Fulkerson.
Maximal flow through a network.
Canad. J. Math., 8:399-404, 1956.

4

Jonathan L. Gross and Jay Yellen.
Graph theory and its applications.
Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, second edition, 2006.

5

John M. Harris, Jeffry L. Hirst, and Michael J. Mossinghoff.
Combinatorics and graph theory.
Undergraduate Texts in Mathematics. Springer, New York, second edition, 2008.

6

Shlomo Hoory, Nathan Linial, and Avi Wigderson.
Expander graphs and their applications.
Bull. Amer. Math. Soc. (N.S.), 43(4):439-561 (electronic), 2006.

7

Bernhard Korte and Jens Vygen.
Combinatorial optimization, volume 21 of Algorithms and Combinatorics.
Springer, Heidelberg, fifth edition, 2012.
Theory and algorithms.

8

John Meier.
Groups, graphs and trees, volume 73 of London Mathematical Society Student Texts.
Cambridge University Press, Cambridge, 2008.
An introduction to the geometry of infinite groups.