# MAT952 Expander graphs (HS21)

Lecturer: Dr. Johannes Schmitt
Time and Place: Thursday, 10:15 - 12:00, Room Y17H05
Further information can be found in the UZH Course Catalogue.

Content

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.

List of talks

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

Requirement for passing

In order to pass the seminar and get credit points, you have to:

• give a talk from the above list to the remaining participants; the length of the talk should be about 90 minutes, the language of the talk is English
• hand in a written part towards the end of the semester; this should be written in LaTeX and can be a summary of the talk or solutions to exercises in the part of the script you are discussing
• attend (most of) the talks of the other participants
There is no grade for the seminar, so it is simply pass/fail.

LaTeX formulas on this site powered by MathJax Back to Johannes Schmitt's homepage