Gaps Between Almost-Primes and a Construction of Almost-Ramanujan Graphs

For all $k\ge 3$, we show how one can explicitly construct an infinite family of $k$-regular graphs all of which have second largest eigenvalue satisfying the bound $O(k^{1\mathrm{/}2})$. This resolves an open problem of Reingold, Vadhan and Wigderson.