Description

An introduction to expander graphs

Expander graphs are families of finite graphs that are simultaneously relatively sparse and highly connected. Since their discovery in the lates 1960s, they have appeared in many seemingly unrelated areas of mathematics, from theoretical computer science to arithmetic and algebraic geometry, from representation theory to number theory.

The goal of this book is to present the theory of expander graphs and to explore some of these rich connections. Besides a careful exposition of the basic parts of the theory, including the Cheeger constant, random walks and spectral gap characterizations of expander graphs, it contains many different constructions of various families of expander graphs. The applications that are suveyed in the last chapter try to communicate the remarkable reach of expander graphs in modern mathematics.