# Ramanujan Graphs and Random Walks on Trees

## ABSTRACT

An infinite sequence of finite regular graphs of a fixed degree $k$ is called a family of {\it expanders} if the eigenvalue gap of every graph in the sequence is bounded away from $0$ by a constant which depends only on $k$. Explicit constructions of such families have found extensive use in efficient planning of networks and other applications.

The best possible exapnders are called {\it Ramanujan graphs}. The main open problem about Ramanujan graphs is the existence of infinite families of Ramanujan graphs of fixed degree $k$, for every $k\geq 3$.

An introduction into Ramanujan graphs will be given in the first part of the talk. In the second part of the talk I will report on a joint work with Alex Lubotzky in which we study the problem of existense of infinite families of Ramanujan graphs in the class of all finite (not necessarily regular) graphs.

I will also report on some results on random walks on infinite trees which allow to decide algorithmically whether a given finite graph is Ramanujan.

The talk should be accessible to a broad audience.

Speaker's Contact Info: tatiana(at-sign)math.kth.se