Elementary constructions of expander graphs using algebraic graph theory

science. On the one hand, they can be helpful to construct "optimal"
networks. On the other hand, they were used in the analysis of
several algorithms as computation graphs to prove lower time
bounds. However, only few explicit constructions of these graphs are
known and most of them rely on algebraic theories. These lectures
aim at showing how tools from group theory and number theory can
be used in the construction of expander graphs.

We will first review the basic concepts of spectral graph theory. We
show how expansion properties of a graph are related with its
spectrum (that is, the eigenvalues of its adjacency matrix and
similiar operators). We will introduce the zeta function of a graph
G and study its relation to certain invariants of G like the genus
or the number of spanning trees of G.

Algebraic graph theory deals with algebraically or arithmetically
defined graphs. Most of them are given as Cayley-graphs of
arithmetical groups or as quotients of similar groups acting on
trees. For a certain family of these graphs, we give an algorithmic
description of the zeta function that leads (in special cases) to
explicit formulas. We finally exploit the strong connections between
the spectrum of a graph and its zeta function to prove very good
expansion properties of these graphs.

The lectures will be self-contained. The audience is only assumed to
be familiar with notions of elementary (linear) algebra.

(Follow-up lecture on October 23.)