Almost-Ramanujan graphs and prime gaps

The method of Murty and Cioabă shows how one can use results about gaps between primes to construct families of almost-Ramanujan graphs. In this paper we give a simpler construction which avoids the search for perfect matchings and thus eliminates the need for any computational effort. A couple of known bounds on the gap between consecutive primes are then used to give the construction of kk-regular families with lower bounds on the spectral gaps. We then show that a result of Ben-Aroya and Ta-Shma can be improved using our simpler construction though on the assumption of the Riemann Hypothesis; this sheds some more light on a question raised by Reingold, Vadhan and Widgerson.