Israel CS THEORY DAY
Open University of
Division of Computer Science
Date: 17.3.08
Speaker: Nati Linial
Title: Ramanujan Graphs, Lifts
and Word Maps
Abstract:
It is well known that the expansion of a
graph is tightly controlled by its spectral gap. The well-known Alon-Boppana bound says that a d-regular graph must have eigenvalues which are at least as large as 2sqrt(d-1) - o(1). Graphs that meet this bound are called Ramanujan Graphs. There are still many unresolved questions
about the existence of such graphs. In the first part of the talk I will survey
this background material. I will then explain what lifts of graphs are and how
the above questions can be approached using random lifts of graphs. Finally I
will explain the notion of word map which originated in group theory and present
some analysis of formal words that bears on the problems related to spectra of
lifted graphs.
The more recent work explained here is
joint with Doron Puder