Ramanujan graph

In spectral graph theory, a Ramanujan graph, is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". These graphs are indirectly named after Srinivasa Ramanujan; their name comes from the Ramanujan–Petersson conjecture, which was used in a construction of some of these graphs.

Definition

Let ${\displaystyle G}$ be a connected ${\displaystyle d}$-regular graph with ${\displaystyle n}$ vertices, and let ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$ be the eigenvalues of the adjacency matrix of ${\displaystyle G}$ (or the spectrum of ${\displaystyle G}$). Because ${\displaystyle G}$ is connected and ${\displaystyle d}$-regular, its eigenvalues satisfy ${\displaystyle d=\lambda _{1}>\lambda _{2}}$ ${\displaystyle \geq \cdots \geq \lambda _{n}\geq -d}$.

Define ${\displaystyle \lambda (G)=\max _{i\neq 1}|\lambda _{i}|=\max(|\lambda _{2}|,|\lambda _{n}|)}$. A connected ${\displaystyle d}$-regular graph ${\displaystyle G}$ is a Ramanujan graph if ${\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}$.

Many sources uses an alternative definition ${\displaystyle \lambda '(G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|}$ (whenever there exists ${\displaystyle \lambda _{i}}$ with ${\displaystyle |\lambda _{i}|<d}$) to define Ramanujan graphs.[1] In other words, we allow ${\displaystyle -d}$ in addition to the "small" eigenvalues. Since ${\displaystyle \lambda _{n}=-d}$ if and only if the graph is bipartite, we will refer to the graphs that satisfy this alternative definition but not the first definition bipartite Ramanujan graphs.

As observed by Toshikazu Sunada, a regular graph is Ramanujan if and only if its Ihara zeta function satisfies an analog of the Riemann hypothesis.[2]

Examples and constructions

The complete graph ${\displaystyle K_{d+1}}$ has spectrum ${\displaystyle d,-1,-1,\dots ,-1}$, and thus ${\displaystyle \lambda (K_{d+1})=1}$ and the graph is a Ramanujan graph for every ${\displaystyle d>1}$. The complete bipartite graph ${\displaystyle K_{d,d}}$ has spectrum ${\displaystyle d,0,0,\dots ,0,-d}$ and hence is a bipartite Ramanujan graph for every ${\displaystyle d}$.

The Petersen graph has spectrum ${\displaystyle 3,1,1,1,1,1,-2,-2,-2,-2}$, so it is a 3-regular Ramanujan graph. The icosahedral graph is a 5-regular Ramanujan graph.[3]

A Paley graph of order ${\displaystyle q}$ is ${\displaystyle {\frac {q-1}{2}}}$-regular with all other eigenvalues being ${\displaystyle {\frac {-1\pm {\sqrt {q}}}{2}}}$, making Paley graphs an infinite family of Ramanujan graphs.

Mathematicians are often interested in constructing ${\displaystyle d}$-regular Ramanujan graphs for every fixed ${\displaystyle d}$. Current constructions of infinite families of such Ramanujan graphs are often algebraic.

• Lubotzky, Phillips and Sarnak[1] show how to construct an infinite family of ${\displaystyle (p+1)}$-regular Ramanujan graphs, whenever ${\displaystyle p}$ is a prime number and ${\displaystyle p\equiv 1{\pmod {4}}}$. Their proof uses the Ramanujan conjecture, which led to the name of Ramanujan graphs. Besides being Ramanujan graphs, their construction satisfies some other properties, for example, their girth is ${\displaystyle \Omega (\log _{p}(n))}$ where ${\displaystyle n}$ is the number of nodes.
• Morgenstern[4] extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever ${\displaystyle p}$ is a prime power.
• Arnold Pizer proved that the supersingular isogeny graphs are Ramanujan, although they tend to have lower girth than the graphs of Lubotzky, Phillips, and Sarnak.[5] Like the graphs of Lubotzky, Phillips, and Sarnak, the degrees of these graphs are always a prime number plus one. These graphs have been proposed as the basis for post-quantum elliptic-curve cryptography.[6]
• Adam Marcus, Daniel Spielman and Nikhil Srivastava[7] proved the existence of infinitely many ${\displaystyle d}$-regular bipartite Ramanujan graphs for any ${\displaystyle d\geq 3}$. Later[8] they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices. Michael B. Cohen[9] showed how to construct these graphs in polynomial time.

It is still an open problem whether there are infinitely many ${\displaystyle d}$-regular (non-bipartite) Ramanujan graphs for any ${\displaystyle d\geq 3}$. In particular, the problem is open for ${\displaystyle d=7}$, the smallest case for which ${\displaystyle d-1}$ is not a prime power and hence not covered by Morgenstern's construction.

Ramanujan graphs as expander graphs

The constant ${\displaystyle 2{\sqrt {d-1}}}$ in the definition of Ramanujan graphs is the best possible constant for each ${\displaystyle d}$ and for large graphs: in other words, for every ${\displaystyle d}$ and ${\displaystyle \epsilon >0}$, there exists ${\displaystyle n}$ such that all ${\displaystyle d}$-regular graphs ${\displaystyle G}$ with at least ${\displaystyle n}$ vertices satisfy ${\displaystyle \lambda (G)>2{\sqrt {d-1}}-\epsilon }$. (See below for more precise statements and proof sketches.) On the other hand, Friedman[10] showed that for every ${\displaystyle d}$ and ${\displaystyle \epsilon >0}$ and for sufficiently large ${\displaystyle n}$, a random ${\displaystyle d}$-regular ${\displaystyle n}$-vertex graph ${\displaystyle G}$ satisfies ${\displaystyle \lambda (G)<2{\sqrt {d-1}}+\epsilon }$ with high probability. This means that Ramanujan graphs are essentially the best possible expander graphs.

Due to achieving the tight bound on ${\displaystyle \lambda (G)}$, the expander mixing lemma gives excellent bounds on the uniformity of the distribution of the edges in Ramanujan graphs, and any random walks on the graphs has a logarithmic mixing time (in terms of the number of vertices): in other words, the random walk converges to the (uniform) stationary distribution very quickly. Therefore, the diameter of Ramanujan graphs are also bounded logarithmically in terms of the number of vertices.

Extremality of Ramanujan graphs

If ${\displaystyle G}$ is a ${\displaystyle d}$-regular graph with diameter ${\displaystyle m}$, a theorem due to Noga Alon[11] states

${\displaystyle \lambda _{2}(G)\geq 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor m/2\rfloor }}.}$

Whenever ${\displaystyle G}$ is ${\displaystyle d}$-regular and connected on at least three vertices, ${\displaystyle |\lambda _{2}|<d}$, and therefore ${\displaystyle \lambda (G)\geq \lambda _{2}}$. Let ${\displaystyle {\mathcal {G}}_{n}^{d}}$ be the set of all connected ${\displaystyle d}$-regular graphs ${\displaystyle G}$ with at least ${\displaystyle n}$ vertices. Because the minimum diameter of graphs in ${\displaystyle {\mathcal {G}}_{n}^{d}}$ approaches infinity for fixed ${\displaystyle d}$ and increasing ${\displaystyle n}$, this theorem implies an earlier theorem of Alon and Boppana[12] which states

${\displaystyle \lim _{n\to \infty }\inf _{G\in {\mathcal {G}}_{n}^{d}}\lambda (G)\geq 2{\sqrt {d-1}}.}$

A slightly stronger bound is

${\displaystyle \lambda _{2}(G)\geq 2{\sqrt {d-1}}\cdot \left(1-{\frac {c}{m^{2}}}\right),}$

where ${\displaystyle c\approx 2\pi ^{2}}$. The outline of the proof is the following. Take ${\displaystyle k=\left\lfloor {\frac {m}{2}}\right\rfloor -1}$. Let ${\displaystyle T_{d,k}}$ be the complete ${\displaystyle (d-1)}$-ary tree of height ${\displaystyle k}$ (each internal vertex has ${\displaystyle d-1}$ children), and let ${\displaystyle A_{d,k}}$ be its adjacency matrix. We want to prove that ${\displaystyle \lambda _{2}(G)\geq \lambda _{1}(T_{d,k})=2{\sqrt {d-1}}\cos \theta }$, where ${\displaystyle \theta ={\frac {\pi }{k+2}}}$. Define a function ${\displaystyle g:V(T_{d,k})\rightarrow \mathbb {R} }$ by ${\displaystyle g(x)=(d-1)^{-\delta /2}\cdot \sin((k+1-\delta )\theta )}$, where ${\displaystyle \delta }$ is the distance from ${\displaystyle x}$ to the root of ${\displaystyle T_{d,k}}$. One can verify that ${\displaystyle A_{t,k}g=\lambda _{1}(T_{d,k})g}$ and that ${\displaystyle \lambda _{1}(T_{d,k})}$ is indeed the largest eigenvalue of ${\displaystyle A_{d,k}}$. Now let ${\displaystyle s}$ and ${\displaystyle t}$ be a pair of vertices at distance ${\displaystyle m}$ in ${\displaystyle G}$ and define

${\displaystyle f(v)={\begin{cases}c_{1}g(v_{s})&{\text{for }}v{\text{ at distance }}\leq k{\text{ from }}s,\\-c_{2}g(v_{t})&{\text{for }}v{\text{ at distance }}\leq k{\text{ from }}t,\\0&{\text{otherwise,}}\end{cases}}}$

where ${\displaystyle v_{s}}$ is a vertex in ${\displaystyle T_{d,k}}$ which distance to the root is equal to the distance from ${\displaystyle v}$ to ${\displaystyle s}$ and the symmetric for ${\displaystyle v_{t}}$. (One can think of this as "embedding" two disjoint copies of ${\displaystyle T_{d,k}}$, with some vertices collapsed into one.) By choosing the value of positive reals ${\displaystyle c_{1},c_{2}}$ properly we get ${\displaystyle f\perp 1}$, ${\displaystyle (Af)_{v}\geq \lambda _{1}(T_{d,k})f_{v}}$ for ${\displaystyle v}$ close to ${\displaystyle s}$ and ${\displaystyle (Af)_{v}\leq \lambda _{1}(T_{d,k})f_{v}}$ for ${\displaystyle v}$ close to ${\displaystyle t}$. Then by the min-max theorem we get

$${\displaystyle \lambda _{2}(G)\geq fAf^{T}/\|f\|^{2}\geq \lambda _{1}(T_{d,k})\approx 2{\sqrt {d-1}}\left(1-{\frac {1}{2}}\left({\frac {2\pi }{m}}\right)^{2}\right),}$$

as desired.

See also

• Expander graph
• Expander mixing lemma
• Spectral graph theory

References

1. Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Ramanujan graphs". Combinatorica. 8 (3): 261–277. doi:10.1007/BF02126799.
2. Terras, Audrey (2011), Zeta functions of graphs: A stroll through the garden, Cambridge Studies in Advanced Mathematics, 128, Cambridge University Press, ISBN 978-0-521-11367-0, MR 2768284
3. Weisstein, Eric W. "Icosahedral Graph". mathworld.wolfram.com. Retrieved 2019-11-29.
4. Moshe Morgenstern (1994). "Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q". Journal of Combinatorial Theory, Series B. 62: 44–62. doi:10.1006/jctb.1994.1054.
5. Pizer, Arnold K. (1990), "Ramanujan graphs and Hecke operators", Bulletin of the American Mathematical Society, New Series, 23 (1): 127–137, doi:10.1090/S0273-0979-1990-15918-X, MR 1027904
6. Eisenträger, Kirsten; Hallgren, Sean; Lauter, Kristin; Morrison, Travis; Petit, Christophe (2018), "Supersingular isogeny graphs and endomorphism rings: Reductions and solutions" (PDF), in Nielsen, Jesper Buus; Rijmen, Vincent (eds.), Advances in Cryptology – EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018, Proceedings, Part III (PDF), Lecture Notes in Computer Science, 10822, Cham: Springer, pp. 329–368, doi:10.1007/978-3-319-78372-7_11, MR 3794837
7. Adam Marcus; Daniel Spielman; Nikhil Srivastava (2013). Interlacing families I: Bipartite Ramanujan graphs of all degrees. Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium.
8. Adam Marcus; Daniel Spielman; Nikhil Srivastava (2015). Interlacing families IV: Bipartite Ramanujan graphs of all sizes. Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium.
9. Michael B. Cohen (2016). Ramanujan Graphs in Polynomial Time. Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium. arXiv:1604.03544. doi:10.1109/FOCS.2016.37.
10. Friedman, Joel (2003). "Relative expanders or weakly relatively Ramanujan graphs". Duke Math. J. 118 (1): 19–35. doi:10.1215/S0012-7094-03-11812-8. MR 1978881.
11. Nilli, A. (1991), "On the second eigenvalue of a graph", Discrete Mathematics, 91 (2): 207–210, doi:10.1016/0012-365X(91)90112-F, MR 1124768.
12. Alon, N. (1986). "Eigenvalues and expanders". Combinatorica. 6 (2): 83–96. doi:10.1007/BF02579166. MR 0875835.

Further reading

• Giuliana Davidoff; Peter Sarnak; Alain Valette (2003). Elementary number theory, group theory and Ramanujan graphs. LMS student texts. 55. Cambridge University Press. ISBN 0-521-53143-8. OCLC 50253269.
• T. Sunada (1985). "L-functions in geometry and some applications". Lecture Notes in Math. Lecture Notes in Mathematics. 1201: 266–284. doi:10.1007/BFb0075662. ISBN 978-3-540-16770-9.

External links

• Survey paper by M. Ram Murty