<p>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 </p>

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

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

CC BY-SA 3.0
2015-12-27T13:50:02.860Z
have you checked the survey http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf? see section 5.3.
Sasho Nikolov
CC BY-SA 3.0
2015-12-30T04:50:50.503Z
You might want to check out constructions by Lubetzky et al and Margulis. The references are mentioned in http://arxiv.org/pdf/1304.4132v2.pdf. AFAIK explicit families of non bipartite Ramanujan expanders for every degree 'd' are not known.
NAg
<expanders>
Explicit Ramanujan graph families (Reference Request)
user7823
# Explicit Ramanujan graph families (Reference Request)

(Asked by: username_0 on 2015-12-26)

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$).

**Tags:** expanders

> **Comments:**
> **username_1**: have you checked the survey http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf? see section 5.3.  
> **username_2**: You might want to check out constructions by Lubetzky et al and Margulis. The references are mentioned in http://arxiv.org/pdf/1304.4132v2.pdf. AFAIK explicit families of non bipartite Ramanujan expanders for every degree 'd' are not known.  

---

## 0 answers

