__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**