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.

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:

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