What is a "Ramanujan Graph"?

Question

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}$?

Answer 1

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.

Answer 2

I meant to write this as a comment to Alain's answer, but it didn't fit.

I will discuss this in terms of the eigenvalues of the adjacency matrix.

As Alain wrote, the original definition of Lubotzky, Phillips and Sarnak states that a $d$-regular graph is Ramanujan if the maximum absolute value of eigenvalues not equal to $\pm d$, is at most $2\sqrt{d-1}$. In the Hoory, Linial, Wigderson survey (see Section 2.4 and Definition 5.11), a $d$-regular graph is called Ramanujan if the maximum absolute value of eigenvalues not equal to $d$ (what they call $\lambda$), is at most $2\sqrt{d-1}$. Note that by this definition, there would be no bipartite $d$-regular Ramanujan graphs since $-d$ would always appear as an eigenvalue. My guess is that Hoory, Linial and Wigderson meant the same thing as Lubotzky, Phillips and Sarnak and perhaps they used $\lambda$ in their definition as both the "expander mixing lemma" relating the edge distribution in the graph to its eigenvalues and the eigenvalue-expansion inequalities can be stated in terms of $\lambda$. In Sarnak's survey mentioned by Asaf, Sarnak calls a $d$-regular graph Ramanujan if its second largest eigenvalue is at most $2\sqrt{d-1}$. By this definition, the recent breakthrough work of Marcus, Spielman and Srivastava shows the existence of $d$-regular Ramanujan graphs for any degree $d\geq 3$; by the LPS definition, this recent works shows the existence of bipartite $d$-regular Ramanujan graphs for any $d\geq 3$. I would go with the LPS definition.

For what is worth, in 2005 at an IAS Workshop on Expanders, I with some other grad students, asked Lubotzky about the name "Ramanujan graphs" and he told us that Sarnak suggested using this name.

Answer 3

Like Sebi's answer, this should really be a comment but it's too long, and easier to read with proper formatting.

The distinction between (1) and (2), once you've translated so that both talk about the same matrix, concerns whether we require one bound on the eigenvalues or two. This is a significant distinction which also caused some confusion for me (with this question), but it really just amounts to whether or not you care about "bipartiteness". For example, the rate of ordinary "forward" diffusion on a graph is governed by the smallest nontrivial eigenvalue of the Laplacian, $\lambda_2$ (the algebraic connectivity), but the rate of "reverse" diffusion is governed by the largest, $\lambda_n$ (the "bipartiteness").

Equivalently, a random walk on a bipartite graph (with $\lambda_n = 2d$) will alternate between the partite sets, and in this sense never truly converges to a uniform distribution on the vertices; what's more, for nonbipartite graphs, the closer $\lambda_n$ gets to $2d$, the more the random walk tends to alternate between two sets, corresponding to an eigenvector of $\lambda_n$. This is related to the expander mixing lemma that Sebi mentioned.

The bound you mentioned in (3) is the Alon-Boppana bound, but it is only an asymptotic bound: if you prefer, it should really be $\lambda_2 \le d - 2\sqrt{d-1} + o(1)$. So a Ramanujan graph is one which is "better than any infinite family of graphs could be".