Ramanujan graph

In spectral graph theory, a Ramanujan graph, named after Srinivasa Ramanujan, is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders.

Examples of Ramanujan graphs include the clique, the biclique $K_{{n,n}}$ , and the Petersen graph. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". 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.^[1]

Definition

Let $G$ be a connected $d$ -regular graph with $n$ vertices, and let $\lambda _{0}\geq \lambda _{1}\geq \ldots \geq \lambda _{{n-1}}$ be the eigenvalues of the adjacency matrix of $G$ . Because $G$ is connected and $d$ -regular, its eigenvalues satisfy $d=\lambda _{0}>\lambda _{1}$ $\geq \ldots \geq \lambda _{{n-1}}\geq -d$ . Whenever there exists $\lambda _{i}$ with $|\lambda _{i}|<d$ , define

\lambda (G)=\max _{{|\lambda _{i}|<d}}|\lambda _{i}|.\,

A $d$ -regular graph $G$ is a Ramanujan graph if $\lambda (G)\leq 2{\sqrt {d-1}}$ .

A Ramanujan graph is characterized as a regular graph whose Ihara zeta function satisfies an analogue of the Riemann Hypothesis.

Extremality of Ramanujan graphs

For a fixed $d$ and large $n$ , the $d$ -regular, $n$ -vertex Ramanujan graphs nearly minimize $\lambda (G)$ . If $G$ is a $d$ -regular graph with diameter $m$ , a theorem due to Nilli^[2] states

\lambda _{1}\geq 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor m/2\rfloor }}.

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

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

Constructions

Constructions of Ramanujan graphs are often algebraic.

Lubotzky, Phillips and Sarnak^[3] show how to construct an infinite family of $(p+1)$ -regular Ramanujan graphs, whenever $p$ is a prime number and $p\equiv 1(\mod 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 $\Omega (\log _{p}(n))$ where $n$ is the number of nodes.
Morgenstern^[4] extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever $p$ is a prime power.
Adam Marcus, Daniel Spielman and Nikhil Srivastava^[5] proved the existence of $d$ -regular bipartite Ramanujan graphs for any $d$ . Later^[6] they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices.

References

↑ Audrey Terras, Zeta Functions of Graphs: A Stroll through the Garden, volume 128, Cambridge Studies in Advanced Mathematics, Cambridge University Press, (2010).
↑ A Nilli, On the second eigenualue of a graph, Discrete Mathematics 91 (1991) pp. 207-210.
↑ Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Ramanujan graphs". Combinatorica. 8 (3): 261–277. doi:10.1007/BF02126799.
↑ Moshe Morgenstern (1994). "Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q". J. Combinatorial Theory, Series B. 62: 44–62. doi:10.1006/jctb.1994.1054.
↑ 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.
↑ 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.

Guiliana Davidoff; Peter Sarnak; Alain Valette (2003). Elementary number theory, group theory and Ramanjuan 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

This article is issued from Wikipedia - version of the 10/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.