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.