Lecturer: Dr. Johannes Schmitt
Time and Place: Thursday, 10:15 - 12:00, Room Y17H05
Further information can be found in the UZH Course Catalogue.
A graph is a mathematical object consisting of a set of vertices, connected by a number of edges. Graphs have many applications in mathematics (e.g. in combinatorics, topology, ...) but they also have real life applications. For instance, an example of a graph could be the set of ZVV stations in Zurich (vertices) connected by various trams and buses (edges).
In many applications, we would like to connect a given set of vertices using only few edges, but still having e.g. short travel times between any two vertices. Expander graphs are families of graphs having such a high "connectivity" combined with a small total number of edges. The study of such expander graphs is an active area of research, with applications ranging from network design and probabilistic algorithms to geometry and number theory.
In the seminar, we will start with an introduction to some basic graph theory, followed by the definition and properties of expander graphs specifically (where we see what methods from Linear Algebra can tell us about a random walk on a graph). Next we discuss various explicit constructions for expander graphs, using methods from either probability or group theory. Time permitting, we will also discuss applications of expander graphs.
Here you find a preliminary list of topics for the talks.
Here is the preliminary assignment of topics and dates:
Topic | Date | Student |
---|---|---|
Introduction to graphs | 23.09 | Irena Syla |
Basic properties of graphs | 30.09 | Rathes Sriram |
Cayley graphs, action graphs, Schreier graphs | 07.10 | Keerthiga Rajakumar |
Expansion in graphs | 14.10 | Praveena Premananthan |
Digression: Finite Markov chains | 21.10 | Xuelun Schmid |
Random walks | 28.10 | Florin Zahiri |
Random walks II | 04.11 | Jennifer Chan |
Random walks and expansion | 11.11 | Joel Zülle |
The discrete Laplace operator and expansion of Cayley graphs | 18.11 | Corina Spreiter |
Exercise class | 25.11 | Jessica Lam Jia Hong |
Existence of expanders I | 02.12 | Vigan Dautaj |
Existence of expanders II | 09.12 | Philipp Moor |
Applications of expanders I | 16.12 | Chiara Aruanno |
Applications of expanders II | 23.12 | Therese Hauser |
In order to pass the seminar and get credit points, you have to: