Seminar Geometrie: Graphentheorie

Christian Bär

Sommersemester 2010

Das Seminar behandelt Graphen, kombinatorisch-geometrische Objekte, die z.B. Netzwerke oder Moleküle beschreiben. Solche Netzwerke können schwingen, wobei die auftretenden Frequenzen durch die so genannten Eigenwerte des Graphen gegeben sind. Im Seminar werden diese Eigenwerte untersucht und mit der Geometrie des Graphen in Verbindung gebracht.

Bei der Vorbereitung gibt es Hilfestellung durch den Tutor Frank Pfäffle. Jede(r) Vortragende erstellt ein Handout, das zu Beginn des Vortrags an alle Hörer verteilt wird. Das Handout ist in LaTeX zu erstellen; eine Schablone findet sich hier. Jede(r) Vortragende bespricht ihre/seine Vortragskonzeption spätestens eine Woche vor dem Vortrag mit dem Tutor. Das Handout ist vorher per E-Mail einzureichen.


Preisaufgabe:

Beweise oder widerlege durch Gegenbeispiel:

{tex}\noindent Sei $G$ ein endlicher Graph mit mindestens 4 Knoten und sei $H$ der gewichtete Graph, der aus $G$ durch Identifikation zweier Knoten hervorgeht. Dann gilt: $$\lambda_2(G) \leq \lambda_2(H).$${/tex}

Unter allen korrekten, bis zum Dienstag, den 18.5.2010 (Abgabetermin verlängert!), bei Frank Pfäffle eingereichten Lösungen wird ein Buchpreis verlost. Der Rechtsweg ist ausgeschlossen.

Vorbesprechung:

Vorstellung der einzelnen Vortragsthemen und Vergabe der Vorträge an die Interessenten findet statt am Mittwoch, dem 3. Februar 2010, 15:15 Uhr, in Haus 8, Raum 0.53.

Wann:

Mittwoch, 12:15-13:45 Uhr

Wo:

Haus 8, Raum 0.59

Seminarplan (Vorträge):

siehe unten

Semester (empfohlen):

ab 3. Semester

Modulnummern:

621, 631, 651, 661

Erforderliche Vorkenntnisse:

Grundvorlesungen über Lineare Algebra. Das Konzept von Eigenvektoren und Eigenwerten muss man verstanden haben.

Handouts:

  1. Einführung in Graphen und ihre Eigenwerte [Chung, S.2-6]: Einführung von Graphen, ihrem Laplace-Operator und dessen Eigenwerte. Beispiele 1.1 bis 1.6 ausführlicher erläutern. Bemerkungen über Homologie und riemannsche Mannigfaltigkeiten ignorieren. Für einige Definitionen kann auf [Bollobas] oder [Diestel] zurückgegriffen werden.
  2. Eigenschaften des Spektrums eines Graphen [Chung, S. 6-11]: Verschiedene Eigenwertabschätzungen. Lemma 1.14 angeben, für den Beweis auf den folgenden Vortrag verweisen.
  3. Eigenwerte gewichteter Graphen [Chung, Abschnitt 1.4]: Lemma 1.14 und 1.15 ausführlich beweisen.
  4. Eigenwerte und Zufallswege I [Chung, Abschnitt 1.5 bis einschließlich Theorem 1.16]: Ein Zufallsweg ist der Weg eines Betrunkenen, der auf dem Graphen entlangspaziert und bei jeder Ecke die Wahl der weiteren Richtung dem Zufall überlässt. Ergodizität, Grenzverteilung, Abschätzung der Konvergenz gegen die Grenzverteilung durch die Eigenwerte. Für diesen Vortrag ist es nicht unbedingt erforderlich, bereits eine Vorlesung über Wahrscheinlichkeitstheorie gehört zu haben, aber hilfreich ist es schon.
  5. Eigenwerte und Zufallswege II [Chung, S.18 Mitte - 21]: Fortsetzung des Vortrag über Eigenwerte und Zufallswege
  6. Die Cheeger-Ungleichung [Chung, Abschnitte 2.2 und 2.3]: Definition der Cheeger-Konstante und Abschätzung des ersten Eigenwerts.
  7. Charakterisierung der Cheeger-Konstante [Chung, Abschnitte 2.4 und 2.5]: modifizierte Cheeger-Konstante, Charakterisierung der Cheeger-Konstante durch eine Art "Rayleigh-Quotient".
  8. Kartesische Produkte [Chung, Abschnitt 2.6]: kartesische Produkte von Graphen, ihr Spektrum, isoperimetrische Ungleichung
  9. Durchmesser und Eigenwerte [Chung, Abschnitte 3.1 und 3.2]: Durchmesser eines Graphen, Eigenwerte und Abstand von Teilgraphen
  10. Expander-Graphen [Chung, Abschnitt 6.2]: Expander-Graphen sind solche, bei denen die Ecken mit vielen anderen verbunden sind. Abschätzungen für das "Nachbarschafts-Verhältnis"
  11. Explizite Konstruktionen: [Chung, Abschnitt 6.3]: Paley-Graphen, Margulis-Graphen, Ramanujan-Graphen
  12. Anwendungen auf Kommunikations-Netzwerke: [Chung, Abschnitt 6.4]

Literatur:

  1. B. Bollobas: Extremal Graph Theory, Academic Press 1978
  2. F. Chung: Spectral Graph Theory, Amer. Math. Soc. 1997 (die korrigierten ersten Kapitel hier frei erhältlich)
  3. R. Diestel: Graph Theory, 3. Aufl., Springer-Verlag 2005 (freie elektronische Version hier)