25
$\begingroup$

I recently taught expanders, and introduced the notion of Ramanujan graphs. Michael Forbes asked why they are called this way, and I had to admit I don't know. Anyone?

$\endgroup$
36
$\begingroup$

To add some content to the answers here, I'll explain briefly what Ramanujan's conjecture is.

First of all, Ramanujan's conjecture is actually a theorem, proved by Eichler and Igusa. Here is one way to state it. Let $r_m(n)$ denote the number of integral solutions to the quadratic equation $x_1^2 + m^2 x_2^2 + m^2 x_3^2 + m^2 x_4^2 = n$. If $m=1$, that $r_m(n) > 0$ was of course proved by Legendre, but Jacobi gave the exact count: $r_1(n) = 8 \sum_{d \mid n, 4 \not \mid d} d$. Nothing similarly exact is known for larger $m$ but Ramanujan conjectured the bound: $r_m(n) = c_m \sum_{d \mid n} d + O(n^{1/2 + \epsilon})$ for every $\epsilon > 0$, where $c_m$ is a constant dependent only on $m$.

Lubtozky, Phillips and Sarnak constructed their expanders based on this result. I'm not familiar with the details of their analysis but the basic idea, I believe, is to construct a Cayley graph of $PSL(2,Z_q)$ for a prime $q$ that $1 \bmod 4$, using generators determined by every sum-of-four-squares decomposition of $p$, where $p$ is a quadratic residue modulo $q$. Then, they relate the eigenvalues of this Cayley graph to $r_{2q}(p^k)$ for integer powers $k$.

A reference, other than the Lubotzky-Phillips-Sarnak paper itself, is Noga Alon's brief description in Tools from Higher Algebra.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ nice ! great answer. $\endgroup$ – Suresh Venkat Oct 19 '10 at 22:08
21
$\begingroup$

Wikipedia delivers this answer rather promptly. Quoting

Constructions of Ramanujan graphs are often algebraic. Lubotzky, Phillips and Sarnak show how to construct an infinite family of $p+1$-regular Ramanujan graphs, whenever $p = 1 \mod 4$ is a prime. Their proof uses the Ramanujan conjecture, which led to the name of Ramanujan graphs.

The paper referred to is Ramanujan graphs A. Lubotzky, R. Phillips and P. Sarnak, COMBINATORICA Volume 8, Number 3 (1988), 261-277, DOI: 10.1007/BF02126799.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ the question is: what is the ramanujan conjecture $\endgroup$ – Suresh Venkat Oct 19 '10 at 21:51
  • $\begingroup$ It is sometimes much better to preserve links when you quote. $\endgroup$ – Tsuyoshi Ito Oct 20 '10 at 2:21
  • $\begingroup$ Indeed. I underestimated the seriousness of the question. $\endgroup$ – Dave Clarke Oct 20 '10 at 13:31

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.