I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify.


(1)
The Hoory-Linial-Wigderson review on expanders in its definition 5.11 calls a d-regular graph to be Ramanujan if the second highest (adjacency?) eigenvalue is bounded above by $2\sqrt{d-1}$.


(2)
The Batson-Spielman-Srivastava paper (arxiv:0808.0163v3) on page 2 seems to say that a d-regular graph is Ramanujan if the non-zero Laplacian eigenvalues lie between $[d-2\sqrt{d-1},d + 2\sqrt{d-1}]$.


Aren't these two things different?


Like the largest eigenvalue of a d-regular Laplacian can I guess be as large as $2d$ even for Ramanujan graphs (and will definitely be so for bipartite d-regular Ramanujan) but how come BSS is asking for a stronger upper bound than that?


And why does Hoory-Linial-Wigderson not have any lower bound in their definition? Can the smallest eigenvalue of a d-regular adjacency matrix be arbitrarily low-right?


(3)
Also the BSS paper in the footnote on page 3 says that the largest (Laplacian?) eigenvalue is at least $d+2\sqrt{d-1}$ and the second-smallest (Laplacian?) eigenvalue is at most $d-2\sqrt{d-1}$.


Are the above two bounds independent of what the Alon-Bopanna bound says as in the smallest possible value of the second-highest eigenvalue is $2\sqrt{d-1}$? 



What is a "Ramanujan Graph"?
Ramanujan graphs were first defined by Lubotzky, Phillips and Sarnak:
<http://math1.math.huji.ac.il/~alexlub/PAPERS/ramanujan%20graphs/ramanujanGraphs.pdf>


As you can see, they are $d$-regular and and all eigenvalues of the adjacency matrix, except for $\pm d$, are in $[-2\sqrt{d-1},2\sqrt{d-1}]$. This is equivalent to your 2nd definition. The name "Ramanujan" was coined because all constructions of infinite families available for more than 25 years, relied on deep number theory/algebraic geometry (In particular the Ramanujan conjecture, as proved by Deligne). A drawback of these constructions was that the degree $d$ had to be of the form $d=1+q$, with $q$ a prime power. In Problem 10.7.3 of his book on expanders, Lubotzky asked whether there are infinite families of $d$-regular Ramanujan graphs for other values of $d$. The answer is provided in that paper by Marcus-Spielman-Srivastava:
<http://arxiv.org/pdf/1304.4132.pdf>


Namely: for every $d\geq 3$, there exists infinite families of $d$-regular, bipartite Ramanujan graphs. Note that the proof is purely existential. At the same time, it is completely elementary. So maybe "Ramanujan graph" is not the best terminology after all.


