Ramanujan Graphs and Random Walks on Trees

Tatiana Smirnova-Nagnibeda

Royal Institute of Technology, Stockholm

March 12,
refreshments at 3:45pm


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

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on February 26, 2003 at 02:22 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.