Hauptseminar (S2C2): Spectral Graph Theory and Applications

The course will focus on connections between combinatorial structures in graphs and algebraic properties of the associated matrices, as well as their algebraic applications. The eigenvalues of the adjacency matrix and other associated matrices reveal structural information on connectivity and the mixing time of random walks. They also lead to natural methods for graph drawing, clustering, sparsifying graphs, and enable us to construct expander graphs, a key tool in algorithm design and coding theory. 


The seminar will  mainly follow the manuscript ``Spectral and Algebraic Graph Theory'' by Daniel Spielman available at http://cs-www.cs.yale.edu/homes/spielman/sagt/sagt.pdf  
We will cover a selection of topics from the book. 


Required background: V2C1 Einführung in die Diskrete Mathematik

You can find the slides from the planning meeting here. For any questions, contact László Végh at lvegh@uni-bonn.de

Dates

Pre-meeting: 

Tuesday, 3rd February, 2026, 18:00 s.t.
Gerhard-Konow-Hörsaal, Lennéstr. 2

Class hours:

Friday 14:15-15:45. Approval talks: 16:15-17:45 

Rules and Regulations

  • Seminars will be held Friday 14:15-15:45, with approval talks on the same days 16:15-17:45.
  • The seminar will be held in English.
  • A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
  • The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
  • Each participant has to write a summary consisting of one or two pages.
  • Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.

Schedule

17.04.2026: Intro session 1: Basics and Chapter 10 — Wenzheng Li
24.04.2026: Intro session 2: Basics and Chapter 10 — Haoyuan Ma
08.05.2026: Chapter 11: Walks, springs, resistor networks —Nils Hermann
15.05.2026: Chapter 12: Effective resistance — Sönke Schneider 
22.05.2026: Chapter 13: Random spanning trees — Meike Schumm
12.06.2026: Chapters 20-21 Graph partitioning and Cheeger’s inequality — Bogdan Miziuk 
19.06.2026: Chapter 22 Local graph clustering — Lars Johannsen 
26.06.2026: Chapter 32 Sparsification by random sampling —Wenzheng Li
03.07.2026: Chapter 33 Linear sized sparsifiers — Finn Rudolph