# Jerusalem Mathematics Colloquium

Thursday, 25th March 2004, 4:00 pm

Mathematics Building, Lecture Hall 2

##

Professor Nati Linial

(Hebrew University)

"A new simple approach to Ramanujan Graphs"

** Abstract: **
The study of expander graphs can be put in the following
very general framework - To what extent can finite d-regular
graphs behave like the infinite d-regular tree? The tree T
is the ultimate expander, since for every finite set of
vertices S in T, at most only |S|-1 of the edges incident with
the vertices in S stay inside S. It is a basic fact in this
area that expansion goes hand-in-hand with a large spectral
gap in the graph's incidence matrix. Again one could ask
if finite graphs can exhibit spectral behavior akin to what
we find in the infinite T.

Finite graphs with this property, having the largest possible
spectral gap are called Ramanujan Graphs. Constructions
of such graphs are so far based on fairly deep number theory
or representation theory. The challenge of constructing
such graphs using elementary methods is still open. In this
talk I will describe a recent work in this direction.

This is a joint work with Yonatan Bilu.

Light refreshments will be served in the faculty lounge at 3:30.

List of talks, 2003-04

List of talks, 2002-03

List of talks, 2001-02

List of talks, 2000-01

List of talks, 1998-99

List of talks, 1997-98