A d-regular graph is Ramanujan if its non-trivial eigenvalues in absolute value are bounded by 2√(d-1). By means of number-theoretic methods, infinite families of Ramanujan graphs were constructed by Margulis and independently by Lubotzky-Phillips-Sarnak in 1980’s for d=q+1, where q is a prime power. The existence of an infinite family of Ramanujan graphs for arbitrary d has been an open question since then. Recently Adam Marcus, Daniel Spielman and Nikhil Srivastava gave a positive answer to this question by showing that any bipartite d-regular Ramanujan graph has a 2-fold cover that is also Ramanujan. In this talk we shall discuss their approach and mention similarities with function field towers.
This video was produced by CIRM as part of the conference Arithmetic, geometry, cryptography and coding theory.
