Instructor: Dr. László Lovász
This course is intended for Master's students. The language of instruction is English.
This semester the main topic is
The study of random walks on finite graphs (closely related to the theory of finite Markov chains) has a long history and a lot of recent applications in algorithm design, simulation, statistical physics and other fields. The computation and estimation of basic quantities is central to these applications. How long does it take (in expectation) to reach a given node? How long before all nodes are visited? After how many steps will we lose all information about the starting position and be anywhere with almost the same probability?
Answers to such questions takes us to linear algebra, the spectrum of graphs, and to algorithms for counting colorings of graphs, for estimating the volume of a convex body, and (time permitting) to better understandin phenomena in statistical physics.