I am looking for a reference for explicit families of $d$-regular Ramanujan graphs for fixed $d.$ In particular, I am looking for a family of $d$-regular graphs such that the associated reversible random walk on any such graph has eigenvalues $\lambda_1 = 1\geq \lambda_2\geq \ldots \geq \lambda_k$ with

$$\max_{2\leq i\leq k} |\lambda_i|\leq \frac{2\sqrt{d-1}}{d}~.$$

I want the absolute spectral gap bounded in this way, and therefore bipartite expanders won't do for me (since then, $\lambda_k = -1$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.