The spring semester 2021 will certainly take place online until Easter. Exceptions: Courses that can only be carried out with on-site presence. Please note the information provided by the lecturers.
The course will present the basic theory and selected applications of expander graphs. It will develop the general idea of expansion of graphs and the different formulations of expanding graphs. The existence of expanding graphs will then be established using both probabilistic and deterministic methods. Applications to number theory, geometry and theoretical computer science will be described.
Objective
Content
The course will present the basic theory and selected applications of expander graphs. It will first develop the general idea of expansion of graphs and the different formulations of expanding graphs. The existence of expanding graphs will then be established using both probabilistic and deterministic methods (including a discussion of the recent work on expansion of finite linear groups). Applications to number theory, geometry and theoretical computer science will be described.
Lecture notes
Lecture notes will be available.
Literature
Hoory, Linial and Wigderson: Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), 439-561
Prerequisites / Notice
Prerequisites: Measure and integration, algebra I + II.
