13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Are the papers using different normalizations of the Laplacian? $\endgroup$ – Qiaochu Yuan Dec 26 '14 at 1:08
  • $\begingroup$ For a regular graph, the Laplacian is just $d - A$ (the adjacency matrix), so the second part of the statement in (3) (interpreted for adjacency spectra) corresponds to that in (1). The usual definition, in terms of adjacency spectra, is that the second largest (in absolute value) eigenvalue is at most $d-2\sqrt{d-1}$. (Note the range of possible adjancency eigenvalues is $[d, -d]$.) Presumably the definitions should match. $\endgroup$ – Kimball Dec 26 '14 at 10:01
  • $\begingroup$ Peter wrote a nice short survey in the AMS called what is an exapnder - ams.org/notices/200407/what-is.pdf $\endgroup$ – Asaf Dec 26 '14 at 10:26
  • $\begingroup$ @QiaochuYuan I don't see such an issue and neither do I see how that could help reconcile the discrepancy. $\endgroup$ – user6818 Dec 27 '14 at 1:55
  • 1
    $\begingroup$ @user6818 I just took a look at the BSS paper, and their definition seems to match with what I gave in my comment, since the Laplacian eigenvalues are d - the adjacency ones. In HLW (which I didn't double check now), you should be looking at absolute values of eigenvalues. So it seems to me the definitions match. $\endgroup$ – Kimball Dec 27 '14 at 4:08
19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "-d" may not be an adjacency eigenvalue of a $d-$regular graph - right? And some conventions do drop the $-2\sqrt{d-1}$ part of the definition - right? The only way the two definitions that I quoted can be simultaneously be quoted is if the second definition is implicitly dropping the largest and the smallest Laplacian eigenvalue and then counting - right? $\endgroup$ – user6818 Jan 11 '15 at 8:36
  • $\begingroup$ BTW, I have asked this follow-up question, mathoverflow.net/questions/193658/… Can you kindly help? $\endgroup$ – user6818 Jan 11 '15 at 8:37
7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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".

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.