Ramanujan Graphs and Random Walks on TreesTatiana SmirnovaNagnibedaRoyal Institute of Technology, Stockholm
March 12,

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. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

